Unidad III ESTRUCTURAS LINEALES.

PILA

Una pila es un TDA que se caracteriza por el hecho de que el último elemento en entrar es el primero en salir

La definición de pila nos indica que todas las operaciones trabajan sobre el mismo extremo de la secuencia. En otras palabras, los elementos se sacan de la estructura en el orden inverso al orden en que se han insertado, ya que el único elemento de la secuencia que se puede obtener es el último (figura 1).

EJEMPLOS DE PILAS

En nuestra vida diaria podemos ver este comportamiento muy a menudo. Por ejemplo, si apilamos los platos de una vajilla, únicamente podremos coger el último plato añadido a la pila, porque cualquier intento de coger un plato del medio de la pila (como el plato oscuro de la figura 2) acabará en un destrozo. Otro ejemplo lo tenemos en los juegos de cartas, en los que generalmente robamos las cartas (de una en una) de la parte superior del mazo (figura 2).

En el mundo informático también encontramos pilas, como por ejemplo, en los navegadores web. Cada vez que accedemos a una nueva página, el navegador la añade a una pila de páginas visitadas de manera que cuando seleccionamos la opción “Anterior” el navegador coge la página que se encuentra en la cima de la pila, porque es justamente la última página visitada.

Otro ejemplo lo tenemos en los procesadores de texto, en los que los cambios introducidos en el texto tambbien se almacenan en una pila. Cada vez que apretamos la combinacion de teclas Ctrl+Z deshacemos el ultimo cambio introducido, mientras que cada vez que apretamos la combinacion Ctrl+Y volvemos a añadir a la pila el cambio deshecho.

EJEMPLO MAS ESTRUCTURADO.

Se pide definir una nueva operación, denominada intersección, que amplíe el TAD cola. Esta operación recibirá como entrada dos colas con los elementos ordenados de manera creciente y devolverá una cola ordenada de forma estrictamente creciente solo con los elementos que aparezcan en las dos colas de entrada (fig.13).

                                   Fig. 13. Ejemplo de la operación intersección

El hecho que la cola esté ordenada nos evita tener que recorrer toda la cola cada vez que queramos comprobar si contiene un elemento dado. En otras palabras, si el primer elemento de la cola a es más pequeño que el primer elemento de la cola b, ya es seguro que no encontraremos un elemento igual en toda la cola b, porque todos los elementos de la cola b serán mayores que el primero de la cola a.

Por tanto con la información establecemos que la estrategia de la operación intersección será la siguiente:

1.- Crear la cola en la que se encolarán los elementos comunes a ambas colas de entrada.

2.- Mientras las dos colas no estén vacías, leer el primer elemento de ambas.

3.- si los 2 elementos son iguales, encolar el elemento en la cola resultado y desencolarlo de las 2 colas de entrada. En caso contrario si los 2 elementos no son iguales, desencolar solo el elemento más pequeño.

4.- Volver al punto 2 mientras no se haya vaciado ninguna de las dos colas.

OPERACIONES BÁSICAS PARA TRABAJAR CON PILAS.

Nombre	Descripción
Crear	Crea una pila vacía
Apilar	Inserta un elemento en la pila
Desapilar	Extrae el elemento situado en la cima de la pila
Cima	Devuelve el elemento situado en la cima de la pila
Vacía	Devuelve cierto si la pila está vacía y falso en caso contrario

Las operaciones del TAD pila se clasifican en:

•      Operaciones constructoras: crear, apilar y desapilar.

•      Operaciones consultoras: cima y vacía.           

Igualmente, las operaciones constructoras se clasifican en:

·         Operaciones generadoras: Crear y Apilar, porque son imprescindibles para conseguir cualquier estado de la pila.

·         Operaciones modificadoras: Desapilar, porque modifica el estado de la pila extrayendo el elemento de la cima, pero no es una operación imprescindible  para construir una pila.

LISTAS

Una lista es un TAD caracterizado por el hecho de que permite añadir, borrar o consultar cualquier elemento de la secuencia. Es la estructura lineal más flexible, hasta el punto de considerar los TAD pila y cola casos particulares del TAD lista.

OPERACIONES BÁSICAS CON LISTAS

Nombre	Descripción
Crear	Crea una lista vacía
Insertar	Inserta un elemento en la lista delante del punto de interés
Borrar	Extrae el elemento distinguido y desplaza el punto de interés al elemento siguiente
Actual	Devuelve el elemento distinguido
Vacía	Devuelve cierto si la lista está vacía y falso en caso contrario
Principio	Sitúa el punto de interés sobre el primer elemento de la lista
Avanzar	Desplaza el punto de interés al elemento siguiente
Fin	Devuelve cierto si el punto de interés está en el extremo derecho (final) de la lista y falso en caso contrario

TIPOS DE LISTAS

LISTAS ENLAZADAS LINEALES: LISTAS SIMPLES ENLAZADAS

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

LISTAS DOBLEMENTE ENLAZADAS

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

LISTAS ENLAZADAS CIRCULARES

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros.

LISTAS ENLAZADAS SIMPLES CIRCULARES

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado.

LISTAS ENLAZADAS DOBLEMENTE CIRCULARES

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

NODOS CENTINELAS

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.

COLA

Una cola es un TDA caracterizado por el hecho que el primer elemento en entrar es el primero en salir.

La definición de cola nos indica que las operaciones trabajan sobre ambos extremos de la secuencia: un extremo para añadir los elementos y el otro para consultarlos o extraerlos. En otras palabras, los elementos se extraen en el mismo orden en que se han insertado previamente, ya que se insertan por el final de la secuencia y se extraen por la cabecera (figura 6).

La mayoría de nuestra vida nos la pasamos haciendo colas: para comprar la entrada en un cine, para pagar en la caja de un supermercado, para visitarnos por el médico, etc. La idea siempre es la misma: se atiende la primera persona de la cola, que es la que hace más rato que espera, y una vez atendida sale de la cola y la persona siguiente pasa a ser la primera de la cola (figura 7).

Si en el mundo real es habitual ver colas, en el mundo informático todavía lo es más, cuando el sistema operativo ha de gestionar el acceso a un recurso compartido (procesos que quieren ejecutarse en la CPU, trabajos que se envían a una impresora, descarga de ficheros etc.) una de las estrategias más utilizadas es organizar las peticiones por medio de colas. Por ejemplo, la figura 8 nos muestra una captura de una cola de impresión en un instante dado, en este caso la tarea 321 se está imprimiendo porque es la primera en la cola, mientras que la tarea 326 será la última en imprimirse porque ha sido la última en llegar

Nombre	Descripción
Crear	Crea una cola vacía
Encolar	Inserta un elemento en la cola
Desencolar	Extrae el elemento situado al principio de la cola
Cabeza	Devuelve el elemento situado al principio de la cola
Vacía	Devuelve cierto si la cola está vacía y falso en caso contrario

OPERACIONES BASICAS CON COLAS

APLICACIONES DE LAS COLAS

Esta estructura de datos se usa en muchos sistemas operativos, por ejemplo Unix, para llevar el control  de la ejecución de procesos, cada proceso en el sistema es almacenado en una lista y esta se va recorriendo, dándole un pequeño tiempo del microprocesador a cada proceso, durante la fracción de segundo de cada proceso este asume que tiene el control total del procesador. Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).Si está trabajando en un sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".

Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.