Stacks and Queues

A stack and a queue hold the same things and offer the same two operations: put something in, take something out.

They differ in which thing comes back out.

stack.push('a'); stack.push('b');  stack.pop()    // 'b' — the newest
queue.push('a'); queue.push('b');  queue.shift()  // 'a' — the oldest

A stack is a pile of plates: the last one you put down is the first one you pick up. A queue is a line at a shop: first in, first served.

One line changes the whole algorithm

Here is why this matters more than it looks. Take a traversal that explores a tree, and change nothing except the container:

function explore(start: Node, frontier: Frontier) {
  frontier.add(start);
  while (!frontier.isEmpty()) {
    const node = frontier.take();     // stack or queue — the only difference
    visit(node);
    for (const child of node.children) frontier.add(child);
  }
}

Flip between them and watch the numbers on the nodes — they show the order each one gets visited:

That is also why breadth-first finds shortest paths and depth-first does not. A queue visits everything one step away before anything two steps away, so the first time you reach a node is by the shortest route. A stack offers no such promise — it might reach the same node by a long wander.

The stack is easy; the queue is the interesting one

A stack is just a growable array. Push adds to the end, pop removes from the end. Both touch only the last slot, so both are $O(1)$.

A queue is not, and this catches people:

Two standard fixes.

A circular buffer keeps two indices, head and tail, and wraps them round using modulo. Nothing ever moves; only the indices change.

Or hold two stacks. Push onto the in-stack; pop from the out-stack; when the out-stack empties, tip the in-stack into it:

function dequeue(): T | undefined {
  if (out.length === 0) {
    while (inbox.length > 0) out.push(inbox.pop()!);   // reverses the order
  }
  return out.pop();
}

That while looks expensive, and each element only moves between the stacks once in its lifetime. Spread over all the dequeues, the average cost is $O(1)$ — even though one particular call can be $O(n)$.

Where each shows up

Stacks — whenever the most recent unfinished thing is the one to finish first. Matching brackets, undo history, the call stack your program already runs on, and the monotonic stack, which adds one rule about what may stay on the stack and turns a quadratic scan into one pass.

Queues — whenever arrival order or fairness matters. Job scheduling, buffering between a fast producer and a slow consumer, printer spools, and breadth-first search.