Breve Introducción a las Pilas, Colas y Listas Enlazadas

Breve Introducción a las Pilas, Colas y Listas Enlazadas

PILAS

Podemos definir a una pila como una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informatice debido a su simplicidad y ordenación implícita de la propia estructura.

HISTORIA

El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos

clasificación:

PILA DE LLAMADAS:

Es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre las llamadas a subrutinas actualmente en ejecución en un programa en proceso. Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada.

COMO TIPO ABSTRACTO DE DATOS

La pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). ‘Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas.

Operaciones de pilas

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

Crear: se crea la pila vacía.

Apilar: se añade un elemento a la pila.(push)

Desapilar: se elimina el elemento frontal de la pila.(pop)

Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

Vacía: devuelve cierto si la pila está vacía o falso en caso contrario

como se muestra en la siguente imagen:

Implementación

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.

La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).

COLAS

Definición:

Una cola es una estructura de datos lineal, es decir una colección de elementos en la cual cada elemento tiene un sucesor y un predecesor únicos, con excepción del primero y del último. La estructura cola se caracteriza porque las operaciones de inserción y eliminación de elementos deben hacerse por extremos diferentes. Los elementos se insertan por uno de los extremos y se eliminan por el otro extremo.

En una estructura tipo cola se identifican los dos extremos por donde se realizan las operaciones. El frente o principio de la cola será el extremo en el cual se eliminarán elementos, mientras que el final será el extremo en el cual se harán las inserciones.

Tipos de colas

Entre los tipos de colas encontramos dos mas importantes que son:

Colas circulares:Es aquella en la cual el sucesor del ultimo elemento es el primero. Por lo tanto, el manejo de las colas como estructuras circulares permite un mejor uso del espacio de memoria reservado para la implementación de las mismas.

Colas Dobles:

Como su nombre lo indica, estas estructuras permiten realizar las operaciones de inserción y eliminación por cualquiera de sus extremos. Una cola doble también puede ser circular, en dicho caso, será necesario que los métodos de inserción y eliminación (sobre cualquiera de los extremos) considere el movimiento adecuado de los punteros.

Otros tipos de colas

Colas de prioridad:

En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

* Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

* Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

LISTAS ENLAZADAS

Definición de recorrido:

Recorrido simplemente despliega los datos almacenados en el arreglo Información, con ayuda de un segundo arreglo llamado Índice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

Explicación:

Apuntador toma el valor de Inicio, después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de 0, si cumple lo que hace es que despliega la Info[Apuntador], después Apuntador toma el valor de Índice[Apuntador] (El cual nos indica el siguiente nodo que sigue en la lista) y hace esto hasta que Apuntador sea igual a 0 (Cuando llega a este punto a llegado al fin de la Lista Enlazada).

Tipo de listas enlazadas:

Listas simples enlazadas (Básica)

Es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo 

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo 

Lista Doblemente Enlazada

Lista de dos vías. Cada nodo tiene dos enlaces: 1.- uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo 2.- otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Listas enlazadas circulares

El primer y el último nodo están unidos , podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original

Vistas como listas sin comienzo ni fin, 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 circulares simples 

Cada nodo tiene un enlace . “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.

Permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.

Lista Enlazada Doblemente Circular

Cada nodo tiene dos enlaces . “Enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero” 

Las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso

a algún nodo cercano. Aunque estructural mente una lista circular doblemente enlazada

no tiene ni principio ni fin.

Ventajas sobre los arrays:

No requieren memoria extra para soportar la expansión. Por el contrario, los arrays requieren memoria extra si se necesita expandirlo (una vez que todos los elementos tienen datos no se pueden añadir datos nuevos a un array).

Ofrecen una inserción/borrado de elementos más rápida que sus operaciones equivalentes en los arrays. Sólo se tienen que actualizar los enlaces después de identificar la posición de inserción/borrado. Desde la perspectiva de los arrays, la inserción de datos requiere el movimiento de todos los otros datos del array para crear un elemento vacío. De forma similar, el borrado de un dato existente requiere el movimiento de todos los otros datos para eliminar el elemento vacío.

En contraste, los arrays ofrecen las siguiente ventajas sobre las listas enlazadas:

Los elementos de los arrays ocupan menos memoria que los nodos porque no requieren campos de enlace.

Los arrays ofrecen un aceso más rápido a los datos, medante índices basados en enteros.

Las listas enlazadas son más apropiadas cuando se trabaja con datos dinámicos. En otras palabras, inserciones y borrados con frecuencia.

Por el contrario, los arrays son más apropiados cuando los datos son estáticos (las inserciones y borrados son raras). De todas formas, no olvide que si se queda sin espacio cuando añade ítems a un array, debe crear un array más grande, copiar los datos del array original el nuevo array mayor y elimiar el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace repetidamente.

Mezclando una lista de enlace simple con un array uni-dimensional para acceder a los nodos mediante los índices del array no se consigue nada. Gastará más memoria, porque necesitará los elementos del array más los nodos, y tiempo, porque necesitará mover los ítems del array siempre que inserte o borre un nodo. Sin embargo, si es posible integrar el array con una lista enlazada para crear una estructura de datos.