Lesson 4: Stacks and Queues

Stacks and queues are the minimalists of this course: arrays or linked lists with most operations *forbidden*, leaving only access at the ends. That restriction is their power — by promising exactly how elements enter and leave, they make program behaviour predictable enough to build compilers, schedulers and undo systems on. A stack is last-in, first-out (LIFO): elements are pushed and popped at the same end, the top. A queue is first-in, first-out (FIFO): elements are enqueued at the back and dequeued from the front.

The stack in action

Trace a stack evaluating the bracket string ([{}]). Push opening brackets; on a closing bracket, pop and check it matches:

Empty at the end means valid. A mismatch at any pop, or a non-empty stack at the end, means invalid. Notice what the stack bought: it remembers *nesting order* automatically, because the most recent unmatched opener is always exactly the one a closer must match. That is the same reason your language's call stack works: each function call pushes a frame (return address, local variables), and returning pops it — recursion in Lesson 7 is this mechanism wearing a costume.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)          # O(1) amortised

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()       # O(1)

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

    def is_empty(self):
        return len(self._items) == 0

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = Stack()
    for ch in s:
        if ch in '([{':
            st.push(ch)
        elif ch in ')]}':
            if st.is_empty() or st.pop() != pairs[ch]:
                return False
    return st.is_empty()

In practice you rarely write the class: a Python list *is* a stack (append/pop at the end), and that is the idiom. What matters is the discipline — only touch the end.

Queues, and the pop(0) trap

A queue's contract looks symmetric, but implementing it on a Python list hides a quadratic trap: pop(0) shifts every remaining element left (Lesson 2), so processing n items costs O(n^2). For n = 100,000 that is 10^10 pointer moves — seconds becoming hours. Three correct designs exist:

The circular buffer deserves a trace. Use a fixed array of capacity 5 with head and tail indices that wrap modulo 5. Enqueue A, B, C (tail advances 0, 1, 2); dequeue takes A (head moves to 1); enqueue D, E, F — F wraps to index 0. Logical order is read from head around the ring: B, C, D, E, F. Nothing ever shifts; indices do all the work. This is why ring buffers sit inside network cards, audio drivers and logging systems that must never block on data movement.

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, x):
        self._items.append(x)          # back of the queue

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()   # O(1), unlike list.pop(0)

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

    def is_empty(self):
        return len(self._items) == 0

The two-stacks queue is worth understanding rather than memorising: enqueue by pushing onto stack *in*; dequeue by popping from stack *out*; when *out* empties, pour all of *in* into it, which reverses the elements into FIFO order. Each element moves O(1) times across its life, hence amortised O(1) per operation — Lesson 1's amortised reasoning again.

Choosing between them

Ask one question: in what order must things be processed? Most-recent-first (undo, back button, expression parsing, depth-first traversal, backtracking) means stack. Fairness and arrival order (print spooling, request handling, breadth-first traversal, message pipelines) means queue. A deque (double-ended queue) supports both ends in O(1) and quietly powers sliding-window algorithms in Lesson 19; a priority queue breaks FIFO deliberately by importance rather than arrival — that is Lesson 9.

In the real world

Your text editor's undo history is a stack (often two: undo and redo). A browser's back button is a stack. Print queues, call-centre hold lines, web-server request lines and Kafka-style message pipelines are queues, and CPU schedulers keep per-priority queues of runnable threads. The JavaScript event loop that runs every web page is, at heart, a queue of callbacks. Compiler parsers push and pop stacks thousands of times per file — the bracket matcher above is a real component of every language toolchain.

Common mistakes

• Popping without an empty check. Underflow crashes parsers and evaluators; is_balanced above checks *before* popping for exactly this reason.
• Using list.pop(0) as a queue. Works in demos, dies in production. Reach for deque.
• Peeking by popping and forgetting to push back. peek exists precisely to inspect without mutating.
• Recursion depth as an invisible stack overflow. A recursive algorithm 100,000 calls deep will blow Python's recursion limit; converting it to an explicit stack (Lesson 7) is the standard rescue.

Real-World Challenge

Problem: evaluate a postfix (Reverse Polish) expression. In postfix notation operators follow their operands: 3 4 + 5 * means (3 + 4) * 5 = 35. Given a list of tokens (numbers and the operators + - * /), evaluate the expression with a stack, in one pass, and trace 2 3 1 * + 9 -.

Worked solution. Numbers get pushed. An operator pops the top two values, applies itself (mind the order: the *first* pop is the right operand), and pushes the result:

def eval_postfix(tokens):
    st = []
    for tok in tokens:
        if tok in '+-*/':
            b = st.pop()               # right operand (pushed later)
            a = st.pop()               # left operand
            if tok == '+': st.append(a + b)
            elif tok == '-': st.append(a - b)
            elif tok == '*': st.append(a * b)
            else: st.append(a / b)
        else:
            st.append(float(tok))
    return st.pop()                    # exactly one value should remain

Result -4, matching the infix reading 2 + 3 * 1 - 9. Time O(n), one pass, no recursion, no precedence table — postfix is what stack machines (the JVM, Python's own bytecode interpreter, old HP calculators) actually execute, because evaluation *is* stack discipline. Note the defensive details: a well-formed expression leaves exactly one value; an operator with fewer than two values on the stack means malformed input, and production code should raise rather than crash with IndexError.

Extension. Convert infix to postfix with the shunting-yard algorithm, which uses a second stack for operators and a precedence table — then chain the two: infix string in, numeric answer out. This pair of stacks is, in miniature, the front end of every compiler.

Worked example: undo and redo with two stacks

A text editor's undo system is two stacks and three rules: typing pushes the action onto the undo stack and *clears* the redo stack; undo pops the undo stack, reverses the action, and pushes it onto the redo stack; redo does the mirror image. Trace typing A, typing B, undo, undo, redo, typing C:

The cleared redo stack after typing C is the subtle rule: once you undo and then do something new, the abandoned future (B) must be unreachable — otherwise redo would resurrect a branch of history that no longer connects to the present. Browsers implement the same machine for back/forward navigation, and database transaction logs are its industrial cousin.

The circular queue, implemented

Lesson 4's deque is the practical choice, but the circular buffer is the instructive one: fixed storage, wrap-around indices, and one classic ambiguity — when head meets tail, is the buffer full or empty? Reserving one empty slot resolves it: full means (tail + 1) mod capacity == head.

class CircularQueue:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.capacity = capacity
        self.head = 0
        self.tail = 0

    def enqueue(self, x):
        if (self.tail + 1) % self.capacity == self.head:
            raise OverflowError("queue full")
        self.data[self.tail] = x
        self.tail = (self.tail + 1) % self.capacity

    def dequeue(self):
        if self.head == self.tail:
            raise IndexError("queue empty")
        value = self.data[self.head]
        self.head = (self.head + 1) % self.capacity
        return value

    def __len__(self):
        return (self.tail - self.head) % self.capacity

Every operation is O(1) with zero allocation — which is why this shape appears in interrupt handlers and audio pipelines where allocating memory mid-operation is forbidden.

Deque, fully loaded

Two deque features complete the picture. First, deque(maxlen=k) silently discards from the opposite end when full — a fixed-size window of the most recent k items with O(1) appends, which is precisely the rate limiter of Lesson 11 and the rolling log buffers of production systems. Second, deque operations at the ends are not only O(1) but thread-safe in CPython, which is why deques appear as hand-off queues between producer and consumer threads (though queue.Queue adds the blocking and capacity semantics real pipelines need). And a forward pointer: an explicit stack converts recursive DFS into iterative DFS (Lesson 8) and is the standard rescue when recursion depth, not logic, is the bug — if you take one habit from this lesson, take "when you see nesting or history, think stack; when you see fairness or order, think queue; when you need both ends, think deque".