Stacks, Queues & Deques

Matching and nesting, expression evaluation, queues and the monotonic deque.

A stack is the right tool whenever the most recent unfinished thing must be handled first: matching brackets, nested structures, undo, and evaluating expressions. A queue handles things in arrival order: BFS, scheduling, and recent-event windows. A deque does both, and its monotonic form gives O(n) sliding-window maximums.

For "next greater element" problems, see Monotonic Stack.

In Python

Matching and nesting

Push openers. On a closer, the top of the stack must be its partner.

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

For nested decoding like 3[a2[c]], push the current state (the string built so far and the repeat count) when you see [, and pop it to combine when you see ].

def decode_string(s):
    stack, cur, num = [], "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append((cur, num))
            cur, num = "", 0
        elif ch == "]":
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

Evaluating expressions

Reverse Polish notation is the simplest case: push numbers, and on an operator pop two operands and push the result.

Infix with precedence (3+2*2, no parentheses): keep a stack of terms. Push +n and -n as they are, but apply * and / straight away to the top of the stack. The answer is the sum of the stack.

def calculate(s):
    stack, num, op = [], 0, "+"
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in "+-*/" or i == len(s) - 1:
            if op == "+":   stack.append(num)
            elif op == "-": stack.append(-num)
            elif op == "*": stack.append(stack.pop() * num)
            else:           stack.append(int(stack.pop() / num))  # truncate toward 0
            op, num = ch, 0
    return sum(stack)

With parentheses, push the running result and sign when you see (, and combine them when you see ). Or recurse on the inner expression.

Simulation with a stack

Asteroid collision: the stack holds survivors. A left-moving asteroid fights the right-moving ones on top of the stack.
Simplify a path: split on /, push names, pop on .., ignore . and empty parts.
Exclusive time of functions: the stack holds the running function IDs. Charge the elapsed time to whichever function is on top.

Designing a stack with extras

Min stack: store (value, min_so_far) pairs so get_min is O(1). Max frequency stack: keep a map of value → count and a map of count → stack of values.

Queues and deques

BFS: any shortest path in an unweighted graph or grid. See BFS & DFS.
Recent-event windows: append timestamps and pop from the front while they're too old. This covers "hit counter" and "recent calls" problems.
Circular queue: a fixed array with head and size indexes, using modulo arithmetic.
Queue from two stacks: push onto in. To pop, refill out from in only when out is empty. Each element moves at most once, so operations are amortized O(1).

Monotonic deque: sliding window maximum

Keep the indexes in the deque with their values decreasing. A new value removes every smaller value from the back, because those values can never be the maximum again. The front is always the maximum of the current window.

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:            # front fell out of the window
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

The same structure handles "longest subarray where max − min ≤ limit" (one deque for the maximum, one for the minimum) and "shortest subarray with sum ≥ k" with negative numbers (a monotonic deque over prefix sums).

[!TIP] Practice Valid Parentheses · Min Stack · Evaluate RPN · Decode String · Basic Calculator II · Asteroid Collision · Sliding Window Maximum · Design Hit Counter · Implement Queue Using Stacks