Level 1 · 25 min

Stacks & Queues: When LIFO/FIFO Saves Recursion

Stacks and queues are the simplest data structures with the deepest applications: every recursive algorithm has an iterative form using an explicit stack, and every BFS-style traversal hides a queue. CLRS chapter 10 introduces them; Cracking the Coding Interview chapter 3 builds the intuition.

Stack: LIFO and Recursion Replacement

A stack supports push, pop, peek in O(1). It is the abstract machine of any recursive algorithm: each recursion frame pushes locals; return pops. To convert recursion to iteration: simulate the call stack with an explicit Deque. Java: use ArrayDeque (push/pop), not the legacy Stack class which is synchronized and slower. Why convert? Recursion blows the JVM stack at ~10K-50K frames (depending on -Xss); an explicit ArrayDeque scales to millions of entries on the heap. Classic conversions: iterative DFS, iterative postorder traversal, iterative quicksort partition. CTCI ch. 3 problem 3.5 ''sort stack'' uses two stacks to implement an in-place sort — pure stack manipulation, no other structures.

Queue: FIFO and BFS

A queue supports enqueue (offer) and dequeue (poll) in O(1). Java: ArrayDeque again — implements both Stack and Queue interfaces with circular-buffer semantics, no synchronization overhead. LinkedList also implements Queue but loses cache locality. Critical use case: BFS on graphs and level-order traversal of trees. The queue holds the ''frontier'' — nodes seen but not yet expanded. The shape of BFS''s memory: at any moment the queue contains at most one full level of the tree, so memory is O(width). For binary trees, width can equal n/2 at the bottom level, so worst-case BFS memory is O(n). DFS memory is O(height), O(log n) for balanced trees, O(n) for skewed.

Monotonic Stacks and Deques

A monotonic stack maintains its elements in sorted order — pop anything that violates the invariant before pushing. Use case: ''next greater element'' for every position in O(n). Walk the array, maintain a stack of indices whose values are in decreasing order. When you see a new value greater than top-of-stack, pop and record the answer. Each index pushes and pops at most once, so amortized O(n). Monotonic deque (double-ended) solves ''sliding window maximum'' in O(n): maintain a deque of decreasing values, pop the back when a new larger value arrives, pop the front when it falls out of the window. Both are advanced patterns from CTCI/CLRS that reliably appear in interview rounds and in real production code (e.g. CDN time-series compression).

Key Takeaways

Use ArrayDeque for both stack and queue in Java. Avoid the legacy Stack/LinkedList classes.
Convert deep recursion to iteration with an explicit stack to avoid StackOverflowError at large input sizes.
Monotonic stack/deque solves next-greater-element and sliding-window-max in O(n) — recognize the pattern.

Code example

// Java — iterative DFS with explicit stack (avoids StackOverflowError)
static List<Integer> dfsIterative(TreeNode root) {
  List<Integer> result = new ArrayList<'>();
  if (root == null) return result;
  Deque<TreeNode> stack = new ArrayDeque<'>();
  stack.push(root);
  while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    result.add(node.val);
    if (node.right != null) stack.push(node.right); // right first → left popped first
    if (node.left != null)  stack.push(node.left);
  }
  return result;
}

// Monotonic stack — next greater element for each index
static int[] nextGreater(int[] a) {
  int n = a.length;
  int[] result = new int[n];
  Arrays.fill(result, -1);
  Deque<Integer> stack = new ArrayDeque<'>(); // indices, values decreasing
  for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() '&'&' a[stack.peek()] < a[i]) {
      result[stack.pop()] = a[i];
    }
    stack.push(i);
  }
  return result;
}