Stacks and queues

A discipline, not a structure

A stack and a queue are not containers so much as restrictions. Both hold items; the point is which one you are allowed to take out. That restriction is what makes the code using them simple, and what makes the implementation fast.

Stack — last in, first out. The most recent thing is the next thing. Queue — first in, first out. The oldest thing is the next thing.

A stack is an array you only touch at one end

That is the whole implementation, and it is optimal: both operations are at the cheap end of the array. You will meet stacks whether you build one or not — the call stack, undo history, the back button, matching brackets, and depth-first search in the graph lessons.

Every recursive algorithm is a loop plus a stack, which is why "convert this recursion to iteration" always means "make the stack explicit".

const stack = [];
stack.push(x);         // O(1)
stack.pop();           // O(1)
stack[stack.length - 1];   // peek, without removing

The queue trap

shift is the same word as pop in most people’s heads and costs n times more. A breadth-first search over a million nodes, written with shift, is doing half a trillion moves — and it will look like the algorithm is wrong rather than the container.

const queue = [];
queue.push(x);         // O(1)  — fine
queue.shift();         // O(n)  — every remaining item slides down one

Two ends, one array: the ring buffer

Nothing slides. The head index walks forwards and the array is compacted only when more than half of it is dead — which, amortised over n operations, costs O(1) each, by exactly the argument that made push free.

A true ring buffer goes further: a fixed-size array with head and tail indices that wrap around with % capacity, so nothing is ever allocated or copied. That is what an audio buffer, a network socket and a "last 100 log lines" all use.

class Queue {
  #items = [];
  #head = 0;                       // where the front currently is

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

  dequeue() {
    if (this.#head >= this.#items.length) return undefined;
    const x = this.#items[this.#head];
    this.#items[this.#head++] = undefined;    // let it be collected
    if (this.#head > 32 && this.#head * 2 > this.#items.length) {
      this.#items = this.#items.slice(this.#head);   // compact, rarely
      this.#head = 0;
    }
    return x;
  }

  get size() { return this.#items.length - this.#head; }
}

The variations worth knowing

A deque is a queue with both ends open: Python has collections.deque, and in JavaScript the same index-walking trick gives you one. It is the structure behind the sliding-window maximum, which turns an O(n·k) scan into O(n).