Stacks and Queues

TL;DR: A stack is LIFO (push/pop at one end), a queue is FIFO (enqueue at the back, dequeue from the front). The patterns worth memorizing: a monotonic stack solves next-greater-element and stock-span in one O(n) pass, a queue drives breadth-first traversal level by level, and a deque (or two stacks) gives you both ends in O(1). The interview skill is recognizing the shape: nested/matching structure means stack (brackets, undo, recursion), shortest-hops or level order means queue.

LIFO and FIFO, and why the shape matters

A stack matches anything nested or last-touched-first: balanced brackets, the call stack itself, undo history, depth-first search. A queue matches anything processed in arrival order or by distance: a print spooler, a task buffer, breadth-first search where you want the nearest nodes first. Both are O(1) for their core push and pop operations, so the choice is never about speed; it is about which order the problem demands.

Bracket matching is the canonical stack tell. Scan left to right, push every opener, and on a closer pop and check it matches. If the stack is empty when you need to pop, or non-empty at the end, the string is unbalanced.

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

The monotonic stack

This is the pattern that separates people who memorized "stack = LIFO" from people who can use it. A monotonic stack keeps its elements in sorted order (increasing or decreasing) by popping anything that violates the order before pushing. It answers "for each element, what is the next element greater than it?" in a single O(n) pass instead of the obvious O(n^2) double loop.

The trick: store indices, and when the current value is greater than the value at the top-of-stack index, you have just found the next-greater element for that popped index.

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []  # holds indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

Worked example on [2, 1, 5, 3]. Push index 0 (val 2). Index 1 (val 1) is smaller, push it. Index 2 (val 5) is bigger than 1 and 2, so pop both and set their answers to 5, push 2. Index 3 (val 3) is smaller than 5, push it. Result: [5, 5, -1, -1]. Each index is pushed and popped at most once, so it is O(n) despite the inner while. The stock-span and "daily temperatures" problems are the same pattern with the comparison flipped.

Queues drive BFS

Breadth-first search visits nodes in order of distance from the start, which is exactly FIFO behavior: process the current frontier, enqueue its neighbors, repeat. That ordering is what makes BFS find shortest paths in unweighted graphs. Track the queue size at the start of each round to process one level at a time.

from collections import deque

def bfs_levels(root):
    if not root: return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):       # snapshot this level's size
            node = q.popleft()
            level.append(node.val)
            q.extend(c for c in (node.left, node.right) if c)
        out.append(level)
    return out

Use collections.deque, not a Python list, for the queue. Popping from the front of a list is O(n) because every other element shifts; deque.popleft() is O(1).

Building one from the other

Two stacks make a queue: push onto an in stack; to dequeue, if the out stack is empty, pour everything from in into out (which reverses the order), then pop from out. Each element moves at most twice, so dequeue is O(1) amortized. A single deque gives you both stack and queue behavior directly with O(1) operations at both ends, which is why it is the default container for these problems in practice.

Why interviewers probe this

Stacks and queues are a recognition test wearing a data-structure costume. The interviewer wants to see you name the pattern fast: nested or matching means stack, level-order or shortest-unweighted-path means queue, "next greater/smaller" means monotonic stack. The strong-answer move is to spot the monotonic-stack opportunity and explain why it is O(n) (amortized: each element pushed and popped once) rather than the O(n^2) brute force. The held-back follow-up is often "prove the amortized bound" or "now do it streaming, where you cannot see future elements."

Common misconceptions

• "A monotonic stack is O(n^2) because of the inner while loop." Each element is pushed and popped at most once across the whole run, so total work is O(n). The inner loop's cost is amortized.
• "Use a Python list as a queue." list.pop(0) is O(n). Use collections.deque for O(1) front removal.
• "BFS and DFS find the same paths." Only BFS guarantees the shortest path in an unweighted graph, because it expands by distance. DFS can find a longer path first.
• "Stacks are only the call stack." Any nesting, undo, or matching problem is a stack: expression parsing, bracket validation, backtracking state.

Key takeaways

• Stack for nested/matching/undo (LIFO); queue for level-order and shortest unweighted paths (FIFO).
• The monotonic stack solves next-greater and span problems in one O(n) pass by storing indices.
• BFS uses a queue and snapshots the frontier size to process level by level; use deque, not a list.
• Two stacks emulate a queue in O(1) amortized; a deque gives both ends in O(1) and is the practical default.