Deques y buffers circulares sin desplazar datos

Cuando una cola llega al final de un arreglo, no hace falta mover todo hacia el principio. Podemos volver a la primera posición libre y tratar el arreglo como un círculo. Esa idea convierte espacio fijo en una cola eficiente.

La deque: los dos extremos

Una deque, o cola doble, permite agregar y retirar por ambos extremos. Sus cuatro operaciones básicas son pushFront, pushBack, popFront y popBack.

Puede comportarse como cola usando un extremo para entrar y el otro para salir, o como pila usando el mismo extremo para ambas cosas. También sirve en algoritmos de ventana deslizante, donde elementos viejos salen por delante mientras nuevos candidatos entran por detrás.

El buffer circular: un arreglo que da la vuelta

Un buffer circular guarda posiciones de cabeza y cola dentro de un arreglo de capacidad fija. Después de la última celda, el índice siguiente vuelve a cero:

donde $C$ es la capacidad. Avanzar índices cuesta $O(1)$ y ningún elemento debe desplazarse. El arreglo físico es lineal; lo circular es la forma de interpretar sus posiciones.

Vacío y lleno se ven iguales

Si cabeza y cola tienen el mismo índice, el buffer podría estar vacío o lleno. Para evitar la ambigüedad podemos guardar además la cantidad $q$ de elementos. Entonces las invariantes son $0\leq q\leq C$, la cabeza señala el próximo valor que sale y la cola la próxima celda libre.

Otra estrategia reserva siempre una celda vacía, pero reduce la capacidad útil. Las dos son válidas; lo importante es que la representación permita distinguir todos sus estados.

Una cola circular mínima

Una cola circular mínima puede mantener esos tres datos:

class CircularQueue<T> {
  private readonly slots: Array<T | undefined>;
  private head = 0;
  private tail = 0;
  private count = 0;

  constructor(private readonly capacity: number) {
    if (capacity <= 0) throw new Error('La capacidad debe ser positiva.');
    this.slots = new Array<T | undefined>(capacity);
  }

  enqueue(value: T): boolean {
    if (this.count === this.capacity) return false;
    this.slots[this.tail] = value;
    this.tail = (this.tail + 1) % this.capacity;
    this.count += 1;
    return true;
  }

  dequeue(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.slots[this.head];
    this.slots[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity;
    this.count -= 1;
    return value;
  }
}

Qué hacer cuando se llena

Cuando el buffer se llena, la aplicación debe elegir una política. Una cola de trabajos puede rechazar el nuevo elemento o bloquear al productor. Un historial de métricas puede sobrescribir el dato más viejo porque interesa conservar sólo la ventana reciente.

No hay una respuesta universal. La capacidad fija vuelve explícito un límite que de otro modo aparecería tarde como consumo creciente de memoria.

El costo y el precio de la capacidad fija

Las operaciones en los extremos cuestan $O(1)$ y el espacio queda acotado por $O(C)$. El precio es elegir la capacidad y manejar correctamente los estados vacío y lleno.

Una deque basada en bloques puede crecer dinámicamente; un buffer circular prioriza memoria predecible. Para audio, redes, telemetría o comunicación entre productores y consumidores, esa previsibilidad suele ser más importante que crecer sin límite.

Dónde aparecen de verdad

Cierre

Una deque generaliza pilas y colas al permitir operaciones en ambos extremos. Un buffer circular implementa esas operaciones sobre espacio reutilizable, sin desplazamientos. La clave no es el módulo: son las invariantes de cabeza, cola, cantidad y política de capacidad.