1 - Introducción a las colas (Queues)

Visión general

Las colas son estructuras de datos lineales que atienden elementos en el orden exacto en el que llegan. En C se modelan como un TDA compuesto por posiciones contiguas o nodos enlazados que exponen operaciones acotadas para insertar y extraer sin romper los invariantes del frente.

A lo largo del tutorial exploramos el modelo FIFO, revisamos colas simples, circulares y dobles, y explicamos cuándo conviene derivar hacia una cola de prioridad respaldada por un heap para asignar turnos según importancia.

Esta visión general también conecta con la implementación de colas de tareas, productores/consumidores y planificadores que veremos en los temas siguientes.

1.1 ¿Qué es una cola?

Una cola mantiene un puntero front (frente) que apunta al próximo elemento a retirar y un puntero rear (final) donde se inserta la siguiente solicitud. Al igual que cualquier TDA, define una capacidad y estados especiales para cola vacía o llena, lo que obliga a validar condiciones antes de mover punteros.

Relación entre los punteros front y rear de una cola

Los punteros avanzan en sentidos complementarios para garantizar el orden FIFO.

El siguiente fragmento muestra una implementación fija basada en array que deja listos los auxiliares de capacidad y los accesos a las operaciones principales:



#define TAM_MAX 128

typedef struct {
  int datos[TAM_MAX];
  int frente;
  int final;
  int cantidad;
} Cola;

void inicializar(Cola *cola) {
  cola->frente = 0;
  cola->final = 0;
  cola->cantidad = 0;
}

int enqueue(Cola *cola, int valor) {
  if (cola->cantidad == TAM_MAX) {
    return 0;
  }
  cola->datos[cola->final] = valor;
  cola->final = (cola->final + 1) % TAM_MAX;
  cola->cantidad++;
  return 1;
}

int dequeue(Cola *cola, int *valor) {
  if (cola->cantidad == 0) {
    return 0;
  }
  *valor = cola->datos[cola->frente];
  cola->frente = (cola->frente + 1) % TAM_MAX;
  cola->cantidad--;
  return 1;
}

int peek(const Cola *cola) {
  return cola->cantidad == 0 ? -1 : cola->datos[cola->frente];
}

La función enqueue valida el estado de cola llena, mientras que dequeue evita leer fuera de rango cuando no hay elementos pendientes. Las posiciones se ciclan con el operador módulo para reutilizar el arreglo sin desplazar datos.

Para ver la cola en acción, basta con un main que simule el ingreso de eventos y reporte qué elemento se encuentra en la cabecera:

#include <stdio.h>

int main(void) {
  Cola cola;
  inicializar(&cola);

  enqueue(&cola, 5);
  enqueue(&cola, 8);
  enqueue(&cola, 13);

  int valor;
  while (dequeue(&cola, &valor)) {
    printf("Atendido: %d\n", valor);
  }

  return 0;
}

Puedes copiar ambos fragmentos en CLion o en tu entorno favorito para observar cómo se respetan los estados vacío/lleno y para instrumentar pruebas con aserciones.

Simulación visual de operaciones en la cola

1.2 Modelo FIFO (First In, First Out)

FIFO describe la regla principal de una cola: el primer elemento que ingresa debe salir antes que los demás. Se implementa controlando los índices frente y final sin recorrer posiciones intermedias.

  1. Con la cola vacía encolamos los valores 12, 18 y 4. frente apunta al 12 y final se desplaza tres posiciones.
  2. El primer dequeue entrega 12 y actualiza frente a 18 sin tocar el resto de la memoria.
  3. Si agregamos otro valor (por ejemplo 30) este se ubica en la próxima ranura libre y quedará al final de la fila hasta que los anteriores sean atendidos.

Este modelo mantiene la predictibilidad en colas de impresión, colas de mensajes o buffers de red. Solo se altera en escenarios de prioridad, donde la ordenación se delega a una estructura auxiliar.

1.3 Diferencias con una pila

Aunque pilas y colas son lineales, se utilizan para objetivos distintos. La comparación siguiente resume los contrastes más relevantes:

Característica Cola lineal Pila Cola de prioridad
Orden de servicio FIFO estricto LIFO (el último en entrar sale primero) Depende de la prioridad asignada
Extremos usados Frente para extraer, final para insertar Un solo tope Frente virtual definido por el valor más prioritario
Complejidad O(1) encolado y desencolado O(1) push/pop O(log n) al insertar o extraer si se usa un heap
Casos de uso Turnos, buffers, tareas pendientes Deshacer/rehacer, evaluación de expresiones Planificadores, sistemas de tickets VIP, Dijkstra

1.4 Ventajas y limitaciones

  • Determinismo: al consumir y producir en extremos fijos, las colas simplifican la razón de cómo progresa el sistema.
  • Eficiencia: las operaciones se implementan en O(1) sin recorrer el arreglo ni realinear datos.
  • Limitaciones: no existe acceso directo a elementos intermedios y se debe manejar el caso de cola llena para evitar sobrescrituras.
  • Consideraciones de memoria: en C hay que inicializar punteros y contar elementos para no leer posiciones indefinidas, sobre todo cuando se reserve memoria dinámica.

1.5 Ejemplos cotidianos

  • Sistemas de turnos: bancos o centros de atención usan colas para entregar tickets y atender en el orden emitido.
  • Spool de impresoras: los documentos se encolan y la impresora retira uno por vez, respetando la hora de llegada.
  • Planificación Round Robin: los procesos se encolan y reciben un quantum de CPU antes de volver al final de la lista.
  • Colas de red: los routers mantienen paquetes encolados mientras los enlaces están ocupados.

Visualizar estos comportamientos ayuda a diseñar APIs claras para las colas específicas que abordaremos en los siguientes temas.

Retornar