Definición del tipo de dato abstracto pila

Una pila (stack) es un tipo especial de lista en la que la inserción y borrado de nuevos elementos se realiza sólo por un extremo que se denomina cima o tope (top).

Una pila es una colección ordenada de elementos, en la cual, en un extremo pueden insertarse o retirarse otros elementos, colocados por la parte superior. Una pila permite la inserción y eliminación de elementos, por lo que realmente es un objeto dinámico que cambia constantemente.

Es importante notar que los elementos que se agregan por un extremo de la lista o arreglo (pensando en un arreglo como una lista de elementos), se sacan por el mismo extremo, es decir, el último elemento que se agrega a la lista es el primer elemento que se puede sacar y ningún otro más, por eso, a este tipo de estructuras se les conoce como LIFO (last-in, first-out o última entrada, primera salida).

Un ejemplo de pila o stack se puede observar en el mismo procesador de un sistema de cómputo, es decir, cada vez que en los programas aparece una llamada a una función, el microprocesador guarda el estado de ciertos registros en un segmento de memoria, conocido como stack segment, mismo que será recuperado al regreso de la función.

Definición de las operaciones sobre pilas

Las operaciones que debe tener una pila se muestran a continuación.

Definición del tipo de dato abstracto cola

En la vida cotidiana es muy común ver las colas como una forma de agilizar los servicios de una empresa u organización. En informática, una cola representa una estructura de datos en la cual sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro extremo. También se le llama estructura FIFO (first-in, first-out o primera entrada, primera salida), debido a que el primer elemento en entrar será también el primero en salir. Al igual que las pilas, las escrituras de los datos son inserciones de nodos y las lecturas siempre eliminan el nodo leído.

Las colas se utilizan en sistemas informáticos, bancos, empresas, servicios, transportes y operaciones de investigación (entre otros), donde los objetos, transacciones, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento, tal cual como una fila (cola) en el banco, el proceso implica que la primera persona que entra sea la primera que salga.

En el siguiente ejemplo vemos una representación gráfica de una cola.

Definición de las operaciones sobre colas

Bicolas

La doble cola o bicola es una variante de las colas simples. Ésta es una cola de dos dimensiones en la que las inserciones y eliminaciones pueden realizarse en cualquiera de los dos extremos de la lista, pero no por la mitad. A diferencia de una cola simple, en donde sólo se necesita un método para leer y otro para escribir componentes en la lista, en una doble cola debe haber:

•Dos métodos para leer: uno para hacerlo por el frente y otro para leer por atrás.
•Dos métodos para escribir: uno para hacerlo por el frente y otro para escribir por atrás.

Por otro lado, existen dos variantes de las bicolas:

A continuación veremos de manera gráfica cómo se representan las operaciones en las bicolas DCER y DCSR. Observa en la imagen cómo por medio de flechas se muestran las inserciones y eliminaciones que se realizan sobre ellas.

En relación con el código anterior, es importante tomar en cuenta que el inicio de la cola debe ser declarada con dos apuntadores a nulo, uno que representa el inicio (pPrimero) y otro el final (pUltimo), como se observa en la siguiente imagen.

Por ejemplo, si quisiéramos agregar a la pila el elemento seis y después el elemento 100, lo declararíamos como se puede apreciar en la siguiente imagen.

La representación de la declaración anterior es la siguiente.