← Estructuras de datos desde cero · Lección 9/32
Cola circular y deque
Dar la vuelta con el módulo
Si sabes cuántos caben como máximo (los últimos 5 mensajes, los últimos 60 cuadros de un juego), puedes usar un arreglo fijo y hacer que la cola dé la vuelta: cuando el final llega a la última casilla, sigue en la casilla 0.
El operador módulo % hace la vuelta solo: (i + 1) % tamaño va 0, 1, 2, 3, 4, 0, 1… Nunca se mueve a nadie, nunca se crea memoria nueva y todo es O(1). Se llama cola circular o *ring buffer*.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
El residuo de dividir entre 5 siempre va de 0 a 4 y vuelve a empezar: justo los índices de un arreglo de 5 casillas.
Toda la lección en una página
Dar la vuelta con el módulo
Si sabes cuántos caben como máximo (los últimos 5 mensajes, los últimos 60 cuadros de un juego), puedes usar un arreglo fijo y hacer que la cola dé la vuelta: cuando el final llega a la última casilla, sigue en la casilla 0.
El operador módulo % hace la vuelta solo: (i + 1) % tamaño va 0, 1, 2, 3, 4, 0, 1… Nunca se mueve a nadie, nunca se crea memoria nueva y todo es O(1). Se llama cola circular o *ring buffer*.
for (let i = 0; i < 12; i++) {
console.log(i, "->", i % 5);
}
El residuo de dividir entre 5 siempre va de 0 a 4 y vuelve a empezar: justo los índices de un arreglo de 5 casillas.
La cola circular
La cola circular guarda tres números: cabeza (dónde está el primero), tamano (cuántos hay) y capacidad (cuántos caben). El lugar donde entra el siguiente es (cabeza + tamano) % capacidad.
Esta versión, cuando se llena, pisa al más viejo: es lo que quieres para «los últimos N» (un historial de puntajes, el promedio de los últimos cuadros). Otra opción es negarse a encolar cuando está llena.
class ColaCircular {
constructor(capacidad) {
this.datos = new Array(capacidad);
this.capacidad = capacidad;
this.cabeza = 0;
this.tamano = 0;
}
encolar(x) {
const fin = (this.cabeza + this.tamano) % this.capacidad;
this.datos[fin] = x;
if (this.tamano < this.capacidad) this.tamano++;
else this.cabeza = (this.cabeza + 1) % this.capacidad; // llena: se pierde el más viejo
}
desencolar() {
if (this.tamano === 0) return undefined;
const x = this.datos[this.cabeza];
this.cabeza = (this.cabeza + 1) % this.capacidad;
this.tamano--;
return x;
}
enOrden() {
const r = [];
for (let k = 0; k < this.tamano; k++) r.push(this.datos[(this.cabeza + k) % this.capacidad]);
return r;
}
}
const ultimos = new ColaCircular(5);
for (let i = 1; i <= 7; i++) ultimos.encolar(i);
console.log("casillas:", ultimos.datos);
console.log("en orden:", ultimos.enOrden());
console.log("sale:", ultimos.desencolar());
- Entraron del 1 al 7 en 5 casillas: el 6 y el 7 pisaron al 1 y al 2. Por eso las casillas dicen
[ 6, 7, 3, 4, 5 ]. - En orden, empezando por la cabeza:
[ 3, 4, 5, 6, 7 ], los últimos cinco. - El primero en salir es el 3, el más viejo que sobrevive.
Deque: entrar y salir por las dos puntas
Una deque (*double-ended queue*, se pronuncia «dek») junta la pila y la cola: deja meter y sacar por delante y por detrás, todo en O(1). Se hace con la misma idea circular: para meter por delante, la cabeza retrocede una casilla, (cabeza - 1 + capacidad) % capacidad (se suma la capacidad para no caer en negativos).
Un uso clásico: el máximo de cada ventana de tamaño k en una pasada. La deque guarda índices de candidatos de mayor a menor; los que ya no pueden ganar se sacan por detrás y los que salieron de la ventana, por delante.
// Máximo de cada ventana de 3. Para que se lea, la deque es un arreglo;
// en serio iría circular para que shift sea O(1).
function maximos(nums, k) {
const dq = []; // índices; sus valores van de mayor a menor
const r = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // ya no pueden ganar
dq.push(i);
if (dq[0] <= i - k) dq.shift(); // salió de la ventana
if (i >= k - 1) r.push(nums[dq[0]]);
}
return r;
}
console.log(maximos([1, 3, -1, -3, 5, 3, 6, 7], 3));
Seis ventanas de 3, seis máximos: [ 3, 3, 5, 5, 6, 7 ]. El frente de la deque siempre es el máximo de la ventana actual, y cada índice entra y sale una sola vez: O(n).