← Estructuras de datos desde cero · Lección 8/32
Colas: el primero en llegar sale primero
Se entra por atrás, se sale por delante
Una cola (*queue*) es justa: el primero que llega es el primero al que atienden. FIFO (*first in, first out*). Sus operaciones:
- encolar (*enqueue*): meter al final.
- desencolar (*dequeue*): sacar del frente.
Con un arreglo, lo obvio es push para encolar y shift para desencolar. Funciona, pero acuérdate de la lección anterior: shift recorre a todos los que quedan un lugar. Con una fila de un millón, cada «¡el que sigue!» mueve un millón de casillas.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
Salen en el orden en que llegaron: Ana, luego Beto. Dani llegó después y queda atrás de Caro.
Toda la lección en una página
Se entra por atrás, se sale por delante
Una cola (*queue*) es justa: el primero que llega es el primero al que atienden. FIFO (*first in, first out*). Sus operaciones:
- encolar (*enqueue*): meter al final.
- desencolar (*dequeue*): sacar del frente.
Con un arreglo, lo obvio es push para encolar y shift para desencolar. Funciona, pero acuérdate de la lección anterior: shift recorre a todos los que quedan un lugar. Con una fila de un millón, cada «¡el que sigue!» mueve un millón de casillas.
const fila = [];
fila.push("Ana");
fila.push("Beto");
fila.push("Caro");
console.log("atiendo a", fila.shift());
fila.push("Dani");
console.log("atiendo a", fila.shift());
console.log("esperan:", fila);
Salen en el orden en que llegaron: Ana, luego Beto. Dani llegó después y queda atrás de Caro.
Una cola O(1) con un índice
El truco es no mover a nadie: en vez de sacar el primero del arreglo, se lleva un índice cabeza que dice dónde empieza la fila. Desencolar es leer datos[cabeza] y sumarle uno a cabeza. O(1).
Lo que ya salió se queda ocupando casillas al principio. Para no gastar memoria sin fin, cuando la parte vieja es más de la mitad, se recorta de una vez con slice. Ese recorte cuesta O(n), pero pasa tan de vez en cuando que, repartido entre todas las operaciones, sigue saliendo O(1) en promedio (se dice «amortizado»).
class Cola {
constructor() { this.datos = []; this.cabeza = 0; }
encolar(x) { this.datos.push(x); }
desencolar() {
if (this.vacia) return undefined;
const x = this.datos[this.cabeza++];
// limpieza de vez en cuando: tira lo que ya salió
if (this.cabeza * 2 > this.datos.length) {
this.datos = this.datos.slice(this.cabeza);
this.cabeza = 0;
}
return x;
}
get tamano() { return this.datos.length - this.cabeza; }
get vacia() { return this.tamano === 0; }
}
const c = new Cola();
const t0 = Date.now();
for (let i = 0; i < 20000; i++) c.encolar(i);
while (!c.vacia) c.desencolar();
console.log("Cola: ", Date.now() - t0, "ms");
const a = [];
const t1 = Date.now();
for (let i = 0; i < 20000; i++) a.push(i);
while (a.length) a.shift();
console.log("shift: ", Date.now() - t1, "ms");
Los dos procesan 20 000 elementos y shift tarda muchas veces más: cada salida recorre a todos los que quedan. Con diez veces más elementos, shift tardaría unas cien veces más; la Cola, unas diez. La Cola con índice es O(1) en cualquier navegador y en cualquier lenguaje.
Un adelanto: recorrer por capas
La cola es el corazón de la búsqueda en anchura (BFS), que vas a ver con los árboles y los grafos. La idea: para explorar un mapa desde un punto, encolas el punto de salida; luego, mientras haya alguien en la cola, lo sacas y encolas a sus vecinos que no hayas visto.
Como la cola atiende en orden de llegada, primero salen todos los que están a 1 paso, luego los de 2, luego los de 3: el mapa se explora por capas, como una onda en el agua. Así encuentra Snake si la arena quedó partida en dos.
const mapa = [
"S...",
".xx.",
"....",
];
const dist = mapa.map(f => [...f].map(() => "#"));
const cola = [[0, 0]];
dist[0][0] = 0;
let cabeza = 0;
while (cabeza < cola.length) {
const [y, x] = cola[cabeza++]; // desencolar
for (const [dy, dx] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
const ny = y + dy, nx = x + dx;
if (mapa[ny]?.[nx] === "." && dist[ny][nx] === "#") {
dist[ny][nx] = dist[y][x] + 1;
cola.push([ny, nx]); // encolar
}
}
}
for (const fila of dist) console.log(fila.join(" "));
Cada número es a cuántos pasos está esa casilla de la salida. Los # son los muros, que nunca se alcanzan. Fíjate en la cola: es un arreglo con un índice cabeza, la misma idea de la clase Cola.