Colas

Colas

Una cola es una estructura de datos donde el primer elemento en entrar es el primero en salir, tambin denominadas estructuras FIFO (First In, First Out).

Esta estructura de datos se puede definir como una lista enlazada con acceso FIFO a la que slo se tiene acceso al final de la lista para meter elementos y al principio de esta para sacarlos.

Los operadores asociados a este TDA y las funciones que los implementan en GLib son:

Tabla 14. Operadores asociados al TDA Cola.Operador Funciones asociadas a GQueue.

Iniciar cola. GQueue* g_queue_new (void)

Cola vaca. gboolean g_queue_is_empty (GQueue* queue)

Consultar frente cola. gpointer g_queue_peek_head (GQueue* queue)

Consultar final cola. gpointer g_queue_peek_tail (GQueue* queue)

Meter void g_queue_push_tail (GQueue* queue, gpointer data)

Sacar gpointer g_queue_pop_head (GQueue* queue)

Vaciar cola. void g_queue_free (GQueue* queue)

Definicin

Una cola es una estructura de datos de acceso restrictivo a sus elementos. Un ejemplo sencillo es la cola del cine o del autobs, el primero que llegue ser el primero en entrar, y afortunadamente en un sistema informtico no se cuela nadie salvo que el programador lo diga.

Las colas sern de ayuda fundamental para ciertos recorridos de rboles y grafos.

Las colas ofrecen dos operaciones fundamentales, que son encolar (al final de la cola) y desencolar (del comienzo de la cola). Al igual que con las pilas, la implementacin de las colas suele encapsularse, es decir, basta con conocer las operaciones de manipulacin de la cola para poder usarla, olvidando su implementacin interna.

Es una estructra de tipo FIFO (First In First Out), es decir: primero en entrar, primero en salir.

A continuacin se expone la implementacin de colas, con arrays y con listas enlazadas circulares. En ambos casos se cubren cuatro operaciones bsicas: Inicializar, Encolar, Desencolar, y Vaca. Las claves que contendrn sern simplemente nmeros enteros.

2 Diferentes operaciones definidas en la TDA colaLas operaciones para una cola son anlogas a las de las pilas; las diferencias sustanciales consisten en que las inserciones se hacen al final de la lista, y no al principio, y en que la terminologa tradicional para las colas y listas no es la misma. Se usaran las siguientes operaciones con colas:

1. ANULA(C) convierte la cola C en una lista vacia.

2. FRENTE(C) es una funcion que devuelve el valor del primer elemento de la cola C. FRENTE(C) se puede escribir en funcion de operaciones con listas, como RECUPERA(PRIMERI(C),C).

3. PONE_EN_COLA(x,C) inserta el elemento x al final de la cola C. En funcion de operaciones con listas, PONE_EN_COLA(x,C) es INSERTA(x,FIN(C),C).

4. QUITA_DE_COLA (C) suprime el primer elemento de C; es decir, QUITA_DE_COLA(C) es SUPRIME(PRIMERO(C),C).

5. VACIA(C) devuelve verdadero si, y solo si, C es una cola vacia.

Operaciones Bsicas:

CrearCola: Crea una Cola y la prepara para trabajar.

Agregar: Inserta un elemento en el final de la Cola.

Remover: Devuelve el elemento del frente de la Cola y a su vez lo remueve.

ColaVacia: Verifica si la Cola contiene elementos.

Frente: Retorna el elemento del frente de la Cola. No lo remueve.

VaciarCola: Reinicializa la Cola existente, borrando todos sus elementos.

Longitud: (Operacin opcional)Devuelve el nmero de tems que estn presentes en la Cola.

AsignarCola: Realiza la asignacin de una Cola a otra.

Saca_cliente

Cliente 9

Cliente 2

Cliente 6

Cliente 11

Cliente 5

Cliente 28

Cliente 13

Inserta_cliente

Frente