Índice

Colas

1. Principios de las colas

Cola

a. Modelo de datos cola

La cola es una lista que almacena los elementos en un orden específico. Es como la cola de caja de un supermercado. Las personas llegan una a una y forman la cola, y se van yendo una a una en el orden de llegada, después de haber pagado. Hay una persona en la cabeza de la cola, la primera, y una persona en el final de la cola, la última. Es el concepto de «el primero en llegar, el primero en salir», «First In First Out», denominado FIFO en informática:

images/06ri39.PNG

b. Implementación estática o dinámica

Una cola es una lista particular que utiliza los dos extremos de comienzo y fin, a diferencia de una pila, que solo usa uno. La implementación puede hacerse dinámica con punteros o contigua con una tabla.

Asignación dinámica de memoria

Cola:asignación dinámica de memoria

Representación de una cola dinámica:

images/06ri40.PNG

Hay que tener dos punteros para una cola. Uno para gestionar las entradas en la cola (último) y otro para gestionar las salidas (primero). Con memoria dinámica una cola no tiene tamaño máximo, excepto el de la memoria RAM disponible.

Asignación contigua de memoria

Cola:asignación contigua de memoria

Representación de una cola contigua:

images/06ri41.png

La gestión de una cola contigua es menos fácil de lo que parece en un principio. Hay dos índices: uno para el primero y otro para el último, pero hay que utilizar la tabla de forma circular. ...