7 — Stacks and queues

A stack and a queue are both containers that only let you touch their ends. A stack adds and removes at the same end, so the most recently added item leaves first (last in, first out, LIFO). A queue adds at one end and removes at the other, so items leave in arrival order (first in, first out, FIFO). That restriction is the whole point. Because the structures promise so little, they can deliver every operation in O(1), and because the order of removal is fixed, an algorithm built on one of them inherits a precise invariant: a stack always hands back the most recent unfinished thing, and a queue always hands back the oldest.

Those two invariants drive a surprising amount of computing. Function calls, undo, bracket matching, expression evaluation, depth-first search and the monotonic-stack family of array problems all depend on “most recent first”. Breadth-first search, schedulers, buffers between producers and consumers, and every network card’s packet ring depend on “oldest first”.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ on other machines; the ratios and growth patterns are what matter.

The stack abstract data type

A stack supports:

Popping or peeking at an empty stack is an error. Different libraries signal it differently (an exception, a sentinel value, undefined behavior in C), and forgetting the empty case is the most common bug in stack code.

push 1, push 2, push 3          pop -> 3           push 4
                                                  
   | 3 |  <- top                                    | 4 |  <- top
   | 2 |                         | 2 |  <- top      | 2 |
   | 1 |                         | 1 |              | 1 |
   +---+                         +---+              +---+

Array-backed stacks

The natural implementation is a dynamic array with the top at the end. Push appends, pop removes the last element, and nothing else moves. In Python that is just a list:

stack = []
stack.append(1)        # push
stack.append(2)
top = stack[-1]        # peek
value = stack.pop()    # pop -> 2
if not stack: ...      # empty test

append is O(1) amortized rather than worst case: when the underlying array is full, CPython allocates a larger one and copies the pointers across. The growth is geometric (roughly 1.125 times plus a constant in CPython), so the total copying over n appends is O(n) and each append costs O(1) on average. The array growth argument is covered in Arrays. pop() from the end never copies. CPython does shrink a list’s allocation when it falls below half full, which is also amortized O(1).

The top must be at the end. Using insert(0, x) and pop(0) gives a correct stack with O(n) operations, because every other pointer shifts by one slot.

Linked stacks

A singly linked list with the top at the head also gives O(1) push and pop, and here the bound is worst case rather than amortized, since no operation ever copies:

class LinkedStack:
    __slots__ = ("_head", "_size")

    class _Node:
        __slots__ = ("value", "next")

        def __init__(self, value, next):
            self.value = value
            self.next = next

    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, value):
        self._head = self._Node(value, self._head)
        self._size += 1

    def pop(self):
        if self._head is None:
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        self._size -= 1
        return node.value

    def peek(self):
        if self._head is None:
            raise IndexError("peek at empty stack")
        return self._head.value

    def __len__(self):
        return self._size

The linked version pays for that guarantee with one allocation per push and an extra pointer per element. In Python it also pays interpreter overhead for every method call and attribute access. Pushing 200,000 integers and popping them all:

A list is the right stack in Python. The linked stack is worth knowing for two reasons: it is how stacks are often built in languages without a growable array, and the “push onto the head” idea is the basis of persistent (immutable) stacks, where several versions share their tails. In systems code, a linked stack also never needs a large contiguous reallocation, which matters for lock-free stacks and kernel free lists.

The queue abstract data type

A queue supports:

enqueue 1, 2, 3                dequeue -> 1          enqueue 4

front -> [1][2][3] <- back     front -> [2][3]       front -> [2][3][4]

The difficulty is that a queue changes both ends. A plain array with the front at index 0 makes dequeue O(n), because removing element 0 shifts everything left. There are three standard fixes: a linked list with head and tail pointers, a circular buffer, and a block-linked structure like collections.deque.

List versus deque, measured

list.pop(0) is the trap. It works, it is short, and it is O(n) per call, so draining a list from the front is O(n²) in total. The measurement drains n items from the front of a list and of a collections.deque, with list.pop() from the end as a baseline:

The per-item cost of pop(0) grows linearly with n, so the total grows quadratically. At 300,000 items pop(0) is about 940 times slower per removal than popleft(). At 1,000 items it is only 3.6 times slower, because memmove of a few kilobytes is fast. That is why the bug survives code review: it does not show up on small test data. A BFS over a million-node graph that uses queue.pop(0) will spend almost all its time shifting pointers.

The same trap exists with list.insert(0, x) and with slicing (queue = queue[1:] copies the whole list every time).

How collections.deque is built

CPython’s deque (in Modules/_collectionsmodule.c) is a doubly linked list of fixed-size blocks, each holding 64 object pointers (BLOCKLEN is 64). The deque keeps a pointer to the leftmost and rightmost block and an index into each:

 leftblock                                  rightblock
 +----------------------+    +----------------------+    +----------------------+
 | . . . . . a b c d e  | <->| f g h i j k l m n o  | <->| p q r s . . . . . .  |
 +----------------------+    +----------------------+    +----------------------+
             ^ leftindex                                         ^ rightindex

Appending on either side writes into the current end block, or links a fresh block when that one is full. Popping clears a slot and frees a block when it empties. Nothing else moves, and there is no realloc of a large array, so append, appendleft, pop and popleft are O(1) worst case (apart from the allocator). The source comments note the design choice: one pointer per element plus a small per-block overhead, instead of the two link pointers per element of a textbook doubly linked list, with better cache locality.

The consequences for users:

Use a deque whenever both ends change. Do not use it as an array you index into the middle of: d[len(d) // 2] is a walk, not an address calculation.

deque(maxlen=k) is a bounded buffer with automatic eviction: deque(f, maxlen=10) keeps the last ten lines of a file, which is how a tail is written in one line.

The documentation describes a deque’s appends and pops from either end as thread-safe, but a deque has no blocking get. For a queue between threads, use queue.Queue (blocking, with optional size bound and task_done/join) or queue.SimpleQueue (unbounded, no task tracking, implemented in C). For coroutines, use asyncio.Queue. Their cost is measurable, enqueueing and dequeueing 200,000 integers in one thread:

queue.Queue costs over 20 times as much as a deque because every operation takes a lock and manages condition variables. That is the right price when threads share it and the wrong price inside a single-threaded BFS. The hand-written Python classes lose to the C implementations purely on interpreter overhead; they are shown here for their ideas, not as replacements.

Circular buffers

A circular buffer (ring buffer) is a fixed array with a head index and a count. The back of the queue is (head + count) mod capacity. Both indices move forward and wrap around, so the occupied region slides around the ring instead of the data sliding through memory.

capacity 5, after enqueue a b c d, dequeue a b, enqueue e f

index:   0   1   2   3   4
       [ f ][ . ][ c ][ d ][ e ]
               ^    ^
             tail  head          head = 2, count = 4, tail = (2 + 4) % 5 = 1

The implementation, with the design decisions in comments:

class CircularQueue:
    """Fixed-capacity FIFO queue on a preallocated list (a ring buffer)."""

    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self._buf = [None] * capacity
        self._head = 0          # index of the front element
        self._size = 0

    def enqueue(self, value):
        if self._size == len(self._buf):
            raise OverflowError("queue is full")
        tail = (self._head + self._size) % len(self._buf)
        self._buf[tail] = value
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from empty queue")
        value = self._buf[self._head]
        self._buf[self._head] = None            # drop the reference
        self._head = (self._head + 1) % len(self._buf)
        self._size -= 1
        return value

    def front(self):
        if self._size == 0:
            raise IndexError("front of empty queue")
        return self._buf[self._head]

    def __len__(self):
        return self._size

Every operation is O(1) worst case and the buffer uses exactly capacity slots, with no allocation after construction. That predictability is why ring buffers are everywhere in systems code: audio pipelines, network interface descriptor rings, log buffers, the submission and completion queues of Linux io_uring, and the LMAX Disruptor in finance all use them.

Full versus empty

With only head and tail indices, head == tail means both “empty” and “full”. There are three standard fixes:

1. Keep a count, as above.
2. Leave one slot always unused, so full is (tail + 1) % capacity == head. This is common in lock-free single-producer single-consumer rings, because the producer writes only tail and the consumer writes only head, and neither needs a shared counter.
3. Let head and tail run as unbounded integers and take them modulo the capacity only when indexing. Then size is tail - head, full is size == capacity, and when the capacity is a power of two the modulo becomes a bit mask (i & (capacity - 1)). Many kernel ring buffers use this form.

Growable ring buffers

When the capacity must grow, copying the array as is would break the wrap-around: the elements from head to the end of the old array need to stay in order before those from index 0. The usual fix is to unroll the ring into a new array twice the size with the front at index 0:

def enqueue(self, value):
    if self._size == len(self._buf):
        n = len(self._buf)
        self._buf = ([self._buf[(self._head + i) % n] for i in range(n)]
                     + [None] * n)
        self._head = 0
    self._buf[(self._head + self._size) % len(self._buf)] = value
    self._size += 1

Doubling gives O(1) amortized enqueue by the same argument as a dynamic array. Java’s ArrayDeque and Rust’s VecDeque are growable ring buffers of this kind.

The overwrite policy

A bounded buffer must decide what happens when it is full. The choices are to reject the new item (as above), to block the producer until space appears (queue.Queue(maxsize=n)), or to overwrite the oldest item (deque(maxlen=n), most logging and metrics rings). Rejecting or blocking provides back-pressure, which keeps a slow consumer from being buried; overwriting keeps the most recent data and silently loses old data. The right choice depends on whether losing data or stalling the producer is worse.

Deques

A double-ended queue supports push and pop at both ends. It generalizes both structures: use one end only and it is a stack; push at one end and pop at the other and it is a queue. Its own uses are the ones that need both behaviors at once:

• Sliding window maximum and minimum (the monotonic deque, below): new items enter at the back, dominated items leave from the back, expired items leave from the front.
• 0-1 BFS: shortest paths when edge weights are 0 or 1. A weight-0 edge pushes the neighbor to the front, a weight-1 edge to the back, and the deque stays sorted by distance. See Graph algorithms.
• Work stealing: each worker thread pops tasks from its own end of its deque (LIFO, good for cache locality) while idle workers steal from the other end (FIFO, taking the oldest and usually largest tasks). Java’s ForkJoinPool is built this way.
• Palindrome checks and other problems that consume a sequence from both ends.
• Undo history with a cap: push new actions on one end, drop the oldest from the other when the cap is reached.

Queue using two stacks

A FIFO queue can be built from two LIFO stacks. Enqueue pushes onto an in stack. Dequeue pops from an out stack, and when out is empty it first moves every element of in across, which reverses them so the oldest is on top.

class TwoStackQueue:
    def __init__(self):
        self._in = []     # receives enqueues
        self._out = []    # serves dequeues, front of queue on top

    def enqueue(self, value):
        self._in.append(value)

    def dequeue(self):
        if not self._out:
            if not self._in:
                raise IndexError("dequeue from empty queue")
            while self._in:                 # reverse once: oldest ends on top
                self._out.append(self._in.pop())
        return self._out.pop()

    def __len__(self):
        return len(self._in) + len(self._out)

enqueue 1 2 3        in: [1 2 3]   out: []
dequeue              in: []        out: [3 2 1]   -> pops 1
enqueue 4            in: [4]       out: [3 2]
dequeue              in: [4]       out: [3]       -> pops 2 (no transfer needed)
dequeue              in: [4]       out: []        -> pops 3
dequeue              in: []        out: [4]       -> transfer, pops 4

The invariant is that every element in out is older than every element in in, and out holds its elements with the oldest on top. A transfer happens only when out is empty, so it never puts newer elements above older ones.

Amortized O(1). A single dequeue can cost O(n), when it triggers a transfer of n elements. But each element is pushed onto in once, popped from in once, pushed onto out once and popped from out once, so n enqueues and n dequeues do at most 4n stack operations in total. With the accounting method: charge each enqueue 3 units, spend 1 on the push and bank 2 with the element for its later transfer and final pop. The bank never goes negative, so the amortized cost per operation is O(1).

Amortized is not the same as worst case. Enqueueing 1,000,000 items and then timing each dequeue separately:

1,000,000 dequeues: total 124.7 ms, median 125 ns, 99.9th pct 250 ns, max 16.5 ms

The median dequeue takes 125 nanoseconds. One dequeue, the first, takes 16.5 milliseconds, about 130,000 times the median and 13 percent of the total, because it moves a million items. In a latency-sensitive system that single pause can matter more than the average. A ring buffer or deque avoids it.

Why build a queue this way at all? Two reasons beyond interviews. In purely functional languages, where arrays are immutable and linked lists are the native structure, a pair of lists is the standard O(1) amortized queue (often called a banker’s queue). And the two-stack trick extends to a queue with O(1) min or max: make each of the two stacks a min stack (next section) and the queue’s minimum is the smaller of the two stacks’ minimums. That gives the same result as the monotonic deque for sliding window minimum, with a different constant factor.

Stack using queues

The reverse direction is less useful but shows up as a classic problem. With a single queue, make push expensive: after enqueueing the new item, rotate the queue by dequeuing and re-enqueueing the other n - 1 items, so the newest item is at the front.

from collections import deque

class OneQueueStack:
    """Stack using a single FIFO queue: push is O(n), pop is O(1)."""

    def __init__(self):
        self._q = deque()

    def push(self, value):
        self._q.append(value)
        for _ in range(len(self._q) - 1):   # rotate the new item to the front
            self._q.append(self._q.popleft())

    def pop(self):
        if not self._q:
            raise IndexError("pop from empty stack")
        return self._q.popleft()

    def __len__(self):
        return len(self._q)

Push is O(n) and pop is O(1), and unlike the two-stack queue there is no amortization rescue: a sequence of n pushes costs O(n²). The two-queue version moves the cost around (cheap push, expensive pop, or the reverse) without improving it. A FIFO discipline cannot cheaply recover LIFO order, while two LIFO stacks can recover FIFO order, because reversing twice is the identity.

Balanced parentheses

Valid Parentheses: given a string of ()[]{} characters, decide whether every opener is closed by the matching closer in the right order. The invariant is that the stack holds the openers that are still waiting to be closed, innermost on top. A closer must match the top; anything else is an error.

PAIRS = {")": "(", "]": "[", "}": "{"}

def is_balanced(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

s = "{[()()]}"
{        stack: {
[        stack: { [
(        stack: { [ (
)        matches (, stack: { [
(        stack: { [ (
)        matches (, stack: { [
]        matches [, stack: {
}        matches {, stack: empty  -> balanced

s = "([)]"   ) arrives with [ on top -> not balanced

O(n) time and O(n) space in the worst case (all openers). Three failure modes must all be checked: a closer with an empty stack, a closer that does not match the top, and openers left over at the end. Code that checks only the first two accepts "((".

With only one bracket type, a counter is enough: increment on (, decrement on ), fail if it goes negative, succeed if it ends at zero. The counter is the stack’s height; with one type there is nothing else to remember. That reduction stops working as soon as there are two types, because "([)]" has correct counts for each type and is still invalid.

Related problems use the same stack with different payloads:

• Minimum Add to Make Parentheses Valid: count unmatched closers seen and openers left on the stack.
• Longest Valid Parentheses: push indices instead of characters, with a sentinel index -1 at the bottom marking the start of the current valid run; the length of a run ending at i is i - stack[-1].
• Score of Parentheses, Decode String (3[a2[c]] becomes accaccacc): push the partial result when entering a bracket and combine it when leaving.

In real parsers this is exactly what happens, except that the stack is usually the call stack of a recursive descent parser rather than an explicit list.

Min stack and max stack

Min Stack: support push, pop, top and get_min in O(1). The minimum of a stack can only change at the top, so it can be recorded as part of each entry: store, with every element, the minimum of the stack from the bottom up to and including that element.

class MinStack:
    def __init__(self):
        self._items = []     # pairs (value, minimum of the stack up to here)

    def push(self, value):
        current_min = value if not self._items else min(value, self._items[-1][1])
        self._items.append((value, current_min))

    def pop(self):
        return self._items.pop()[0]

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

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

Pushing 5, 3, 7, 3, 1 and then repeatedly reading the minimum and popping:

[(1, 1), (3, 3), (3, 7), (3, 3), (5, 5)]

Each pair is (get_min(), pop()). When the 1 leaves, the minimum reverts to 3 without any search, because the entry below already recorded it. This works because a stack can only undo its history in reverse order, so each saved minimum is always valid while its entry is present.

A leaner variant keeps a second stack that receives a value only when it is a new minimum. It must use <=, not <, so that duplicates of the minimum are each recorded:

def push(self, value):
    self._items.append(value)
    if not self._mins or value <= self._mins[-1]:
        self._mins.append(value)

def pop(self):
    value = self._items.pop()
    if value == self._mins[-1]:
        self._mins.pop()
    return value

With <, pushing 2, 2 and popping once would remove the only recorded 2 and report the wrong minimum. Space is O(n) worst case for both versions; the lean version saves space when minimums are rare.

There is also an O(1) extra space trick that stores 2 * value - min when a new minimum arrives and decodes it on pop. It works for integers, is fragile with overflow in fixed-width languages and does not work for arbitrary comparable objects, so it is rarely worth it.

Max stack with pop_max

A max stack with only peek_max is the min stack mirrored. Max Stack proper also requires pop_max: remove the largest element (the topmost one if tied) wherever it sits in the stack. That breaks the “only the top changes” property, so the per-entry trick no longer works. A standard approach keeps the stack and a max-heap of the same entries, each tagged with a unique id, and deletes lazily: removing an entry from one structure marks its id as dead, and the other structure discards dead entries when they reach its top.

import heapq, itertools

class MaxStack:
    def __init__(self):
        self._stack = []                 # (id, value)
        self._heap = []                  # (-value, -id): ties pop the newest
        self._removed = set()
        self._ids = itertools.count()

    def push(self, value):
        i = next(self._ids)
        self._stack.append((i, value))
        heapq.heappush(self._heap, (-value, -i))

    def _clean_stack(self):
        while self._stack[-1][0] in self._removed:
            self._removed.discard(self._stack.pop()[0])

    def _clean_heap(self):
        while -self._heap[0][1] in self._removed:
            self._removed.discard(-heapq.heappop(self._heap)[1])

    def pop(self):
        self._clean_stack()
        i, value = self._stack.pop()
        self._removed.add(i)             # the heap copy is now stale
        return value

    def top(self):
        self._clean_stack()
        return self._stack[-1][1]

    def peek_max(self):
        self._clean_heap()
        return -self._heap[0][0]

    def pop_max(self):
        self._clean_heap()
        neg_value, neg_i = heapq.heappop(self._heap)
        self._removed.add(-neg_i)        # the stack copy is now stale
        return -neg_value

push, pop_max and peek_max are O(log n) amortized, pop and top are O(1) amortized plus the heap work deferred to later. A balanced binary search tree keyed by (value, id) paired with a doubly linked list gives O(log n) worst case. Heaps and lazy deletion are covered in Heaps.

Expressions: infix, postfix and prefix

Arithmetic can be written three ways:

Prefix notation is named after Jan Łukasiewicz, who used it in logic in the 1920s; postfix is its mirror image, hence “reverse Polish”. Postfix and prefix are unambiguous without parentheses because each operator applies to a fixed number of the operands immediately available to it. That makes them trivial to evaluate with a stack, and it is why stack machines (the JVM, CPython’s bytecode interpreter, PostScript, HP calculators, Forth) execute what is essentially postfix code. CPython compiles a + b * c to load a, load b, load c, multiply, add, which is the postfix order.

Evaluating postfix

Scan left to right. Push operands. On an operator, pop two operands, apply, push the result. At the end exactly one value must remain.

import operator

OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul,
       "/": operator.truediv, "^": operator.pow}

def eval_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok in OPS:
            right = stack.pop()             # order matters for - / ^
            left = stack.pop()
            stack.append(OPS[tok](left, right))
        else:
            stack.append(float(tok))
    if len(stack) != 1:
        raise ValueError("malformed expression")
    return stack[0]

Evaluating 3 4 2 1 - 2 ^ * + (the stack after each token):

3    [3.0]
4    [3.0, 4.0]
2    [3.0, 4.0, 2.0]
1    [3.0, 4.0, 2.0, 1.0]
-    [3.0, 4.0, 1.0]
2    [3.0, 4.0, 1.0, 2.0]
^    [3.0, 4.0, 1.0]
*    [3.0, 4.0]
+    [7.0]

The first value popped is the right operand. Getting that backwards is the classic bug, and it only shows for the non-commutative operators.

O(n) time, O(n) space. A malformed expression shows up as a pop from an empty stack (too many operators) or more than one value at the end (too many operands). Evaluate Reverse Polish Notation is this function with integer division that truncates toward zero, which in Python is int(left / right), not left // right (floor division rounds -7 // 2 to -4, but the problem expects -3).

Evaluating prefix

Prefix is postfix read backwards. Scan right to left with the same stack; the difference is that the first value popped is now the left operand:

def eval_prefix(tokens):
    stack = []
    for tok in reversed(tokens):            # scan right to left
        if tok in OPS:
            left = stack.pop()              # left operand is now on top
            right = stack.pop()
            stack.append(OPS[tok](left, right))
        else:
            stack.append(float(tok))
    if len(stack) != 1:
        raise ValueError("malformed expression")
    return stack[0]

>>> eval_prefix("- * 2 3 / 8 4".split())
4.0

That is 2 * 3 - 8 / 4. Prefix can also be evaluated left to right by recursion (read an operator, recursively read two subexpressions), which is how Lisp’s surface syntax is parsed.

Infix to postfix: the shunting-yard algorithm

Edsger Dijkstra described the shunting-yard algorithm in 1961 for the first ALGOL 60 compiler. It converts infix to postfix in one left-to-right pass with an operator stack. The name comes from a railway shunting yard: operands go straight to the output track, while operators wait on a siding (the stack) until an operator of lower precedence or a closing parenthesis forces them out.

The rules:

1. An operand goes straight to the output.
2. An operator o first pops to the output every operator on the stack that should be applied before it: those with higher precedence, and those with equal precedence if o is left-associative. Then o is pushed.
3. ( is pushed.
4. ) pops operators to the output until the matching (, which is discarded.
5. At the end, pop everything that remains.

The invariant is that the operators on the stack between parentheses are in strictly increasing precedence from bottom to top (allowing equal precedence only for right-associative operators), so an operator is released exactly when nothing after it can bind more tightly.

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT_ASSOC = {"^"}

def to_postfix(tokens):
    output, ops = [], []
    for tok in tokens:
        if tok in PREC:
            while (ops and ops[-1] != "(" and
                   (PREC[ops[-1]] > PREC[tok] or
                    (PREC[ops[-1]] == PREC[tok] and tok not in RIGHT_ASSOC))):
                output.append(ops.pop())
            ops.append(tok)
        elif tok == "(":
            ops.append(tok)
        elif tok == ")":
            while ops and ops[-1] != "(":
                output.append(ops.pop())
            if not ops:
                raise ValueError("unmatched )")
            ops.pop()                       # discard the "("
        else:
            output.append(tok)              # operand
    while ops:
        if ops[-1] == "(":
            raise ValueError("unmatched (")
        output.append(ops.pop())
    return output

A trace of 3 + 4 * (2 - 1) ^ 2, showing the token, the operator stack and the output after each step:

token stack       output
3                 3
+     +           3
4     +           3 4
*     + *         3 4
(     + * (       3 4
2     + * (       3 4 2
-     + * ( -     3 4 2
1     + * ( -     3 4 2 1
)     + *         3 4 2 1 -
^     + * ^       3 4 2 1 -
2     + * ^       3 4 2 1 - 2
end               3 4 2 1 - 2 ^ * +

The * stays on the stack when ^ arrives because ^ binds tighter. Evaluating the result gives 7.0.

Associativity matters for exponentiation. 2 ^ 3 ^ 2 means 2 ^ (3 ^ 2) = 512, not (2 ^ 3) ^ 2 = 64. The rule “pop equal precedence only for left-associative operators” produces 2 3 2 ^ ^, which is correct. A longer check:

>>> p = to_postfix(tokenize("3 + 4 * 2 / (1 - 5) ^ 2 ^ 3"))
>>> " ".join(p)
'3 4 2 * 1 5 - 2 3 ^ ^ / +'
>>> eval_postfix(p), 3 + 4 * 2 / (1 - 5) ** 2 ** 3
(3.0001220703125, 3.0001220703125)

The implementations here were checked against Python’s own evaluation of about 20,000 random expressions with nested parentheses and all five operators.

Infix can be evaluated directly, without producing postfix, by running the same algorithm with two stacks: a value stack instead of the output list, and “pop an operator, pop two values, push the result” wherever the algorithm would emit an operator. Conversion from infix to prefix is shunting-yard run on the reversed token list with the parentheses swapped and the associativity rule mirrored, followed by reversing the output.

Pitfalls in expression parsing

• Unary minus. In -3 + 4 and 2 * (-1), the - takes one operand. A tokenizer has to distinguish it by context: a - at the start, after (, or after another operator is unary. The usual fix is to emit a distinct token (such as neg) with its own precedence, or to rewrite it as 0 - x when that preserves precedence.
• Multi-digit and decimal numbers must be grouped by the tokenizer, not handled character by character in the parser.
• Division semantics differ between languages (truncation versus floor) and between integer and float arithmetic.
• Precedence of unary minus versus exponentiation: in Python, -2 ** 2 is -4, because ** binds tighter than unary minus on its left. Not every language agrees.

Basic Calculator (+, -, parentheses and unary minus, no multiplication) has a shorter solution than a full parser. Keep a running result and a sign; at (, push the current result and sign and start fresh; at ), fold the inner result back:

def calculate(s):
    result, number, sign = 0, 0, 1
    stack = []                              # saved (result, sign) at each "("
    for ch in s:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch in "+-":
            result += sign * number
            number, sign = 0, (1 if ch == "+" else -1)
        elif ch == "(":
            stack.append((result, sign))
            result, sign = 0, 1
        elif ch == ")":
            result += sign * number
            number = 0
            prev_result, prev_sign = stack.pop()
            result = prev_result + prev_sign * result
    return result + sign * number

>>> calculate("1 - (2 - (3 + 4)) + -5")
1

The stack holds exactly what recursion would hold: the state of each enclosing parenthesized expression.

Iterative DFS with an explicit stack

Depth-first search is naturally recursive: visit a vertex, then recursively visit each unvisited neighbor. The recursion uses the call stack to remember where to resume in each vertex’s neighbor list. In Python that call stack is limited:

import sys

n = 5_000
path = {i: [i + 1] for i in range(n - 1)}   # 0 -> 1 -> 2 -> ... -> 4999
path[n - 1] = []

print(sys.getrecursionlimit())
print(len(dfs_iterative(path, 0)))
try:
    dfs_recursive(path, 0)
except RecursionError as e:
    print("RecursionError:", e)

1000
5000
RecursionError: maximum recursion depth exceeded

The default limit is 1,000 frames. A recursive DFS fails on any graph with a path longer than that, which includes a linked list of 1,000 nodes, a degenerate tree, a long snake through a grid, and many real dependency graphs. sys.setrecursionlimit raises the limit; with the limit set to 1,000,000, a 100,000-deep recursive DFS completed in testing here, while a 1,000,000-deep one still raised RecursionError. Raising the limit is a process-wide change, each Python frame costs memory, and recursion that passes through C code can still exhaust the native stack, so for input of unknown depth an explicit stack is the reliable choice.

Converting recursion to a stack

The direct conversion pushes neighbors and marks vertices visited when popped:

def dfs_iterative(graph, start):
    order, seen = [], set()
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue                        # pushed twice; skip the stale copy
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]):        # reversed so graph[u][0] is popped first
            if v not in seen:
                stack.append(v)
    return order

Two details make this produce exactly the same visiting order as the recursive version, which the tests above confirm on random directed graphs:

• Push neighbors in reverse. The stack pops the last pushed first, so pushing graph[u] in reverse order makes the first neighbor come off first.
• Mark on pop, not on push. A vertex may be pushed several times by different parents before it is visited. Marking it when pushed would fix its position at the first parent’s push, while recursion visits it from whichever parent reaches it first in depth-first order. Marking on pop and skipping stale copies matches recursion. The cost is that the stack can hold up to O(E) entries instead of O(V).

If only reachability matters and not the order, marking on push is fine and keeps the stack at O(V). That variant is not DFS order, though: it is a “stack-based search” that some sources still call DFS. For tasks that depend on DFS structure (discovery and finish times, topological sort, Tarjan’s strongly connected components, articulation points), the order matters.

Post-order: a stack of iterators

Recursion does more than visit vertices in order; it also knows when a vertex is finished (all its descendants done), which topological sort and cycle detection need. The cleanest iterative form stores, for each active vertex, an iterator over its remaining neighbors. That is precisely what a recursive frame stores.

def dfs_iterator_stack(graph, start):
    order, finish, seen = [start], [], {start}
    stack = [(start, iter(graph[start]))]
    while stack:
        u, neighbors = stack[-1]
        for v in neighbors:
            if v not in seen:
                seen.add(v)
                order.append(v)
                stack.append((v, iter(graph[v])))
                break
        else:                               # no unvisited neighbor left
            stack.pop()
            finish.append(u)                # post-order position
    return order, finish

The for ... else resumes u’s neighbor iteration where it stopped, pushes the first unvisited neighbor, and finishes u only when the iterator is exhausted. The stack holds at most O(V) entries (one per vertex on the current path), discovery order matches recursion, and finish matches recursive post-order exactly. The same pattern converts any recursive tree traversal (in-order, post-order) to an iterative one. Tree traversals are in Trees and graph DFS applications in Graph traversal.

The monotonic stack

A monotonic stack is a stack whose contents are kept sorted, increasing or decreasing from bottom to top, by popping everything that would violate the order before each push. It answers “for each element, what is the nearest element to the left (or right) that is larger (or smaller)?” for all elements in O(n) total, instead of O(n²) by scanning from each element.

Next greater element

For each position, find the next element to its right that is strictly greater, or -1 if none.

The idea: scan left to right and keep a stack of indices whose answer is not yet known. When a new element arrives, it is the answer for every waiting element smaller than it. The invariant that makes this cheap is that the waiting elements are non-increasing from bottom to top, so the smaller ones are exactly those on top of the stack. Pop them and record the new element as their answer, then push the new element. Whatever remains below it is at least as large, so the invariant holds after the push.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                              # indices whose answer is still unknown
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

>>> next_greater([2, 1, 2, 4, 3])
[4, 2, 4, -1, -1]

Why O(n). The inner while loop can run many times for one i, but every index is pushed once and popped at most once, so the total number of pops across the whole scan is at most n. This is the same amortized argument as for the two-stack queue, and it applies to every monotonic stack algorithm below.

The four variants differ in scan direction and comparison:

“Previous” answers are read from the top of the stack after popping, before pushing. Whether to pop on < or <= decides how equal elements are treated (strictly greater versus greater or equal), and getting it wrong is the most common monotonic-stack bug. When a problem counts subarrays, one side must use strict comparison and the other non-strict, or equal elements are counted twice.

Next Greater Element II makes the array circular. Scan indices 0 to 2n - 1 using nums[j % n] and push only during the first pass; the second pass resolves elements whose next greater element wraps around:

>>> next_greater_circular([2, 1, 2, 4, 3])
[4, 2, 4, -1, 4]

Daily Temperatures

For each day, how many days until a warmer temperature (0 if none)? This is next greater element returning distances instead of values:

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

The stack, as index:temperature, after each day of [73, 74, 75, 71, 69, 72, 76, 73]:

day temp  resolved   stack
0   73    []         0:73
1   74    [0]        1:74
2   75    [1]        2:75
3   71    []         2:75  3:71
4   69    []         2:75  3:71  4:69
5   72    [4, 3]     2:75  5:72
6   76    [5, 2]     6:76
7   73    []         6:76  7:73

Result [1, 1, 4, 2, 1, 1, 0, 0]. Day 5 (72) resolves days 4 and 3 at once, and day 6 resolves days 5 and 2. Days 6 and 7 never get popped and keep their default of 0.

Online Stock Span

The span of today’s price is the number of consecutive days, ending today, with a price less than or equal to today’s. This is previous greater element, computed online as prices arrive. Each stack entry stores a price and the span it absorbed, so popping a day also skips all the days that day had already absorbed:

class StockSpanner:
    def __init__(self):
        self._stack = []                    # (price, span) pairs, prices decreasing

    def next(self, price):
        span = 1
        while self._stack and self._stack[-1][0] <= price:
            span += self._stack.pop()[1]    # absorb the popped day's span
        self._stack.append((price, span))
        return span

>>> s = StockSpanner()
>>> [s.next(p) for p in [100, 80, 60, 70, 60, 75, 85]]
[1, 1, 1, 2, 1, 4, 6]

O(1) amortized per call, O(n) space.

Largest Rectangle in Histogram

Given bar heights, find the largest rectangle that fits under the bars. For each bar, the largest rectangle using that bar’s full height extends left and right until a strictly shorter bar on each side. So the answer needs, for every bar, its previous smaller and next smaller element, and a single increasing stack provides both: when a bar is popped because a shorter bar i arrived, i is its next smaller bar, and the element now beneath it on the stack is its previous smaller bar.

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

The trace for [2, 1, 5, 6, 2, 3]:

i=0 h=2 stack(heights)=[2]
  i=1: pop height 2, width 1, area 2
i=1 h=1 stack(heights)=[1]
i=2 h=5 stack(heights)=[1, 5]
i=3 h=6 stack(heights)=[1, 5, 6]
  i=4: pop height 6, width 1, area 6
  i=4: pop height 5, width 2, area 10
i=4 h=2 stack(heights)=[1, 2]
i=5 h=3 stack(heights)=[1, 2, 3]
  i=6: pop height 3, width 1, area 3
  i=6: pop height 2, width 4, area 8
  i=6: pop height 1, width 6, area 6
i=6 h=0 stack(heights)=[0]

The best is 10, the rectangle of height 5 over bars 2 and 3. The sentinel bar of height 0 at the end forces every remaining bar off the stack so that each one is measured. Popping on >= rather than > means a bar equal to the incoming one is measured early with too short a width, but the last of a run of equal bars is measured with the full width, so the maximum is still correct. The implementation was checked against an O(n²) brute force on thousands of random arrays.

O(n) time and O(n) space. Maximal Rectangle (largest all-ones rectangle in a binary matrix) runs this once per row on column heights that accumulate downward, for O(rows × cols) in total.

Trapping Rain Water

Given bar heights, how much water is trapped after rain? Water above bar i reaches min(max height to the left, max height to the right) - height[i], if positive. Three solutions, all O(n) time:

Monotonic stack, filling horizontal layers. Keep a decreasing stack of indices. When a bar taller than the top arrives, the top is a basin floor bounded by the new bar on the right and the next stack element on the left; add the water in that horizontal band.

def trap_stack(height):
    water = 0
    stack = []                              # indices, heights decreasing
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = height[stack.pop()]
            if not stack:
                break                       # no left wall
            left = stack[-1]
            width = i - left - 1
            water += (min(height[left], h) - bottom) * width
        stack.append(i)
    return water

Two pointers, filling vertical columns. Move inward from both ends. Whichever side has the lower current bar is the bottleneck: if height[left] < height[right], then there is a wall at least height[right] on the right, so the water above left is determined by left_max alone. Add it and move that pointer.

def trap_two_pointers(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

Prefix and suffix maxima compute left_max[i] and right_max[i] in two passes and apply the formula directly, using O(n) extra space.

On the standard example [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] both functions return 6, and all three agree with an O(n²) brute force on random inputs.

The two-pointer version is covered from the array side in Arrays. The 2D version (Trapping Rain Water II) uses neither: it needs a min-heap flood from the boundary inward.

Remove K Digits

Remove k digits from a number string to make the result as small as possible. The leftmost digits dominate, so a digit should be removed whenever the digit after it is smaller: “1432219” with k = 3 should drop the 4 (because 3 follows it), then the 3, then a 2. A non-decreasing stack does exactly that greedily:

def remove_k_digits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    if k:
        stack = stack[:-k]                  # still owe removals: drop from the end
    return "".join(stack).lstrip("0") or "0"

>>> remove_k_digits("1432219", 3), remove_k_digits("10200", 1), remove_k_digits("10", 2)
('1219', '200', '0')

Three edge cases: if removals remain after the scan, the stack is non-decreasing, so the largest digits are at the end and those are removed; leading zeros are stripped; an empty result is "0". The greedy choice was verified against trying every subset of positions on random inputs. Remove Duplicate Letters (smallest subsequence containing each letter once) is the same stack with an extra rule: a letter may only be popped if it appears again later.

Recognizing monotonic stack problems

The signals are “next/previous greater/smaller”, “nearest”, “how far until”, “span”, “the range in which this element is the minimum/maximum”, and sums or counts over all subarrays of their minimum or maximum (Sum of Subarray Minimums: each element contributes value × left_count × right_count, with both counts from monotonic stacks). If a brute force would scan outward from each element until hitting something larger or smaller, a monotonic stack almost certainly reduces it to O(n).

The monotonic deque: Sliding Window Maximum

Sliding Window Maximum: return the maximum of every window of k consecutive elements. A window drops elements from the front and adds them at the back, so a stack is not enough; a deque is.

The key observation: if nums[j] >= nums[i] and j > i, element i can never again be a window maximum, because every future window that contains i also contains j. So keep a deque of indices whose values are strictly decreasing from front to back. On each step:

1. Drop the front if it has left the window.
2. Pop from the back every index whose value is <= the new value (they are dominated).
3. Push the new index at the back.
4. The front is the maximum of the current window.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                            # indices, values decreasing front to back
    result = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()                    # front fell out of the window
        while dq and nums[dq[-1]] <= x:
            dq.pop()                        # dominated: can never be a maximum again
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the deque contents (as values) and the reported maximum:

i  x   deque         max
0  1   [1]
1  3   [3]
2  -1  [3, -1]       3
3  -3  [3, -1, -3]   3
4  5   [5]           5
5  3   [5, 3]        5
6  6   [6]           6
7  7   [7]           7

The answer is [3, 3, 5, 5, 6, 7]. Each index enters and leaves the deque at most once, so the total is O(n) regardless of k, with O(k) space.

Two alternatives are a max-heap of (value, index) with lazy removal of expired entries, O(n log n), and recomputing max of each window, O(nk). On 100,000 random floats:

The deque’s time does not depend on k. The brute force grows linearly with k; at k = 10 it is still competitive because max over a slice runs in C. The heap stays within a small factor of the deque in this run, but it pays O(log n) per push and never catches up.

The same structure gives the sliding window minimum (reverse the comparison) and appears inside harder problems: Shortest Subarray with Sum at Least K (monotonic deque over prefix sums, works with negative numbers where a plain sliding window fails), Constrained Subsequence Sum and Jump Game VI (dynamic programming where each state takes the maximum of the previous k states).

BFS with a queue

Breadth-first search explores a graph in order of distance from the start. The queue’s FIFO invariant is what makes that true: all vertices at distance d are enqueued before any vertex at distance d + 1, so they are all dequeued first.

from collections import deque

def bfs_order(graph, start):
    seen = {start}
    order = []
    queue = deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v)                 # mark on enqueue, not on dequeue
                queue.append(v)
    return order

O(V + E) time and O(V) space. Unlike DFS, BFS should mark vertices when they are enqueued. Marking on dequeue lets the same vertex be enqueued many times by different neighbors at the same level, which in a dense graph inflates the queue toward O(E) and can multiply the work. Shortest paths in unweighted graphs, level-order tree traversal and “minimum number of moves” puzzles are all BFS. The details, including path reconstruction and bidirectional BFS, are in Graph traversal.

Replacing the queue with a stack in this code does not produce DFS order (it marks on push, see above), and replacing it with a priority queue keyed by distance produces Dijkstra’s algorithm. The container decides the search.

Level-by-level processing

Many problems need to know where one level ends. Either store the distance with each vertex, or process the queue in rounds of its current length:

while queue:
    for _ in range(len(queue)):      # exactly the vertices of the current level
        u = queue.popleft()
        ...
    level += 1

len(queue) is evaluated once when range is created, so vertices appended during the round are left for the next one.

Multi-source BFS: Rotting Oranges

Rotting Oranges: in a grid, 2 is a rotten orange, 1 a fresh one and 0 an empty cell. Each minute, every fresh orange next to a rotten one rots. How many minutes until none are fresh, or -1 if some never rot?

Running a separate BFS from each rotten orange would be O(sources × cells). Instead, put all sources in the queue at distance 0 before starting. BFS then computes, for every cell, the distance to its nearest source, as if there were one virtual source connected to all of them by edges of length 0. The number of rounds is the answer.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))        # every source starts at distance 0
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):         # one full level = one minute
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

minute 0      minute 1      minute 2      minute 3      minute 4
2 1 1         2 2 1         2 2 2         2 2 2         2 2 2
1 1 0         2 1 0         2 2 0         2 2 0         2 2 0
0 1 1         0 1 1         0 1 1         0 2 1         0 2 2

The function returns 4 for this grid and -1 for [[2,1,1],[0,1,1],[1,0,1]], where the bottom-left orange is walled off. It was checked against a minute-by-minute simulation on 2,000 random grids.

The loop condition while queue and fresh matters: without the fresh test, the last round of rotten oranges is processed, finds nothing, and still increments minutes, giving an answer one too large. Two more edge cases: a grid with no fresh oranges returns 0 even if there are no rotten ones, and the function mutates its input, which a caller may not expect.

O(rows × cols) time and space. The same pattern solves Walls and Gates (distance from every room to the nearest gate), 01 Matrix (distance to the nearest 0), As Far from Land as Possible and multi-source shortest paths in general.

First non-repeating character in a stream

Characters arrive one at a time; after each, report the first character so far that has appeared exactly once, or # if none. A queue holds candidates in arrival order and a counter holds frequencies. Each new character is enqueued; then the front is discarded while it has been seen more than once.

from collections import Counter, deque

def first_non_repeating_stream(stream):
    counts = Counter()
    queue = deque()
    out = []
    for ch in stream:
        counts[ch] += 1
        queue.append(ch)
        while queue and counts[queue[0]] > 1:
            queue.popleft()
        out.append(queue[0] if queue else "#")
    return "".join(out)

>>> first_non_repeating_stream("aabcbcd")
'a#bbc#d'

Every character is enqueued once and dequeued at most once, so the whole stream costs O(n), O(1) amortized per character. The queue never needs to remove from the middle: a repeated character deep in the queue is harmless until it reaches the front, where it is discarded. That lazy deletion is what keeps the structure a plain queue.

The queue can hold O(n) entries. If the alphabet is small, a variant stores each character only on first sight (the duplicates are never enqueued), bounding the queue by the alphabet size. In Python, an insertion-ordered dict gives a neat alternative: keep the set of characters seen exactly once as dict keys, delete a key on its second occurrence, and the first key is the answer. Deleting from a dict is O(1), and finding the first key is fast in practice, although CPython’s compact dict leaves deleted entries behind until it resizes, so next(iter(d)) may have to skip over many of them, and the worst case is worse than the queue version’s. Both versions were checked against recomputing from scratch after every character.

Where stacks and queues appear in real systems

A recurring design issue in production queues is unbounded growth. An in-memory queue between a fast producer and a slow consumer grows until the process runs out of memory, and a long queue also means long latency for everything in it. Bounded queues with back-pressure (block, reject or drop) turn that slow failure into an explicit decision.

Summary