Stacks, Queues and Monotonic Structures

A stack gives you the most recent unfinished thing. A queue gives you the oldest. Those two orderings, last in first out and first in first out, model a surprising amount of problem structure: matching brackets, undoing work, evaluating expressions, processing in arrival order, and breadth-first search. The most valuable idea in this chapter is the monotonic stack, which turns many "next greater element" problems from quadratic to linear.

1. When this pattern applies

Stack signals:

• Things must be matched or nested (brackets, tags, parentheses).
• You need to undo or backtrack to the most recent state.
• You evaluate expressions or process nested structure.
• For each element you need the nearest earlier or later element that is greater or smaller. (Monotonic stack.)
• You want to simulate recursion iteratively.

Queue signals:

• Process items in arrival order.
• Breadth-first exploration, level by level.
• A sliding window where you need the maximum or minimum (monotonic deque).

2. The tools in Python

from collections import deque

stack = []                 # a list is a stack: append and pop from the end are O(1)
stack.append(1); stack.append(2)
assert stack.pop() == 2 and stack[-1] == 1     # stack[-1] peeks at the top

queue = deque()            # use deque, never list.pop(0), which is O(n)
queue.append(1); queue.append(2)
assert queue.popleft() == 1 and queue[0] == 2

3. Matching and nesting

Valid parentheses. Push openers, and when a closer arrives it must match the most recent unmatched opener.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:                              # a closer
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:                                        # an opener
            stack.append(ch)
    return not stack                                 # nothing left unmatched

assert is_valid("()[]{}") is True
assert is_valid("([)]") is False
assert is_valid("((") is False
assert is_valid("") is True

Time $O(n)$, space $O(n)$. The two failure cases are worth naming: a closer with no matching opener, and openers left over at the end.

Evaluate reverse Polish notation. Operands are pushed, and each operator pops two operands and pushes the result. Mind the order for subtraction and division: the first popped is the right operand.

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in {"+", "-", "*", "/"}:
            b, a = stack.pop(), stack.pop()          # b is the right operand
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))           # truncate toward zero
        else:
            stack.append(int(t))
    return stack[0]

assert eval_rpn(["2", "1", "+", "3", "*"]) == 9
assert eval_rpn(["4", "13", "5", "/", "+"]) == 6
assert eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22

Decode string (3[a2[c]] becomes accaccacc) uses a stack of (count, text so far) pairs:

def decode_string(s):
    stack = []                   # (text before the bracket, repeat count)
    current, count = "", 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)
        elif ch == "[":
            stack.append((current, count))
            current, count = "", 0
        elif ch == "]":
            prev, repeat = stack.pop()
            current = prev + current * repeat
        else:
            current += ch
    return current

assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"

4. A stack that remembers more: min stack

Design a stack that supports push, pop, top and minimum in $O(1)$. Store, with each element, the minimum so far.

class MinStack:
    def __init__(self):
        self.stack = []                  # (value, minimum of everything at or below)

    def push(self, x):
        current_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, current_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

m = MinStack()
for v in [5, 3, 7, 3]:
    m.push(v)
assert m.get_min() == 3
m.pop(); m.pop()
assert m.get_min() == 3 and m.top() == 3
m.pop()
assert m.get_min() == 5

This shows the general trick: augment each stack entry with the aggregate you need, so that popping restores the previous aggregate automatically.

5. The monotonic stack

A monotonic stack keeps its elements in sorted order (increasing or decreasing). Whenever a new element would violate the order, you pop elements until it fits. The pops are exactly the moments when an element finds its "next greater" (or "next smaller") neighbour.

Daily temperatures. For each day, how many days until a warmer one? Keep a stack of indexes of days still waiting for a warmer day, with temperatures decreasing from bottom to top. A new, warmer day resolves every waiting day colder than it.

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                                   # indexes of days waiting, temps decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:    # today is warmer than the day on top
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

assert daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert daily_temperatures([30, 60, 90]) == [1, 1, 0]

Time $O(n)$: every index is pushed once and popped at most once, even though there is a while inside the for. Space $O(n)$.

Next greater element in a circular array works the same way, iterating over the array twice:

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):                       # go around twice
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        if i < n:
            stack.append(i)
    return result

assert next_greater_circular([1, 2, 1]) == [2, -1, 2]
assert next_greater_circular([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]

Largest rectangle in a histogram. For each bar, the widest rectangle using it as the height extends left and right until a shorter bar. A stack of increasing heights finds both limits: when a shorter bar arrives, the bars it pops have found their right limit, and the new top of the stack is their left limit.

def largest_rectangle(heights):
    stack = []                       # indexes, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):        # a sentinel 0 flushes the stack
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1    # first shorter bar on the left
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

assert largest_rectangle([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle([2, 4]) == 4
assert largest_rectangle([]) == 0

This is a hard problem, and the stack idea is the same as in the temperatures problem. The same technique solves maximal rectangle in a binary matrix (apply it row by row) and underlies trapping rain water in its stack form.

6. Queues and monotonic deques

Queue using two stacks. Push onto an input stack. When asked to pop, if the output stack is empty, move everything from the input to the output, which reverses the order. Each element moves at most once, so operations are $O(1)$ amortised.

class QueueFromStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

q = QueueFromStacks()
for v in [1, 2, 3]:
    q.push(v)
assert q.pop() == 1
q.push(4)
assert [q.pop(), q.pop(), q.pop()] == [2, 3, 4]

Sliding window maximum. For every window of size $k$, report the maximum. A monotonic deque keeps indexes of candidates with decreasing values: the front is the current maximum, smaller values behind a larger newcomer can never be the maximum again, so they are discarded. Expire the front when it leaves the window.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                 # indexes, values decreasing from front to back
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:          # smaller values behind x are useless
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                        # front fell out of the window
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9, 11], 2) == [11]

Time $O(n)$, since each index enters and leaves the deque once. A heap would give $O(n\log n)$. The deque version is the answer interviewers want.

7. Stack as explicit recursion

Recursion uses the call stack. When recursion depth could be large (Python's default limit is about 1,000 frames), or when you must avoid recursion, simulate it with your own stack.

def inorder_iterative(root_children):
    """Iterative inorder on a tuple-tree: node = (value, left, right) or None."""
    result, stack, node = [], [], root_children
    while node or stack:
        while node:                       # go as far left as possible
            stack.append(node)
            node = node[1]
        node = stack.pop()
        result.append(node[0])
        node = node[2]                    # then visit the right subtree
    return result

tree = (4, (2, (1, None, None), (3, None, None)), (6, (5, None, None), (7, None, None)))
assert inorder_iterative(tree) == [1, 2, 3, 4, 5, 6, 7]

The tree chapter covers this pattern in detail.

8. Recognising monotonic-stack problems

Ask: "For each element, do I need the nearest element to its left or right that is greater (or smaller)?" If yes, a monotonic stack is almost always the answer. Typical statements:

• Next greater element, next warmer day.
• Stock span: how many consecutive previous days had a price at most today's.
• Largest rectangle in a histogram.
• Sum of subarray minimums (each element contributes as the minimum over a range found by its previous and next smaller elements).
• Remove $k$ digits to make the smallest number (a greedy stack).
• Trapping rain water.

Choose the direction of monotonicity by what you pop. To find next greater, keep the stack decreasing (pop when a larger element arrives). To find next smaller, keep it increasing.

9. Common mistakes

• Using list.pop(0) as a queue. It is $O(n)$, turning BFS quadratic. Use deque.
• Popping from an empty stack. Guard with if stack or a sentinel.
• Storing values instead of indexes in a monotonic stack, when you need distances or positions.
• Wrong operand order for non-commutative operators in expression evaluation.
• Forgetting to flush the stack at the end (use a sentinel).
• Strict versus non-strict comparison in a monotonic stack (< versus <=), which changes how equal elements are treated. Decide what the problem requires for ties.
• Python integer division differs for negative numbers: use int(a / b) to truncate toward zero when the problem asks for it.

10. Practice set

1. Valid parentheses, minimum add to make parentheses valid, longest valid parentheses.
2. Min stack, then max stack, then stack with increment.
3. Evaluate reverse Polish notation, basic calculator (with parentheses).
4. Daily temperatures, next greater element I and II, stock span.
5. Largest rectangle in histogram, maximal rectangle.
6. Remove $k$ digits, remove duplicate letters.
7. Sliding window maximum.
8. Implement queue using stacks, implement stack using queues.
9. Asteroid collision (a stack simulation).
10. Sum of subarray minimums.