Pilas, Colas, Listas.

Una pila, es una lista ordenada 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 informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa,retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto
• Implementación de recursividad.

Colas

Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Operaciones básicas de colas.-

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Listas

Al contrario que las pilas y las colas las listas enlazadas pueden acceder a una zona de memoria de forma aleatoria, ya que cada trozo de información lleva un enlace al siguiente elemento de la cadena. Una lista enlazada requiere una estructura de datos compleja, al contrario que las colas o las pilas, que pueden operar con elementos simples o complejos, además una operación de recuperación en una lista enlazada no elimina ni destruye el elemento de la lista. Para poder eliminar un elemento de una lista es necesario utilizar una operación especifica de eliminación.

Las listas enlazadas se utilizan principalmente para dos propósitos, crear arrays de un tamaño desconocido en memoria, y los archivos de almacenamiento en disco para bases de datos, las listas enlazadas permiten insertar y eliminar nuevos elementos.

Las listas pueden ser simplemente enlazadas o doblemente enlazadas, las simplemente enlazadas contienen un enlace al elemento siguiente, las doblemente enlazadas tanto al siguiente elemento como al elemento anterior del la lista.

Listas simplemente enlazadas.-

Una lista  simplemente enlazada necesita que cada elemento contenga un enlace con el siguiente elemento, cada elemento consiste en una estructura de campos de información  a punteros de enlace.

Existen dos formas de construir una lista simplemente enlazada , la primera es añadir un nuevo elemento al principio o al final de la lista, la otra añade los elementos en un punto especifico de la lista.

Si la lista ya esta ordenada, es conveniente mantenerla así, insertando los nuevos elementos en su lugar apropiado para lo cual se explora la lista de forma secuencial hasta encontrar el lugar apropiado, la nueva dirección se inserta en ese punto y los enlaces se vuelven a colocar como sea necesario.

Se pueden dar tres posibles situaciones al insertar un elemento en una lista enlazada.

Primero: El elemento se puede convertir en el primer elemento.

Segundo: Puede ser insertado entre otros dos elementos.

Tercero: Se puede convertir en el ultimo elemento de la lista.

Tener en cuenta que al cambiar el primer elemento hay que actualizar el punto de entrada en alguna parte del programa, también se puede utilizar un centinela, que no es

más que el primer elemento no cambia nunca con un valor especial, con lo que siempre será el primer elemento  de la lista pero se necesita una posición más de memoria. Para recuperar un elemento de la lista es como seguir una cadena, una rutina basada en el campo nombre. Para borrar un elemento al igual que para insertar un elemento se pueden dar los mismos tres casos, si se borra el primer elemento de la lista el puntero previo ha de hacerse nulo, y la función tiene que devolver un puntero al comienzo de la lista para que cuando se borre el primer elemento de la lista, el programa conozca la dirección del nuevo primer elemento de la lista. Las listas simplemente enlazadas solo se pueden recorrer en sentido ascendente y no en sentido descendente, para lo cual se pueden utilizar las listas doblemente enlazadas.

 Listas doblemente enlazadas.-

Las listas doblemente enlazadas consisten en datos y enlaces tanto al elemento siguiente como al elemento anterior. Con lo que se consiguen dos grandes ventajas, primero la lista se puede leer en cualquier dirección, la segunda es que se pueden leer los enlaces hacia delante como hacia atrás, con lo que si un enlace resulta no valido se puede reconstruir utilizando el otro enlace.

Como en las listas simplemente enlazadas, las doblemente enlazadas pueden contener una función que almacene cada elemento en una posición especifica de la lista a medida que esta se construye, en lugar de colocar cada elemento al final de la lista.