Lesson 10 of 2414 min read

Queues and Deques

First in, first out. You need one for breadth-first search, and a double-ended one for the sliding-window-maximum problem that trips up most candidates.

By the end: Build an O(1) queue and use a deque to keep a running maximum.

A queue is a line. You join at the back and leave from the front. First in, first out — the opposite of a stack.

You need one for breadth-first search, which is lesson 17 and one of the highest-value algorithms in interviews. So getting the queue right matters.

The trap first

The obvious implementation is push to add and shift to remove. It is also wrong for anything large, because shift moves every remaining element down one slot.

Why shift makes a queue quadratic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function drainWithShift(n) {
  const q = Array.from({ length: n }, (_, i) => i);
  let elementMoves = 0;
  while (q.length > 0) {
    elementMoves += q.length - 1;    // everything after index 0 shifts down
    q.shift();
  }
  return elementMoves;
}

function drainWithPointer(n) {
  const q = Array.from({ length: n }, (_, i) => i);
  let head = 0, elementMoves = 0;
  while (head < q.length) {
    head++;                          // nothing moves at all
    elementMoves += 0;
  }
  return elementMoves;
}

for (const n of [100, 400, 1600]) {
  console.log('n =', String(n).padStart(4),
    '| shift moves:', String(drainWithShift(n).toLocaleString('en-US')).padStart(11),
    '| pointer moves:', drainWithPointer(n));
}

Output

The queue you should actually write

A head-pointer queue: O(1) for everything

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Queue {
  #items = [];
  #head = 0;      // index of the front element

  enqueue(x) { this.#items.push(x); return this; }

  dequeue() {
    if (this.isEmpty) return undefined;
    const item = this.#items[this.#head];
    this.#items[this.#head] = undefined;   // release the reference
    this.#head++;
    // Occasionally compact so the discarded prefix does not grow forever.
    if (this.#head > 32 && this.#head * 2 >= this.#items.length) {
      this.#items = this.#items.slice(this.#head);
      this.#head = 0;
    }
    return item;
  }

  peek() { return this.#items[this.#head]; }
  get size() { return this.#items.length - this.#head; }
  get isEmpty() { return this.size === 0; }
}

const q = new Queue();
q.enqueue('a').enqueue('b').enqueue('c');
console.log('size:', q.size, '| peek:', q.peek());
console.log('dequeue:', q.dequeue(), '| dequeue:', q.dequeue());
console.log('size now:', q.size, '| empty?', q.isEmpty);
q.enqueue('d');
console.log('after enqueue d:', q.dequeue(), q.dequeue(), q.isEmpty);

Output

The BFS shape you will write over and over

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['D', 'E'],
  D: ['E'],
  E: [],
};

function bfsOrder(start) {
  const visited = new Set([start]);
  const queue = [start];
  let head = 0;                       // no shift anywhere
  const order = [];

  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);            // mark when ENQUEUING, not when dequeuing
        queue.push(next);
      }
    }
  }
  return order;
}

console.log('BFS from A:', bfsOrder('A'));

Output

Level-by-level processing

Often you need to know which level of the search you are on: the depth of a tree, the number of steps in a shortest path, the minute in a spreading-rot simulation. Capture the queue size at the top of each round and process exactly that many.

Processing one level at a time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29const tree = {
  val: 1,
  children: [
    { val: 2, children: [{ val: 4, children: [] }, { val: 5, children: [] }] },
    { val: 3, children: [{ val: 6, children: [] }] },
  ],
};

function levels(root) {
  const out = [];
  let queue = [root], head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;    // freeze the count for this level
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      level.push(node.val);
      for (const c of node.children) queue.push(c);
    }
    out.push(level);
  }
  return out;
}

const result = levels(tree);
console.log('levels:', result);
console.log('depth:', result.length);
console.log('widest level has', Math.max(...result.map(l => l.length)), 'nodes');

Output

Deques: both ends

A double-ended queue lets you add and remove at either end. In JavaScript an array technically does this, but unshift and shift are O(n). For the one problem that really needs a deque, the standard answer is an array used as a window of indices, which only ever pushes and pops at the ends you can afford.

Sliding window maximum: the deque problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// For every window of k, report the maximum. The naive answer is O(n*k).
// A deque of indices, kept in decreasing order of value, makes it O(n).
function maxSlidingWindow(nums, k) {
  const out = [];
  const deque = [];    // indices; nums[deque] is strictly decreasing

  for (let i = 0; i < nums.length; i++) {
    // 1. Drop indices that have fallen out of the window on the left.
    while (deque.length > 0 && deque[0] <= i - k) deque.shift();

    // 2. Drop indices whose value is smaller than the incoming one: they can
    //    never be the maximum again, because this one is bigger and newer.
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();

    deque.push(i);

    // 3. The front is the largest index in the window.
    if (i >= k - 1) out.push(nums[deque[0]]);
  }
  return out;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));   // [3,3,5,5,6,7]
console.log(maxSlidingWindow([1], 1));                          // [1]
console.log(maxSlidingWindow([9, 8, 7, 6], 2));                 // [9,8,7]
console.log(maxSlidingWindow([1, 2, 3, 4], 2));                 // [2,3,4]

Output

The same idea with a head pointer, strictly O(1) per operation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function maxSlidingWindowStrict(nums, k) {
  const out = [];
  const dq = [];
  let front = 0;                       // index into dq, replaces shift()

  for (let i = 0; i < nums.length; i++) {
    while (front < dq.length && dq[front] <= i - k) front++;
    while (front < dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[front]]);
  }
  return out;
}

console.log(maxSlidingWindowStrict([1, 3, -1, -3, 5, 3, 6, 7], 3));
console.log(maxSlidingWindowStrict([4, 3, 2, 1], 2));

Output

Monotonic deque, monotonic stack: the same family

Lesson 09's monotonic stack answered "what is the next greater element?". This deque answers "what is the maximum in the current window?". Both work by throwing away elements that can never be the answer again. Recognising that shared idea is more useful than memorising both.

Minimum in a window: the same code with one comparison flipped

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function minSlidingWindow(nums, k) {
  const out = [], dq = [];
  let front = 0;
  for (let i = 0; i < nums.length; i++) {
    while (front < dq.length && dq[front] <= i - k) front++;
    // >= becomes <= : keep the deque INCREASING instead of decreasing
    while (front < dq.length && nums[dq[dq.length - 1]] >= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[front]]);
  }
  return out;
}

console.log('max:', maxSlidingWindowInline([1, 3, -1, -3, 5, 3, 6, 7], 3));
console.log('min:', minSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));

function maxSlidingWindowInline(nums, k) {
  const out = [], dq = [];
  let front = 0;
  for (let i = 0; i < nums.length; i++) {
    while (front < dq.length && dq[front] <= i - k) front++;
    while (front < dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[front]]);
  }
  return out;
}

Output

A circular buffer, briefly

Sometimes you are asked for a queue with a fixed capacity that reuses its slots. The arithmetic is (index + 1) % capacity, and it appears in "design a circular queue" style questions.

Fixed-capacity circular queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class CircularQueue {
  #buf; #head = 0; #count = 0;

  constructor(capacity) { this.#buf = new Array(capacity).fill(null); }

  get size() { return this.#count; }
  get isFull() { return this.#count === this.#buf.length; }

  enqueue(x) {
    if (this.isFull) return false;
    const tail = (this.#head + this.#count) % this.#buf.length;   // wrap around
    this.#buf[tail] = x;
    this.#count++;
    return true;
  }

  dequeue() {
    if (this.#count === 0) return undefined;
    const x = this.#buf[this.#head];
    this.#buf[this.#head] = null;
    this.#head = (this.#head + 1) % this.#buf.length;
    this.#count--;
    return x;
  }

  toArray() {
    const out = [];
    for (let i = 0; i < this.#count; i++) out.push(this.#buf[(this.#head + i) % this.#buf.length]);
    return out;
  }
}

const cq = new CircularQueue(3);
console.log([cq.enqueue(1), cq.enqueue(2), cq.enqueue(3), cq.enqueue(4)]);   // last is false
console.log('contents:', cq.toArray(), '| full?', cq.isFull);
console.log('dequeue:', cq.dequeue(), '→', cq.toArray());
cq.enqueue(4);                       // reuses the slot that was freed
console.log('after wrapping:', cq.toArray());

Output

Your turn: three queue problems

rottingOranges(grid) — 2 is rotten, 1 is fresh, 0 is empty. Each minute, rot spreads to adjacent fresh oranges. Return the minutes until none are fresh, or -1. This is a multi-source BFS: start with every rotten cell in the queue and count levels.
openLock(deadends, target) — a 4-wheel lock starting at '0000'; each move turns one wheel one notch. Fewest moves to reach the target, avoiding deadends. BFS over strings.
MovingAverage(size) — a class with next(value) returning the average of the last size values. A fixed window with a running sum.

Editable. Fill them in, then run.

function rottingOranges(grid) {
  // seed the queue with all 2s, count fresh, then BFS level by level
}

function openLock(deadends, target) {
  // BFS from '0000'; neighbours turn one wheel up or down with wraparound
}

class MovingAverage {
  constructor(size) {
    // keep a queue and a running sum
  }
  next(value) {
    // your code
  }
}

console.log(rottingOranges([[2,1,1],[1,1,0],[0,1,1]]));      // 4
console.log(rottingOranges([[2,1,1],[0,1,1],[1,0,1]]));      // -1
console.log(rottingOranges([[0,2]]));                         // 0
console.log(openLock(['0201','0101','0102','1212','2002'], '0202'));   // 6
console.log(openLock(['8888'], '0009'));                                // 1
const m = new MovingAverage(3);
console.log([m.next(1), m.next(10), m.next(3), m.next(5)]);    // [1, 5.5, 4.666..., 6]

Output

Recap

A queue is first in, first out, and you need one for breadth-first search.
Never build a queue with shift: keep a head index and read queue[head++], which is O(1).
Mark nodes visited when you enqueue them, not when you dequeue them.
Freeze the queue size at the start of each round to process one level at a time; the level number is the distance.
A monotonic deque gives the window maximum in O(n) by discarding elements that can never win again, which is the same idea as a monotonic stack.

The trap first

The queue you should actually write

Level-by-level processing

Deques: both ends

Monotonic deque, monotonic stack: the same family

A circular buffer, briefly

Your turn: three queue problems

Recap

New writing, when it lands.