Estructura De Datos: Cola

Estructura de Datos: Cola

Son una estructura lineal de datos similar a las pilas, diferenciandose de ellas en el modo de insercion y eliminacion de datos, en la que la eliminacion se realiza en el principio de la lista de datos y las inserciones ocurren en el otro extremo, en el final.
En las colas el primer elemento que entro es el primero en salir; por ello se le conoce como lista FIFO(First In, First Out, Primero en entrar, primero en salir), por ello las colas se usan para almacenar datos que necesitan ser procesados segun el orden de llegada.



En la vida real se tienen muchos ejemplos de colas: la cola de un autobus, la cola de un cine, entre otros. En todas ellas el primero elemento (pasajero o cliente) que llega es el primero que sale.
En informatica existen tambiennumerosas aplicaciones de las colas. Por ejemplo, El procesador central atiende -normalmente- por riguroso orden de llamadas del usuario; por tanto, todas las llamadas se almacenan en una cola.

Las acciones que están permitidas en una cola son:
Creación de una cola vacía.
Verificación de que una cola esta vacía.
Añadir un dato al final de una cola.
Eliminación de los datos de la cabeza de lacola.
Cola de Prioridad
Una cola de prioridad es una generalización de los conceptos de pila y cola en la que, tras entrar en la cola, la salida de los elementos no se basa necesariamente en el orden de llegada sino que se basa en un orden definido entre ellos.
La extracción de elementos de una cola de prioridad puede buscar minimizar o maximizar el valor del elemento saliente.
En el modelobásico de una cola de prioridad la operaciones que consideramos son:

Insertar en la cola,
Obtener el elemento mínimo (o maximo),
Eliminar el elemento mínimo (o maximo).

La realización de estas operaciones no requiere mantener ordenada (ni total ni parcialmente) la colección de elementos en la cola.

Implementación mediante array
Las colas se pueden implementar utilizando arrays, este seutilizara para almacenar los datos, se definiran dos punteros uno con la direccion del inicio y otro con la direccion del final de la cola.

Cuando un elemento se añade a la cola, se verifica si el puntero final apunta a una posición válida, entonces se añade el elemento a la cola y se incrementa el puntero en 1. Cuando un elemento se elimina de la cola, se hace una prueba para ver si la colaestá vacía y, si no es así, se recupera el elemento de la posición apuntada por el puntero de inicio y éste se incrementa en 1. Este procedimiento funciona bien hasta la primera vez que el puntero de cabeza o cabecera alcanza el extremo del array y el array queda o bien vacío o bien lleno.
El medio más eficiente, sin embargo, para almacenar una cola en un array, es utilizar un tipo especial dearray que junte el extremo final de la cola con su extremo cabeza. Tal array se denomina array circular y permite que el array completo se utilizará para almacenar elementos de la cola sin necesidad
de que ningún dato se desplace.

Operaciones de la cola
Una cola permite un conjunto limitado de operaciones, inicializar la cola, añadir un nuevo elemento (Insertar)o quitar/eliminar un elemento(Eliminar). El tipo Cola proporciona también Frente, que permite ver el primer elemento de la cola. Para esta implementación, con array circular, el tipo cola es el siguiente:

#define MaxTamQ 100
typedef struct
{ int frente;
int final;
TipoDato listaQ[MaxTamQ];
}Cola;
Crearcola
La primera operación que se realiza sobre una cola es inicializarla para que a continuación puedanañadirse elementos a la cola.

void CrearCola(Cola* Q)
{
Q->frente = O;
Q->final = O;
}
Insertar
Antes de que comience el proceso de inserción, el índice final apunta al último elemento insertado. El nuevo elemento se sitúa en la posición siguiente. El cálculo de las posiciones sucesivas se consigue mediante el operador resto (%). Después de situar el elemento de la lista, el índice...