← Data structures from scratch · Lesson 9/32

Circular queue and deque

1/7

Wrapping around with modulo

If you know the most it will ever hold (the last 5 messages, the last 60 frames of a game), you can use a fixed array and let the queue wrap around: when the end reaches the last slot, it continues at slot 0.

The modulo operator % does the wrapping for you: (i + 1) % size goes 0, 1, 2, 3, 4, 0, 1… Nobody ever moves, no new memory is created, and everything is O(1). It's called a circular queue or *ring buffer*.

leccion.js

1for (let i = 0; i < 12; i++) {
2  console.log(i, "->", i % 5);
3}

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The remainder of dividing by 5 always goes from 0 to 4 and starts over: exactly the indexes of a 5-slot array.

The whole lesson on one page

Wrapping around with modulo

1for (let i = 0; i < 12; i++) {
2  console.log(i, "->", i % 5);
3}

The remainder of dividing by 5 always goes from 0 to 4 and starts over: exactly the indexes of a 5-slot array.

The circular queue

The circular queue keeps three numbers: cabeza (where the first one is), tamano (how many there are) and capacidad (how many fit). The slot where the next one goes is (cabeza + tamano) % capacidad.

This version overwrites the oldest when it's full: that's what you want for "the last N" (a score history, the average of the last frames). Another option is to refuse to enqueue when it's full.

1class ColaCircular {
2  constructor(capacidad) {
3    this.datos = new Array(capacidad);
4    this.capacidad = capacidad;
5    this.cabeza = 0;
6    this.tamano = 0;
7  }
8  encolar(x) {
9    const fin = (this.cabeza + this.tamano) % this.capacidad;
10    this.datos[fin] = x;
11    if (this.tamano < this.capacidad) this.tamano++;
12    else this.cabeza = (this.cabeza + 1) % this.capacidad;  // full: the oldest is lost
13  }
14  desencolar() {
15    if (this.tamano === 0) return undefined;
16    const x = this.datos[this.cabeza];
17    this.cabeza = (this.cabeza + 1) % this.capacidad;
18    this.tamano--;
19    return x;
20  }
21  enOrden() {
22    const r = [];
23    for (let k = 0; k < this.tamano; k++) r.push(this.datos[(this.cabeza + k) % this.capacidad]);
24    return r;
25  }
26}
27
28const ultimos = new ColaCircular(5);
29for (let i = 1; i <= 7; i++) ultimos.encolar(i);
30console.log("slots:   ", ultimos.datos);
31console.log("in order:", ultimos.enOrden());
32console.log("out:", ultimos.desencolar());

1 through 7 went into 5 slots: 6 and 7 overwrote 1 and 2. That's why the slots read [ 6, 7, 3, 4, 5 ].
In order, starting from the head: [ 3, 4, 5, 6, 7 ], the last five.
The first one out is 3, the oldest survivor.

Deque: in and out at both ends

A deque (*double-ended queue*, pronounced "deck") combines stack and queue: you can add and remove at the front and at the back, all in O(1). It's built with the same circular idea: to add at the front, the head steps back one slot, (cabeza - 1 + capacidad) % capacidad (adding the capacity avoids going negative).

A classic use: the maximum of every window of size k in one pass. The deque keeps indexes of candidates from largest to smallest; those that can no longer win are popped from the back, and those that left the window, from the front.

1// Maximum of each window of 3. For readability the deque is a plain array;
2// for real it would be circular so shift is O(1).
3function maximos(nums, k) {
4  const dq = [];   // indexes; their values go largest to smallest
5  const r = [];
6  for (let i = 0; i < nums.length; i++) {
7    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // can't win anymore
8    dq.push(i);
9    if (dq[0] <= i - k) dq.shift();                                  // left the window
10    if (i >= k - 1) r.push(nums[dq[0]]);
11  }
12  return r;
13}
14
15console.log(maximos([1, 3, -1, -3, 5, 3, 6, 7], 3));

Six windows of 3, six maximums: [ 3, 3, 5, 5, 6, 7 ]. The front of the deque is always the current window's maximum, and each index goes in and out once: O(n).