Stacks & Queues

Two of the most useful shapes in programming are the same underlying idea with different rules about which end you touch. A stack is LIFO: last in, first out. A queue is FIFO: first in, first out. Picking the wrong one is a common bug; knowing when to reach for which is one of those small skills that separates "it works" from "it works cleanly."

Analogy

A stack is a pile of plates. You add to the top; you take from the top. The plate at the bottom was the first one you put down, and it'll be the last one you pick up. If you tried to pull from the middle, the whole stack topples.

A queue is the line at a coffee shop. You join at the back; you're served from the front. The person who arrived first is served first; the person who just walked in waits the longest.

Both structures track the same collection of items; the difference is which end they let you touch. That's it. Everything else — the algorithms, the data-structure choices, the real-world examples — falls out of that single rule.

Where stacks show up in real code

• The function call stack. Every time you call a function, a new frame is pushed on the stack; when it returns, the frame is popped. Stack overflows are literally "we ran out of room to push more frames" — usually because of unbounded recursion.
• Undo history. Text editors, drawing apps, shells. Every action is pushed; "undo" pops the most recent one. "Redo" is a second stack for popped-then-reapplied actions.
• Depth-first search (DFS). DFS's "frontier" is a stack: when you visit a node, you push its unexplored neighbours; you always pop the most recently pushed one, so you go as deep as possible before backtracking.
• Expression evaluation. Parsing 3 + 4 * (2 - 1) uses a stack to hold operators while operands are reduced. The shunting-yard algorithm is almost pure stack plumbing.
• Balanced delimiters. The canonical stack problem — is ({[]}) balanced? Push every open bracket; on every close, pop and check the pair matches. Any mismatch (or pop-on-empty) is an immediate "no." Clean stack ends — "yes."

Where queues show up in real code

• Breadth-first search (BFS). BFS's frontier is a queue: when you visit a node, you enqueue its neighbours; you always dequeue the oldest one, so you explore level-by-level.
• Task queues. Background jobs — image resizing, email dispatch, webhook delivery — land in a queue so a pool of workers can drain them in order. Redis, RabbitMQ, SQS, Kafka partitions: they're all variations on the same "enq here, deq there" shape.
• Message brokers. "At-least-once delivery", "at-most-once delivery", "exactly-once with idempotency" — the guarantees rest on a queue abstraction under the hood.
• OS process scheduling. Runnable processes sit in a ready queue; the scheduler pops one, runs it for a time slice, and either re-enqueues it or puts it on a blocked queue.
• Event loops. Node.js, browsers, Python asyncio — every pending task goes into a queue and the loop dequeues and runs them one at a time.

Array-backed vs linked-backed: the tradeoff

Both stacks and queues can be implemented two ways:

• Array-backed. A resizeable array (dynamic array). Fast random access; O(1) amortised push/pop at the end. Removing from the front is O(n) because every element has to shift left.
• Linked-backed. A linked list with head+tail pointers. O(1) at either end; no shifting. Costs a bit more memory per element (the pointers) and pays for cache unfriendliness because nodes are scattered in memory.

For a stack, array-backed is almost always the right choice — you only ever touch one end, so the "remove from front is O(n)" problem never comes up. Cache locality gives you a speed win.

For a queue, array-backed works if you use a circular buffer (reuse slots as the head advances) or a deque (double-ended queue) that keeps both ends O(1). A naive array.shift() "queue" runs quadratically under load — a classic perf trap.

Real standard-library examples

Language	Stack	Queue
JavaScript	Array.push / Array.pop	Use a deque-like structure — Array.shift is O(n)
Python	list.append / list.pop	collections.deque (O(1) both ends)
Java	Deque via ArrayDeque	Deque via ArrayDeque, or LinkedList
C++	std::stack (adaptor)	std::queue or std::deque
Go	Idiomatic: slice with append/slice	container/list or slice-based ring
Rust	Vec::push / Vec::pop	VecDeque

Note that Stack and Queue in most languages are adaptors over a general-purpose container (deque, ArrayDeque, etc.) — the abstract operations are deliberately restricted to LIFO or FIFO semantics, but the underlying storage is shared.

The balanced-parens problem — the canonical stack teaching example

function isBalanced(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };
  for (const ch of s) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (")]}".includes(ch)) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Why it's such a clean teaching example:

• It's obviously LIFO. The most recent open bracket is the one that has to match the next close; that's the stack discipline in one sentence.
• Both failure modes matter. You can fail mid-string with a mismatch ("(]") or at the end with unclosed opens ("(("). The algorithm naturally distinguishes them.
• It generalises. Real parsers — HTML, JSON, programming languages — use exactly the same stack pattern, just with richer "bracket" sets.

Gotchas

• pop() on an empty stack. Most languages return undefined / None rather than throw. Treat that as a failure mode in your validation — don't silently treat an empty-stack pop as "matched everything."
• shift() on a JS array is O(n). If you're processing a high-throughput queue with array.shift(), you're accidentally quadratic. Either switch to an index-pointer pattern (advance a "head" counter instead of actually removing) or use a proper deque.
• Stack overflow from unbounded recursion. If you're recursing on a data structure whose depth scales with input, you'll eventually blow the call stack. The fix is almost always "convert to iterative with an explicit stack" — which is exactly the transformation this lesson is about.
• FIFO vs LIFO semantics matter. A task queue that accidentally behaves like a stack is a classic production bug: new tasks pile up on top, old tasks starve. Check the semantics before you reach for any "Stack" or "Queue" class.

Playground

Two sub-modes on the playground tab.

Balanced parens lets you type a bracket string, press Play, and watch the stack grow and shrink one character at a time. Balanced strings end with an empty stack and a green "yes"; unbalanced strings either break mid-scan (the mismatching character is highlighted) or end with leftover opens still on the stack.

Queue ops lets you type a comma-separated op list (enq:a, enq:b, deq, enq:c). Each enq pushes to the right side of the queue; each deq pulls from the left. Scrub through the steps to watch the queue churn.

Visualizer

The Stack & Queue Animator panel runs a short canned scenario side-by-side: a stack being built from (()) and a queue being churned by a small op list. The stack grows upward (push-on-top); the queue grows rightward (enqueue-on-right, dequeue-on-left). It's the single picture to carry out of this level — the shapes are distinct, but the mechanism is the same.