Colas
Cargado por
Ernesto DavidColas
Cargado por
Ernesto DavidColas
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 cola
Las 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.
Saca_cliente
Frente
Cliente 2
Cliente 6
Cliente 11
Cliente 5
Cliente 28
Cliente 13
Cliente 9
Inserta_cliente
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.
