Colas

COLAS
Una cola es una lista lineal de información que se accede en el siguiente orden, el primero que entra es el primero que sale. El primer ítem que se sitúa en la cola es el primer ítem recuperado, el segundo ítem que se sitúa en la cola es el segundo ítem recuperado, y así sucesivamente. Este orden es el único medio de almacenamiento y recuperación; una cola no permite acceso aleatorio a unítem específico.

Las colas se utilizan en muchos tipos de situaciones en programación, tal como simulaciones, planificaciones (como en el método PERT y el diagrama de Gant) y procesos de E/S.

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas,las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.
El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la colapuede comprar la entrada.
El nodo típico para construir pilas es el mismo que vimos en los capítulos anteriores para la construcción de listas y pilas:
struct nodo \{
int dato;
struct nodo *siguiente;
};

• DECLARACIONES DE TIPOS PARA MANEJAR COLAS EN C
Los tipos que definiremos normalmente para manejar colas serán casi los mismos que para manejar listas y pilas, tan sólo cambiaremosalgunos nombres:
typedef struct _nodo \{
int dato;
struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Cola;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Cola es el tipo para declarar colas.
[pic]
Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendomuy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la cola, que será el punto donde insertemos nuevos nodos.
Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremosdistintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.









• OPERACIONES BÁSICAS CON COLAS
De nuevo nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo permiten añadir y leer elementos:
• Añadir:Inserta un elemento al final de la cola.
• Leer: Lee y elimina un elemento del principio de la cola.


• AÑADIR UN ELEMENTO
Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la cola esté vacía.

• AÑADIR ELEMENTO EN UNA COLA VACÍA


Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además lospunteros que definen la cola, primero y ultimo que valdrán NULL:[pic]

El proceso es muy simple, bastará con que:
1. Hacer que nodo->siguiente apunte a NULL.
2. Que el puntero primero apunte a nodo.
3. Y que el puntero último también apunte a nodo.

• AÑADIR ELEMENTO EN UNA COLA NO VACÍA
De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en estecaso, al no estar vacía, los punteros primero y ultimo no serán nulos:
El proceso sigue siendo muy sencillo:
1. Hacemos que nodo->siguiente apunte a NULL.
2. Después que ultimo->siguiente apunte a nodo.
3. Y actualizamos último, haciendo que apunte a nodo.

• AÑADIR ELEMENTO EN UNA COLA, CASO GENERAL
Para generalizar el caso anterior, sólo necesitamos añadir una operación:
1....