Stacks and queues

Many problems only ever touch one end of a collection. The cafe's order screen needs an Undo button that reverses the most recent change first. The online shop packs orders in the order they arrived, so the oldest waiting order is always next. The roaster's control panel shows the average of the last ten temperature readings, forgetting older ones as new ones arrive. In each case, items enter and leave in a strict pattern, and choosing a structure built for that pattern makes the code simpler and faster.

This lesson introduces two of the most widely used structures in computing. A stack hands back the most recent item first; a queue hands back the oldest. You will build both, see why a Python list is perfect for a stack but poor for a queue, use collections.deque for queues and sliding windows, and apply them to real tasks: undo, checking brackets, packing orders and simulating the cafe line.

Abstract data types

A stack and a queue are abstract data types (ADTs): they are defined by the operations they allow and the rules those operations follow, not by how they are stored. A stack promises push, pop and peek with last-in, first-out behavior; how the items are kept is a separate decision called the implementation. Separating the two lets you choose or change the implementation later without touching the code that uses the structure, the same idea as the classes and interfaces of PYTH-102.

For each ADT in this course, ask two questions: what operations does the problem need, and which implementation makes those operations cheap? For stacks and queues, the answer to the second question is that every core operation should be O(1).

Stacks: last in, first out

A stack works like a pile of cups at the cafe counter: you add a cup to the top and take the top cup off. The last item added is the first removed, which is called LIFO (last in, first out). The standard operations are push (add to the top), pop (remove and return the top), peek (look at the top without removing it) and a test for emptiness.

A Python list is an excellent stack if you treat its end as the top. append is push and pop() is pop, both O(1), and items[-1] is peek. Wrapping the list in a small class makes the intent clear and prevents code from reaching into the middle.

class Stack:
    """A last-in, first-out stack built on a list (the end of the list is the top)."""
    def __init__(self):
        self._items = []
    def push(self, item):
        self._items.append(item)
    def pop(self):
        if not self._items:
            raise IndexError("pop from an empty stack")
        return self._items.pop()
    def peek(self):
        if not self._items:
            raise IndexError("peek at an empty stack")
        return self._items[-1]
    def __len__(self):
        return len(self._items)

cups = Stack()
for size in ["small", "medium", "large"]:
    cups.push(size)
print(cups.peek(), len(cups))
print(cups.pop(), cups.pop(), len(cups))

large 3
large medium 1

Undo with two stacks

Undo is the classic stack application. Every change made on Mei's order screen is pushed onto an undo stack. Pressing Undo pops the most recent change and reverses it, so the changes come back off in exactly the opposite order to the one in which they were made. Adding a redo feature needs a second stack: undone changes are pushed onto the redo stack, and any brand-new change clears it, because redoing an old change after a new one would make no sense.

class Order:
    def __init__(self):
        self.lines = {}
        self._undo, self._redo = [], []

    def set_qty(self, item, qty, record=True):
        old = self.lines.get(item, 0)
        if qty:
            self.lines[item] = qty
        else:
            self.lines.pop(item, None)
        if record:
            self._undo.append((item, old))
            self._redo.clear()           # a new change makes redo meaningless

    def undo(self):
        item, old = self._undo.pop()
        self._redo.append((item, self.lines.get(item, 0)))
        self.set_qty(item, old, record=False)

    def redo(self):
        item, qty = self._redo.pop()
        self._undo.append((item, self.lines.get(item, 0)))
        self.set_qty(item, qty, record=False)

o = Order()
o.set_qty("latte", 2)
o.set_qty("muffin", 1)
o.set_qty("latte", 3)
print(o.lines)
o.undo(); print(o.lines)
o.undo(); print(o.lines)
o.redo(); print(o.lines)

{'latte': 3, 'muffin': 1}
{'latte': 2, 'muffin': 1}
{'latte': 2}
{'latte': 2, 'muffin': 1}

Each entry on the undo stack records what is needed to reverse one change, here the item and its previous quantity. Real editors use the same design, often storing command objects that know how to undo themselves. Stacks also appear inside Python itself: every function call pushes a frame onto the call stack and every return pops it, which lesson 6 explores with recursion.

Matching brackets

A stack also solves matching problems, where each opening item must be closed in reverse order. Sam Okoye is writing a checker for the shop's price-rule formulas, such as (base * (1 + tax)) - [discount], and wants to reject formulas with unbalanced brackets before they reach the shop. Scan the text left to right: push each opening bracket, and for each closing bracket pop the top of the stack and check that it is the matching opener. The text is balanced if no mismatch occurs and the stack is empty at the end.

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

def balanced(text):
    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

for formula in ["(base * (1 + tax)) - [discount]", "(base * (1 + tax)", "[price)", "a + b)"]:
    print(f"{formula:<34} {balanced(formula)}")

(base * (1 + tax)) - [discount]    True
(base * (1 + tax)                  False
[price)                            False
a + b)                             False

def is_balanced(text):
    opens = sum(text.count(c) for c in '([{')
    closes = sum(text.count(c) for c in ')]}')
    return opens == closes

print(is_balanced('([)]'))

Queues: first in, first out

A queue works like the line at the cafe counter: people join at the back and are served from the front, so the first to arrive is the first served. This is FIFO (first in, first out). The operations are enqueue (add at the back), dequeue (remove from the front) and peek at the front.

A list makes a poor queue. Appending at the back is fine, but removing from the front with pop(0) shifts every remaining item, O(n), as lesson 2 showed. The standard library's collections.deque (pronounced deck, short for double-ended queue) is designed for this job: append, appendleft, pop and popleft are all O(1). Internally it is a chain of fixed-size blocks, so neither end ever needs to shift the items in the middle.

from collections import deque

packing = deque()
for order_id in [1041, 1042, 1043]:
    packing.append(order_id)              # enqueue at the back
print("next to pack:", packing[0])
print("packed", packing.popleft())        # dequeue from the front
packing.append(1044)
print("waiting:", list(packing))
print("packed", packing.popleft(), "then", packing.popleft())
print("still waiting:", len(packing))

next to pack: 1041
packed 1041
waiting: [1042, 1043, 1044]
packed 1042 then 1043
still waiting: 1

deque supports most list operations, including len, iteration, in and indexing near the ends, but indexing in the middle of a long deque is O(n), so use it for its ends. The table compares the two choices for each core operation.

Some systems implement a queue with a fixed-size list used as a ring, called a circular buffer: two indexes mark the front and the back, and each wraps around to the start of the list when it reaches the end. Nothing ever shifts, so both ends are O(1), and the memory never grows. Network cards, audio players and the roaster's sensor firmware use ring buffers because their size is known in advance. In Python you rarely need to write one, since deque already provides O(1) ends, but recognizing the idea helps when you read code in other languages or work with hardware. Whatever the implementation, the contract is the same: items leave in the order they arrived.

class PackingQueue:
    def __init__(self):
        self._orders = []

    def add(self, order_id):
        self._orders.append(order_id)

    def next(self):
        return self._orders.pop()

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

q = PackingQueue()
q.add(1041)
q.add(1042)
print(q.next())

Sliding windows with a bounded deque

A deque created with maxlen keeps only the most recent items: once full, adding at one end silently drops an item from the other. That is exactly a sliding window. Kai's roaster panel shows the average of the last few drum temperature readings, which smooths out noise from the sensor; a deque with maxlen holds the window, and a running sum avoids re-adding the whole window on every reading.

from collections import deque

def smoothed(readings, size=3):
    window, total, out = deque(maxlen=size), 0.0, []
    for r in readings:
        if len(window) == size:
            total -= window[0]            # the oldest reading is about to fall off
        window.append(r)
        total += r
        out.append(round(total / len(window), 1))
    return out

temps = [196.0, 201.5, 199.0, 205.5, 210.0, 208.5, 212.0]
print(smoothed(temps))

[196.0, 198.8, 198.8, 202.0, 204.8, 208.0, 210.2]

def recent(orders, n=5):
    return orders[:n]

print(recent([1, 2, 3, 4, 5, 6, 7, 8]))

Simulating the cafe line

Queues are the heart of simulations. Rosa wants to know whether one barista can keep up with the morning rush, or whether customers will wait too long. A simple simulation steps through the morning one minute at a time: customers arriving in that minute join a queue, and the barista takes the next customer from the front whenever the previous drink is done. The program records how long each customer waited.

from collections import deque

def simulate(arrivals, serve_minutes):
    """arrivals: minute each customer arrives (sorted); returns each customer's wait."""
    line, waits = deque(), []
    pending = deque(arrivals)
    busy_until, minute = 0, 0
    while pending or line:
        while pending and pending[0] == minute:
            line.append(pending.popleft())
        if line and minute >= busy_until:
            arrived = line.popleft()
            waits.append(minute - arrived)
            busy_until = minute + serve_minutes
        minute += 1
    return waits

rush = [0, 0, 1, 2, 2, 2, 3, 5, 6, 6]           # ten customers over six minutes
for serve in (1, 2):
    w = simulate(rush, serve)
    print(f"{serve} min per drink: average wait {sum(w) / len(w):.1f} min, longest {max(w)} min")

1 min per drink: average wait 1.8 min, longest 3 min
2 min per drink: average wait 6.3 min, longest 12 min

The simulation shows that at one minute per drink the line clears quickly, while at two minutes the waits pile up. Simulations like this, with random arrivals instead of a fixed list, help businesses plan staffing. Python's standard library also has queue.Queue, a queue that several threads can share safely, which PYTH-250 uses for concurrent programs; for ordinary single-threaded code, deque is simpler and faster.