Colas
(FIFO).
Una cola
es una estructura de datos en la que el primer dato en entrar es el primer
dato en salir. Es decir, es una estructura FIFO (First In First Out).
Todo el mundo conocemos como funciona una cola, los nuevos se ponen al final,
los servicios se prestan al principio y no está permitido “colarse”. Las mismas
reglas se aplican a las colas de datos almacenadas en la memoria de un
computador.
Hay
varias formas de implementar una cola en la memoria de un computador. Una forma
simple consiste en almacenar los datos en posiciones de memoria adyacentes y
utilizar punteros para el principio y el fin de la cola. Cuando un elemento se
añade a la cola, el puntero de la parte posterior se ajusta para que señale al
nuevo elemento. De manera similar, cuando un elemento se elimina de la cola, se
ajusta el puntero delantero para que señale al nuevo primer elemento.
El
problema de este método para implementar las colas es que las posiciones de
memoria que ocupan, varían a medida que se añaden y eliminan elementos de la
misma. La solución habitual consiste en asignar un área fija para almacenar la
cola y permitir que se mueva en este área de manera circular. Un área de
almacenamiento de esta forma se denomina buffer circular , y puede apreciarse
en la figura siguiente.
Entre
las aplicaciones que tienen las colas se encuentran el almacenamiento de datos
en camino, entre un procesador y un periférico, o actuar como punto intermedio
en las redes de comunicación de datos.
Pilas
(LIFO).
Una pila
es una colección ordenada de datos a los que sólo se puede acceder por un
extremo, denominado tope o cima de la pila. La pila es una estructura en la que
el último elemento en entrar será el primero en salir, es decir, es lo que se
denomina estructura LIFO (Last In First Out).
Podemos
comparar esta estructura con una pila de platos colocada sobre un muelle.
Cuando
se
añade un nuevo plato en lo alto de la pila, los demás bajan, cuando se retira
un plato de la pila, los demás suben. Igual que en el caso de las colas, van a
existir dos punteros, uno que indica la posición tope de la pila, denominado puntero
de pila, y otro que señala su base, denominado base de pila, y que
mantiene el mismo valor mientras existe la pila. Cuando la pila esta vacía el
puntero de pila tiene el mismo valor que la base de pila.
La
pila es una de las estructuras más importantes en computación. Se usa en
cálculos, para pasar de un lenguaje de computador a otro y, para transferir el
control de una parte del programa a otra. Las operaciones que se pueden
realizar tanto con las colas como con las pilas, son las siguientes:
· Añadir o eliminar un elemento: Si es una cola
podremos añadirlo o eliminarlo al final
de
la misma, y si es una pila al principio.
· Acceder al primer elemento: Normalmente es el único al
que se va a poder acceder
directamente.
· Acceder al elemento siguiente del último procesado:
Este es el mecanismo normal de
acceso
tanto a colas como a pilas.
· Saber si está vacía: Están
vacías si no contienen ningún elemento.
