Estructura de datos - Cola
La cola (Queue) es una estructura de datos lineal que sigue el principio de primero en entrar, primero en salir (First In First Out, FIFO), comparable a la escena de hacer cola para comprar boletos en la vida real: la primera persona que hace cola recibe el servicio primero.
Concepto y principio de la cola
front
rear
enqueue: insertar en rear (final de la cola) | dequeue: eliminar de front (frente de la cola) | complejidad O(1)
Verificación FIFO: encolar 10→20→30, desencolar 10→20→30 (primero en entrar, primero en salir)
La cola solo permite operaciones de inserción en un extremo (final de la cola) y operaciones de eliminación en el otro extremo (frente de la cola).
Esto es exactamente lo contrario del principio LIFO de la pila.
Implementación de cola con arreglos
Ejemplo
#include <stdbool.h>
#define MAX 100
struct Queue {
int items[MAX];
int front; /* Puntero de frente: apunta al primer elemento */
int rear; /* Puntero de final: apunta a la siguiente posición de inserción */
};
void initQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}
bool isEmpty(struct Queue* q) {
return q->front == q->rear;
}
bool isFull(struct Queue* q) {
return q->rear == MAX;
}
/* Encolar: agregar un elemento al final de la cola */
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("¡Cola llena!\n");
return;
}
q->items[q->rear++] = value; /* Escribir en rear, luego mover rear hacia adelante */
printf("Encolar: %d\n", value);
}
/* Desencolar: eliminar un elemento del frente de la cola */
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("¡Cola vacía!\n");
return -1;
}
return q->items[q->front++]; /* Devolver el elemento en front, luego mover front hacia adelante */
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10); /* Encolar: 10 */
enqueue(&q, 20); /* Encolar: 20 */
enqueue(&q, 30); /* Encolar: 30 */
printf("Desencolar: %d\n", dequeue(&q)); /* Salida: Desencolar: 10 (primero en entrar, primero en salir) */
printf("Desencolar: %d\n", dequeue(&q)); /* Salida: Desencolar: 20 */
printf("Desencolar: %d\n", dequeue(&q)); /* Salida: Desencolar: 30 */
return 0;
}
La cola implementada con un arreglo normal tiene el problema del "desbordamiento falso": a medida que se encolan y desencolan continuamente, front y rear se mueven constantemente hacia el final del arreglo, y aunque haya muchos espacios vacíos al frente del arreglo, no se pueden reutilizar. La solución es usarCola circular。
Cola circular
Fórmulas clave de la cola circular
Encolar: items[rear] = value; rear = (rear + 1) % MAX;
Desencolar: value = items[front]; front = (front + 1) % MAX;
Vacío: front == rear | Lleno: (rear + 1) % MAX == front
Ejemplo de ejecución (capacidad=5, máximo almacenar 4): encolar 10→20→30→40, desencolar 10→20, encolar 50→60 → 60 se guarda en el índice 0 (envoltura) aprovechando perfectamente el espacio liberado
La cola circular considera lógicamente el arreglo como una estructura anular conectada de extremo a extremo, y logra la envoltura del puntero mediante la operación de módulo.
Ejemplo
#include <stdbool.h>
#define MAX 5 /* Capacidad deliberadamente pequeña para observar el efecto circular */
struct CircularQueue {
int items[MAX];
int front; /* Índice del frente */
int rear; /* Índice del final (siguiente posición de inserción) */
};
void initQueue(struct CircularQueue* q) {
q->front = 0;
q->rear = 0;
}
/* Vacío: front y rear coinciden */
bool isEmpty(struct CircularQueue* q) {
return q->front == q->rear;
}
/* Lleno: (rear + 1) % MAX == front
Nota: la cola circular deja un espacio vacío a propósito para distinguir entre vacío y lleno */
bool isFull(struct CircularQueue* q) {
return (q->rear + 1) % MAX == q->front;
}
/* Encolar: escribir en rear, luego rear se mueve circularmente */
void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf("¡Cola circular llena!\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % MAX; /* Módulo para lograr la envoltura */
printf("Encolar: %d (rear=%d)\n", value, q->rear);
}
/* Desencolar: devolver el elemento en front, luego front se mueve circularmente */
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("¡Cola circular vacía!\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % MAX; /* Módulo para lograr la envoltura */
return value;
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 10); /* Encolar: 10 (rear=1) */
enqueue(&q, 20); /* Encolar: 20 (rear=2) */
enqueue(&q, 30); /* Encolar: 30 (rear=3) */
enqueue(&q, 40); /* Encolar: 40 (rear=4) — capacidad 5, máximo almacenar 4 */
printf("Desencolar: %d\n", dequeue(&q)); /* Desencolar: 10 (front=1) */
printf("Desencolar: %d\n", dequeue(&q)); /* Desencolar: 20 (front=2) */
enqueue(&q, 50); /* Encolar: 50 (rear=0 — ¡envoltura al principio!) */
enqueue(&q, 60); /* Encolar: 60 (rear=1) */
printf("Elementos restantes: ");
while (!isEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n"); /* Salida: Elementos restantes: 30 40 50 60 */
return 0;
}
Escenarios de aplicación de la cola
| Escenarios de aplicación | Descripción |
|---|---|
| Búsqueda en anchura (BFS) | Recorrer los nodos del grafo capa por capa, se necesita una cola para almacenar los nodos "por visitar" |
| Planificación de tareas del sistema operativo | La CPU asigna los segmentos de tiempo (time slices) según el orden de llegada de las tareas. |
| Cola de tareas de impresión | Varias computadoras comparten una impresora, las solicitudes de impresión se ponen en cola y se procesan en el orden de envío. |
| Cola de mensajes | En sistemas distribuidos, los mensajes producidos por los productores se transmiten a los consumidores a través de una cola. |