Recorrido narrado · La cola y el buffer circular

Por qué el anillo es un dibujo

Suele dibujarse el buffer circular como un anillo. La memoria no es circular: es el mismo array contiguo de siempre. Lo circular es la cuenta de índices, que con el mod salta del último al 0.

Mismo estado dibujado de dos maneras, con el mismo resaltado. Lo que gira es la cuenta de índices, no la memoria.

En la figura de arriba, el estado final del ejemplo anterior (capacidad 4, inicio 2, cola C, D, E) aparece como anillo y como array.

Los invariantes:

Texto

0 ≤ inicio < capacidad0 ≤ longitud ≤ capacidadlos elementos están en inicio, inicio + 1, …, inicio + longitud − 1, todo mod capacidad

Con eso, encolar y desencolar son O(1) y nunca se desplaza nada. Si la capacidad no alcanza, el buffer tiene que crecer, igual que un array dinámico; lo verás en el deque.

Su fila en la tabla de costos

Con la cola como interfaz, el buffer circular tiene dos variantes.

Representación	`encolar`	`desencolar`	`frente`
buffer circular que crece	O(1) amortizado; O(n) en el peor caso, cuando crece	O(1)	O(1)
buffer circular de capacidad fija	O(1); si está lleno, falla o descarta el más antiguo	O(1)	O(1)