Pilas, Colas y Dipolo

PILAS

Una pila es una 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,

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar, que coloca un objeto en la pila, y su operación inversa, retirar, 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. 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).

Pila no vacía

Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que podemos trabajar con una pila vacía como con una pila normal.

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso no vacía:

El proceso sigue siendo muy sencillo:

1. Hacemos que nodo -> siguiente apunte de Pila.
2. Hacemos que pila apunte a nodo.

Leer y eliminar un elemento

Ahora sólo existe un caso posible, ya que sólo podemos leer desde un extremo de la pila. Partiremos de una pila con uno o más nodos, y usaremos un puntero auxiliar, nodo:

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.
2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila - > siguiente.
3. Guardamos el contenido del nodo para volverlo como retorno, recuerda que la operación pop equivale a leer y borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Si la pila sólo tiene un nodo, el proceso sigue siendo válido, ya que el valor de la Pila -> siguiente es NULL, y después de eliminar el último nodo la pila quedará vacía, y el valor de Pila será NULL.

COLAS

Una cola es una estructura de datos, características por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo y la operación de extracción 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 y operaciones, donde 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 implementan en lenguajes orientados a objetos mediante clases, en forma de lista enlazadas.

LISTAS ENLAZADAS

Una lista es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructura de datos. Consiste en una secuencia de nodos, en los que se guardan datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior. El principal beneficio de las listas enlazadas respecto a los arreglos convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento. Una lista enlazadas es un tipo de dato auto referenciado porque contienen un puntero de la lista en tiempo constante, pero no permiten un acceso aleatorio. Existen diferentes tipos de lista enlazadas:

Lista Enlazadas Simples
La lista enlazadas básicas es la lista enlazadas 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.

Lista Doblemente Enlazadas

Es un tipo de lista enlazada más sofisticada donde cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL o a la lista vacía si es el primer nodo, y otro que apunta al siguiente nodo, o apunta al valor NULL o a la lista vacía si es el último nodo.

Lista 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 enlazadas circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que regrese hasta el nodo original. Desde otro punto de vista, la lista enlazadas circulares pueden ser vista como lista son comienzo ni fin.

Dipolos

Esta estructura equivale a dos colas colocadas una en un sentido y la otra en otro sentido contrario, por ello las operaciones de inserción y eliminación se pueden realizar por ambos extremos. Dos casos especiales se pueden tener, el dipolo de entrada restringida donde sólo se puede insertar por un extremo y eliminar por ambos y sólo se puede suprimir por un extremo. Se llamará a estos extremos como izquierdo (izq) y derecho (der). Sus operaciones básicas son: creación, destrucción, verificación de dipolo vacío, inserción de un nuevo elemento por la izquierda, la inserción por la derecha, eliminación por la izquierda, eliminación por la derecha, consulta del elemento que está más a la izquierda y del que está más a la derecha.