5 - Colas circulares (Circular Queue)

5.1 Motivación y necesidad

La cola lineal tradicional sufre el problema de falsa saturación: una vez que final alcanza la capacidad, deja de aceptar elementos aunque haya casilleros libres al comienzo del arreglo. La cola circular solucionó el inconveniente permitiendo que los punteros vuelvan al inicio y reutilicen el espacio liberado.

Es indispensable en sistemas embebidos, colas de dispositivos y buffers de audio porque garantiza un uso parejo de la memoria sin reasignaciones.

5.2 Representación con arrays

La representación circular agrega un contador de elementos para distinguir entre estados vacío y lleno aun cuando frente y final ocupen el mismo índice. Este esqueleto sirve para cualquier tipo de dato:

#define CAP_CIRC 128

typedef struct {
  int datos[CAP_CIRC];
  int frente;
  int final;
  int cantidad;
} ColaCircular;

void inicializar(ColaCircular *c) {
  c->frente = 0;
  c->final = 0;
  c->cantidad = 0;
}

En implementaciones de bajo nivel es habitual colocar la estructura en memoria compartida y protegerla con exclusión mutua.

5.3 Uso del operador módulo (%)

La aritmética modular permite que cualquier desplazamiento excedente vuelva al inicio sin necesidad de condicionales complejos. Se aplica tras incrementar los punteros:

int siguienteIndice(int indice) {
  return (indice + 1) % CAP_CIRC;
}

int enqueue(ColaCircular *c, int valor) {
  if (c->cantidad == CAP_CIRC) {
    return 0;
  }
  c->datos[c->final] = valor;
  c->final = siguienteIndice(c->final);
  c->cantidad++;
  return 1;
}

int dequeue(ColaCircular *c, int *valor) {
  if (c->cantidad == 0) {
    return 0;
  }
  *valor = c->datos[c->frente];
  c->frente = siguienteIndice(c->frente);
  c->cantidad--;
  return 1;
}

El contador cantidad asegura que el operador módulo no provoque confusiones al comparar frente y final.

5.4 Actualización de front y rear

Las funciones utilitarias frenteActual y finalDisponible simplifican el uso de la cola desde capas superiores:

int frenteActual(const ColaCircular *c) {
  return c->cantidad == 0 ? -1 : c->datos[c->frente];
}

int espacioDisponible(const ColaCircular *c) {
  return CAP_CIRC - c->cantidad;
}

En sistemas multitarea conviene actualizar los punteros en secciones críticas para evitar que dos hilos los modifiquen simultáneamente.

5.5 Ventajas del modelo circular

  • Aprovechamiento total del buffer: cada celda se reutiliza en cuanto queda libre.
  • Complejidad constante: mantiene operaciones O(1) sin copiar datos.
  • Compatibilidad con DMA: muchos controladores de hardware consumen datos en secuencias circulares.

Estas ventajas convierten a la cola circular en la opción preferida para flujos continuos.

5.6 Problemas típicos a evitar

  • Confundir lleno/vacío: omitir el contador obliga a reservar un casillero extra para diferenciar estados.
  • Olvidar el operador módulo: hace que los índices sigan creciendo hasta salirse del arreglo.
  • Race conditions: cuando hay múltiples productores y consumidores se requiere sincronización explícita.
  • No validar datos: cargar estructuras sin verificar el valor devuelto de enqueue/dequeue puede perder eventos.

La depuración se vuelve sencilla si se agregan contadores de fallos y una función de traza que imprima el estado interno.

5.7 Ejemplo completo para CLion

Este archivo incluye un pequeño simulador de productor y consumidor. Alterna encolados y desencolados para demostrar cómo los índices regresan al inicio.

#include <stdio.h>

#define CAP_CIRC 5

typedef struct {
  int datos[CAP_CIRC];
  int frente;
  int final;
  int cantidad;
} ColaCircular;

void inicializar(ColaCircular *c) {
  c->frente = 0;
  c->final = 0;
  c->cantidad = 0;
}

int siguiente(int idx) {
  return (idx + 1) % CAP_CIRC;
}

int enqueue(ColaCircular *c, int valor) {
  if (c->cantidad == CAP_CIRC) {
    return 0;
  }
  c->datos[c->final] = valor;
  c->final = siguiente(c->final);
  c->cantidad++;
  return 1;
}

int dequeue(ColaCircular *c, int *valor) {
  if (c->cantidad == 0) {
    return 0;
  }
  *valor = c->datos[c->frente];
  c->frente = siguiente(c->frente);
  c->cantidad--;
  return 1;
}

void imprimir(const ColaCircular *c) {
  printf("[circular] frente=%d final=%d cantidad=%d -> ", c->frente, c->final, c->cantidad);
  for (int i = 0, idx = c->frente; i < c->cantidad; ++i) {
    printf("%d ", c->datos[idx]);
    idx = siguiente(idx);
  }
  puts("");
}

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

  for (int i = 0; i < 4; ++i) {
    enqueue(&cola, i + 1);
  }
  imprimir(&cola);

  int valor;
  dequeue(&cola, &valor);
  dequeue(&cola, &valor);
  imprimir(&cola);

  enqueue(&cola, 99);
  enqueue(&cola, 100);
  imprimir(&cola);

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

  return 0;
}

Puedes modificar el bucle principal para simular patrones diferentes y comprobar que el tamaño de la cola se mantienen constante.

Retornar