FIFO y LIFO

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.