Stacks, Queues & Deques

Abstract data types vs implementations

An abstract data type (ADT) is a contract: a set of operations and the rules they obey, with no mention of memory. An implementation is the concrete data structure that fulfils the contract. Keeping them separate is one of the most useful ideas in software design: code that depends only on the contract keeps working when you swap the implementation.

The same ADT can have several implementations with different costs:

A stack on a list

A Python list is already a great stack, as long as the end of the list is the top: append pushes and pop() pops, both O(1). Wrapping it in a small class documents the intent and prevents callers from reaching into the middle.

You already use a stack every time you call a function: the call stack. Each call pushes a frame holding its local variables; each return pops it. A recursion that never stops overflows that stack, which is what Python's RecursionError protects against.

Queues, and the list.pop(0) trap

A queue adds at the back and removes from the front. With a list, the natural code is append + pop(0). It works, and it is correct, but pop(0) moves every remaining element one slot left (M20). Process a queue of n items and you have done O(n²) work.

collections.deque

deque gives O(1) append, appendleft, pop, and popleft. In CPython it is a doubly linked list of fixed-size blocks, each holding 64 item pointers. The deque tracks the left block and an index into it, and the right block and an index into it. Pushing at either end writes into the current end block, allocating a new block only when that one is full. This hybrid gives linked-list speed at the ends with array-like density in the middle.

With maxlen, adding to one end silently drops an item from the other end. That makes deque(maxlen=n) the idiomatic "keep the last n things" tool: recent log lines, a sliding window of readings, a tail -n on a file.

Preview: queue.Queue for threads

When several threads share a queue, you need more than fast ends: you need locking (so two threads cannot corrupt the structure) and blocking (a consumer should sleep until an item arrives, a producer should wait when a bounded queue is full). The queue module provides exactly that:

• queue.Queue(maxsize=0): FIFO. put blocks when full, get blocks when empty; task_done() and join() let you wait until all work is processed.
• queue.LifoQueue: a thread-safe stack. queue.PriorityQueue: smallest item first (a heap, see M25). queue.SimpleQueue: unbounded FIFO without task tracking.
• Since Python 3.13, Queue.shutdown() makes further put calls raise queue.ShutDown, a clean way to stop workers.

pixi run python workers.py

Threads are covered fully in M37; asyncio.Queue, its coroutine counterpart, appears in M38.

A circular buffer from scratch

How would you build an O(1) queue on a plain array, with no shifting? Keep a fixed array plus a head index (the front) and a size. The back is at (head + size) % capacity. Dequeuing advances head; enqueuing writes at the back. When an index runs off the end of the array, the modulo wraps it to the beginning, so the queue chases itself around a ring.

class ArrayQueue:
    def __init__(self, capacity=4):
        self._data = [None] * capacity
        self._head = 0
        self._size = 0

    def enqueue(self, item):
        if self._size == len(self._data):
            self._grow()                                   # or raise / overwrite, for a bounded buffer
        back = (self._head + self._size) % len(self._data)
        self._data[back] = item
        self._size += 1

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

Growing a ring is subtle: you cannot just copy the array, because the items may wrap around the end. Instead, copy them out in queue order ((head + i) % capacity for i in range(size)) into the start of the new array, and reset head to 0. You will write this in exercise 2.

Application: balanced brackets

Is {[()()]} balanced? Is ([)]? Every opening bracket must be closed by the matching kind, in reverse order of opening: the most recently opened bracket must close first. "Most recent first" is the signature of a stack.

1. Scan left to right. Push every opening bracket.
2. On a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it.
3. At the end, the stack must be empty (nothing left unclosed).

Compilers, linters, and editors do exactly this (with more bracket types, quotes, and comments) to highlight the matching parenthesis or report "unexpected ')'". You'll implement it in exercise 1.

Application: undo and redo

An editor keeps two stacks. Every edit pushes onto the undo stack and clears the redo stack (a new edit makes the old redo history meaningless). Undo pops from undo and pushes onto redo; redo does the reverse.

Application: RPN and the shunting-yard algorithm

We write arithmetic in infix notation: the operator sits between operands, 3 + 4 * 2. Infix needs precedence rules and parentheses to be unambiguous. Reverse Polish notation (RPN, or postfix) puts operators after their operands: 3 4 2 * +. It needs no parentheses and no precedence, and it is trivial to evaluate with a stack. HP calculators, the PostScript language, and Python's own bytecode virtual machine all work this way.

Evaluating RPN

Scan tokens. A number is pushed. An operator pops two values (the second pop is the left operand), applies itself, and pushes the result. At the end exactly one value remains.

The disassembly loads a, b, c onto the VM's value stack, then multiplies, then adds: it is literally RPN.

Converting infix to postfix: shunting-yard

Edsger Dijkstra's shunting-yard algorithm (named after a railway yard where carriages are reordered) converts infix to postfix with one stack of operators:

1. A number goes straight to the output.
2. An operator o: while the stack's top is an operator with higher precedence, or equal precedence and o is left-associative, pop it to the output. Then push o.
3. ( is pushed. ) pops operators to the output until the matching (, which is discarded. If none is found, the parentheses are mismatched.
4. At the end, pop all remaining operators to the output (any ( left means a mismatch).

The result is 3 4 2 1 - * +. You will implement the full algorithm, with right-associative ^ and error checking, in exercise 5 and the mini-project.

Preview: queues in breadth-first search

A queue processes things in the order they were discovered. Applied to a graph, that explores everything 1 step away, then everything 2 steps away, and so on: breadth-first search (BFS), which finds shortest paths in unweighted graphs. Swap the queue for a stack and you get depth-first search instead. Same loop, different ADT, completely different behaviour.

Graphs get a full treatment in M26 and M31.

Application: the monotonic stack

Problem: for each day's temperature, how many days until a warmer day? Or more generally, for each element, find the next greater element to its right. The brute force checks every later element: O(n²).

A monotonic stack solves it in O(n). Keep a stack of indexes whose answers are still unknown, with their values in decreasing order from bottom to top. When a new value arrives, it is the answer for every smaller value on top of the stack: pop them and record it. Then push the new index.

Why is this O(n) when there is a loop inside a loop? Each index is pushed once and popped at most once, so the inner while runs at most n times in total across the whole outer loop. That is an amortized argument, just like the dynamic array in M19.

Monotonic stacks solve a whole family of problems: daily temperatures, stock span, largest rectangle in a histogram, trapping rain water, and removing digits to make the smallest number.

Pitfalls and choosing the right tool

• list.pop(0) as a queue: O(n) per dequeue. Use deque.popleft().
• Popping an empty stack: [].pop() raises IndexError; check first or catch it, and give your own classes a clear message.
• Operand order in RPN: the first pop is the right operand. 5 2 - is 3, not −3.
• Indexing a deque in the middle is O(n). If you need random access, you want a list.
• Forgetting maxlen drops silently: data falls off the other end with no error.
• Sharing a plain list between threads for producer/consumer work: use queue.Queue.

Practice

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

class ArrayQueue:
    def __init__(self, capacity=4):
        self._data = [None] * capacity
        self._head = 0
        self._size = 0

    def __len__(self):
        return self._size

    def _grow(self):
        old = self._data
        new = [None] * (2 * len(old))
        for i in range(self._size):
            new[i] = old[(self._head + i) % len(old)]
        self._data = new
        self._head = 0

    def enqueue(self, item):
        if self._size == len(self._data):
            self._grow()
        self._data[(self._head + self._size) % len(self._data)] = item
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from empty queue")
        item = self._data[self._head]
        self._data[self._head] = None
        self._head = (self._head + 1) % len(self._data)
        self._size -= 1
        return item

    def peek(self):
        if self._size == 0:
            raise IndexError("peek at empty queue")
        return self._data[self._head]

    def __iter__(self):
        for i in range(self._size):
            yield self._data[(self._head + i) % len(self._data)]

import operator

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

def eval_rpn(expr):
    stack = []
    for tok in expr.split():
        if tok in OPS:
            if len(stack) < 2:
                raise ValueError(f"operator {tok!r} needs two operands")
            right = stack.pop()
            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]

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

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] in PREC 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()
        else:
            output.append(tok)
    while ops:
        top = ops.pop()
        if top == "(":
            raise ValueError("unmatched '('")
        output.append(top)
    return output

Mini-project: an expression calculator

flowchart LR
  A["text: 2*(3+4)"] --> B[tokenize]
  B --> C["tokens: 2 * ( 3 + 4 )"]
  C --> D[shunting-yard]
  D --> E["postfix: 2 3 4 + *"]
  E --> F[stack evaluator]
  F --> G[14]
        

pixi init calc
cd calc
pixi add python=3.14 pytest
pixi run python calc.py "2 * (3 + 4)"
pixi run python -m pytest -q

Quiz

Recap

• An ADT is a contract; implementations fulfil it with different costs.
• A stack is LIFO: a list with append/pop is ideal.
• A queue is FIFO: use deque (append/popleft), never list.pop(0).
• deque is a doubly linked list of blocks: O(1) ends, O(n) middle; maxlen bounds it; rotate cycles it.
• A circular buffer is an array plus head and size with modulo indexing.
• Stacks solve bracket matching, undo/redo, RPN evaluation, shunting-yard conversion, and next-greater problems.
• Queues drive BFS; queue.Queue coordinates threads.

Going further

• collections.deque
• queue: a synchronized queue class
• dis: Python's stack-based bytecode
• Shunting yard algorithm (Wikipedia)
• Next: M23 Hash Tables & Sets.