Stacks and Queues in Python: Use Cases and collections.deque

A pricing-rule editor accepts the formula tier[gold{2]} without complaint and then crashes when the rule runs. A linter that points at the exact column of the mistake needs only one idea: the bracket you opened most recently must be the first one you close. That rule, last in, first out, is a stack. Its mirror image, first in, first out, is a queue. Between them they decide the order in which most programs process things.

A stack in twelve lines

A Python list already behaves as a stack: append pushes onto the right end and pop() removes from the right end, both O(1). The checker below pushes every opening bracket together with its position, and for every closing bracket pops and compares.

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


def check_nesting(text):
    """Return None if brackets nest correctly, else (index, reason)."""
    stack = []                       # holds (char, index) of unclosed openers
    for i, ch in enumerate(text):
        if ch in "([{":
            stack.append((ch, i))
        elif ch in PAIRS:
            if not stack:
                return (i, f"'{ch}' closes nothing")
            opener, _ = stack.pop()
            if opener != PAIRS[ch]:
                return (i, f"'{ch}' does not match '{opener}'")
    if stack:
        opener, i = stack[-1]
        return (i, f"'{opener}' is never closed")
    return None


for sample in ["price[tier{2}](x)", "price[tier{2]}(x)", "total)", "calc((1+2)"]:
    print(f"{sample!r:22} -> {check_nesting(sample)}")

'price[tier{2}](x)'    -> None
'price[tier{2]}(x)'    -> (12, "']' does not match '{'")
'total)'               -> (5, "')' closes nothing")
'calc((1+2)'           -> (4, "'(' is never closed")

Notice what the stack stores at any moment: exactly the brackets that are still waiting for a partner, innermost on top. The three failure cases correspond to the three ways the stack can disagree with the text: a closer with nothing to close, a closer that meets the wrong opener, and openers left over at the end.

Where stacks hide in real systems

• The call stack. Each function call pushes a frame; each return pops one. Infinite recursion ends with RecursionError: maximum recursion depth exceeded once the limit (1000 by default in CPython) is hit.
• Undo and back navigation. Push the previous state before every change; undo pops it. A redo feature is a second stack.
• Depth-first search and backtracking. Recursion is an implicit stack; an explicit list-based stack lets you go deeper than the recursion limit allows.
• Parsing and evaluating expressions. Operators and operands wait on a stack until their partner arrives, as in the bracket example.

A queue at the clinic desk

A walk-in clinic serves patients in the order they arrive. New arrivals join the back; the nurse takes from the front. The right tool is collections.deque, which supports O(1) appends and removals at both ends. The board of recently called patients uses maxlen, so old entries fall off automatically.

from collections import deque


class WalkInQueue:
    """Clinic desk: first come, first served, with a bounded 'recently called' board."""

    def __init__(self):
        self.waiting = deque()
        self.board = deque(maxlen=3)      # old entries fall off the left automatically

    def arrive(self, name):
        self.waiting.append(name)         # join at the back

    def call_next(self):
        if not self.waiting:
            return None
        name = self.waiting.popleft()     # leave from the front
        self.board.append(name)
        return name


desk = WalkInQueue()
for patient in ["Ila", "Omar", "Bea", "Chen", "Dev"]:
    desk.arrive(patient)

print(desk.call_next(), desk.call_next())
desk.arrive("Fay")
print(desk.call_next(), desk.call_next())
print("waiting:", list(desk.waiting))
print("board:  ", list(desk.board))

Ila Omar
Bea Chen
waiting: ['Dev', 'Fay']
board:   ['Omar', 'Bea', 'Chen']

Fay arrived after Dev even though she turned up in the middle of the calls, and Ila has already dropped off the board because it only holds three names. A bounded deque is a cheap way to keep "the last N events" for a rolling average, a recent-searches list or a log tail.

Why not just use list.pop(0)?

Removing the first element of a list forces every other element to shift one slot left. The subclass below counts that shifting while draining 1,000 items.

class CountingList(list):
    shifted = 0

    def pop(self, index=-1):
        if index == 0:
            CountingList.shifted += len(self) - 1
        return super().pop(index)


items = CountingList(range(1000))
while items:
    items.pop(0)
print("list.pop(0) drained 1000 items; elements shifted:", CountingList.shifted)

list.pop(0) drained 1000 items; elements shifted: 499500

That is 1000 x 999 / 2 moves, the same quadratic shape you saw in the previous lesson. deque.popleft() moves nothing, so draining the same 1,000 items costs 1,000 cheap operations.

Common mistakes

• Popping from an empty container. A list raises IndexError: pop from empty list; a deque raises IndexError: pop from an empty deque. Check for emptiness or catch the error. In the bracket checker, forgetting if not stack before popping turns a user typo into a crash.
• Draining a list with `pop(0)`. No error, but throughput collapses as the backlog grows. Switch to deque.popleft().
• Mutating a deque while iterating over it. Python raises RuntimeError: deque mutated during iteration. Loop with while queue: and popleft() instead.
• Forgetting that `maxlen` discards silently. A full bounded deque drops the oldest item without any warning, which is perfect for a log tail and a data-loss bug for a job queue. Use an unbounded deque or a queue.Queue(maxsize=n) when dropping is unacceptable.
• Using `queue.Queue` in single-threaded code. It works, but the locking is overhead you do not need; deque is lighter. Note that queue.Queue.get_nowait() on an empty queue raises queue.Empty, which is a different exception from IndexError.

How this shows up in real projects and interviews

Real services are full of queues: a job runner draining background tasks, a rate limiter keeping the timestamps of the last N requests, an event buffer flushing in batches. Stacks show up as undo history, parser state and the iterative form of recursion. Interviewers like the bracket-matching problem because it tests whether you can see the stack in a string, and they follow it up with "now report the position of the error" or "what if there are multiple bracket types". Expect breadth-first search as the standard queue exercise; you will use it for the tree traversal in the trees and heaps lesson.