← Data structures from scratch · Lesson 8/32
Queues: first come, first served
In at the back, out at the front
A queue is fair: the first to arrive is the first served. FIFO (*first in, first out*). Its operations:
- enqueue: add at the back.
- dequeue: remove from the front.
With an array, the obvious way is push to enqueue and shift to dequeue. It works, but remember the last lesson: shift moves everyone left one place. With a line of a million, every "next, please!" moves a million slots.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
They leave in the order they arrived: Ana, then Beto. Dani came later and is behind Caro.
The whole lesson on one page
In at the back, out at the front
A queue is fair: the first to arrive is the first served. FIFO (*first in, first out*). Its operations:
- enqueue: add at the back.
- dequeue: remove from the front.
With an array, the obvious way is push to enqueue and shift to dequeue. It works, but remember the last lesson: shift moves everyone left one place. With a line of a million, every "next, please!" moves a million slots.
const fila = [];
fila.push("Ana");
fila.push("Beto");
fila.push("Caro");
console.log("serving", fila.shift());
fila.push("Dani");
console.log("serving", fila.shift());
console.log("waiting:", fila);
They leave in the order they arrived: Ana, then Beto. Dani came later and is behind Caro.
An O(1) queue with an index
The trick is not moving anyone: instead of removing the first item from the array, keep an index cabeza (head) that says where the line starts. Dequeue reads datos[cabeza] and adds one to cabeza. O(1).
What already left keeps taking up slots at the front. To avoid wasting memory forever, when the old part is more than half, trim it in one go with slice. That trim costs O(n), but it happens so rarely that, spread across all operations, it's still O(1) on average (called "amortized").
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++];
// occasional cleanup: drop what already left
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");
Both process 20,000 items and shift takes many times longer: every removal shifts everyone left. With ten times more items, shift would take about a hundred times longer; the Cola, about ten. The indexed Cola is O(1) in any browser and any language.
A preview: exploring in layers
The queue is the heart of breadth-first search (BFS), which you'll see with trees and graphs. The idea: to explore a map from a point, enqueue the starting point; then, while someone is in the queue, take them out and enqueue their neighbors you haven't seen.
Since the queue serves in order of arrival, first come everyone 1 step away, then 2, then 3: the map is explored in layers, like a ripple on water. That's how Snake checks whether the arena got split in two.
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++]; // dequeue
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]); // enqueue
}
}
}
for (const fila of dist) console.log(fila.join(" "));
Each number is how many steps that cell is from the start. The # are walls, never reached. Look at the queue: an array with a cabeza index, the same idea as the Cola class.