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 de la lista. La cola circular solucionó el inconveniente permitiendo que los índices 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:

CAP_CIRC = 128


class ColaCircular:
  def __init__(self, capacidad=CAP_CIRC):
    self.capacidad = capacidad
    self.datos = [None] * capacidad
    self.frente = 0
    self.final = 0
    self.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:

def siguiente_indice(indice, capacidad):
  return (indice + 1) % capacidad


class ColaCircular:
  ...

  def encolar(self, valor):
    if self.cantidad == self.capacidad:
      raise OverflowError("Cola llena")
    self.datos[self.final] = valor
    self.final = siguiente_indice(self.final, self.capacidad)
    self.cantidad += 1

  def desencolar(self):
    if self.cantidad == 0:
      raise IndexError("Cola vacia")
    valor = self.datos[self.frente]
    self.frente = siguiente_indice(self.frente, self.capacidad)
    self.cantidad -= 1
    return valor

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

5.4 Actualización de frente y final

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

class ColaCircular:
  ...

  def frente_actual(self):
    return None if self.cantidad == 0 else self.datos[self.frente]

  def espacio_disponible(self):
    return self.capacidad - self.cantidad

En sistemas multitarea conviene actualizar los índices 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 listo para Python

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

CAP_CIRC = 5


def siguiente(idx, capacidad):
  return (idx + 1) % capacidad


class ColaCircular:
  def __init__(self, capacidad=CAP_CIRC):
    self.capacidad = capacidad
    self.datos = [None] * capacidad
    self.frente = 0
    self.final = 0
    self.cantidad = 0

  def encolar(self, valor):
    if self.cantidad == self.capacidad:
      raise OverflowError("Cola llena")
    self.datos[self.final] = valor
    self.final = siguiente(self.final, self.capacidad)
    self.cantidad += 1

  def desencolar(self):
    if self.cantidad == 0:
      raise IndexError("Cola vacia")
    valor = self.datos[self.frente]
    self.frente = siguiente(self.frente, self.capacidad)
    self.cantidad -= 1
    return valor

  def imprimir(self):
    recorrido = []
    idx = self.frente
    for _ in range(self.cantidad):
      recorrido.append(str(self.datos[idx]))
      idx = siguiente(idx, self.capacidad)
    print(f"[circular] frente={self.frente} final={self.final} cantidad={self.cantidad} -> {' '.join(recorrido)}")


if __name__ == "__main__":
  cola = ColaCircular()

  for i in range(4):
    cola.encolar(i + 1)
  cola.imprimir()

  cola.desencolar()
  cola.desencolar()
  cola.imprimir()

  cola.encolar(99)
  cola.encolar(100)
  cola.imprimir()

  while cola.cantidad:
    valor = cola.desencolar()
    print("consumido:", valor)
  cola.imprimir()

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