Stacks & Queues

Two access disciplines

A stack (LIFO) lets you touch only the most-recently-added item; a queue (FIFO) serves in arrival order. Both give O(1) insert/remove. The whole skill is recognizing which discipline a problem secretly wants — “resolve the most recent first” → stack; “process in order” → queue.

Stacks: last in, first out

Use a stack whenever the most recently opened thing must be resolved first — matching brackets, undo, the call stack, backtracking, and iterative DFS.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pairs:                       # closing
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)                  # opening
    return not stack

Implemented on a dynamic array (list.append/pop) — both amortized O(1).

Queues: first in, first out

A queue is the natural fit for BFS and level-order traversal. Use collections.deque for O(1) pops from the front (a plain list.pop(0) is O(n)):

from collections import deque
q = deque([root])
while q:
    node = q.popleft()                       # O(1)
    for child in node.children:
        q.append(child)

A circular buffer (ring) implements a fixed-size queue in an array with head/tail indices — the “Design Circular Queue” problem.

Deque: both ends, and the sliding-window maximum

A double-ended queue supports O(1) push/pop at both ends. Its signature use is the monotonic deque for sliding-window maximum — keep indices of a decreasing window so the front is always the current max:

def max_sliding_window(nums, k):
    dq, out = deque(), []                    # dq holds indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x: dq.pop()      # pop smaller from the back
        dq.append(i)
        if dq[0] == i - k: dq.popleft()              # drop the out-of-window front
        if i >= k - 1: out.append(nums[dq[0]])       # front is the window max
    return out

O(n): each index is pushed and popped once.

The monotonic stack (a whole problem class)

A monotonic stack keeps elements sorted as you push, popping violators. It answers “next/previous greater/smaller element” in O(n) total (each element pushed and popped once):

def daily_temperatures(temps):
    res = [0] * len(temps)
    stack = []                               # indices, temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j                   # i is the next-warmer day for j
        stack.append(i)
    return res

It also cracks largest rectangle in a histogram, trapping rain water, and stock span. Heuristic: if you’re scanning for the nearest larger/smaller value, it’s a monotonic stack.

Expression evaluation

Stacks evaluate and convert expressions:

• Postfix (RPN) eval — push numbers; on an operator, pop two and push the result.
• Infix → postfix — the shunting-yard algorithm uses an operator stack honoring precedence.
• Basic calculator — a stack handles parentheses and + − × ÷ with precedence.

Iterative DFS

Recursion uses the call stack; to avoid stack-overflow on deep inputs (or by request), make it explicit:

def dfs_iter(root):
    stack = [root]
    while stack:
        node = stack.pop()
        visit(node)
        stack.extend(reversed(node.children))   # push so leftmost is processed first

Classic designs to know

• Min stack — O(1) min() by keeping a parallel stack of running minimums.
• Queue via two stacks — in and out stacks; amortized O(1) (move when out empties).
• Stack via two queues — push/pop in O(n)/O(1) by rotating.

Common pitfalls

• list.pop(0) is O(n) — use deque.popleft() for a queue.
• Popping an empty stack — guard if stack.
• Storing indices vs values in a monotonic stack — usually store indices so you can compute distances.

Choosing in an interview

• Match/parse nested structure, undo, iterative DFS → stack.
• Process in order, BFS / level-order → queue (deque).
• Nearest greater/smaller element → monotonic stack.
• Window min/max in O(n) → monotonic deque.
• O(1) min, or a queue from stacks → the classic designs.