lesson 174 Algorithms & Complexity · advanced

Stacks and queues

When work piles up, the order it comes out matters. A stack hands back the newest item; a queue hands back the oldest. Choosing the wrong one gives wrong answers or slow programs.

You'll be able to

Use append and pop for last-in, first-out processing (undo, bracket matching)
Use deque append and popleft for first-in, first-out processing (fair queues, level-by-level searches)
Explain why list.pop(0) makes a slow queue

The idea

A stack is last in, first out (LIFO): like a pile of plates, you take from the top. A Python list is a ready-made stack: append puts an item on top and pop() takes the top one off, both O(1).

Stacks fit any job where the most recent thing must be dealt with first: undoing the last edit, or checking that brackets close in the right order. Every closing bracket must match the latest bracket still open.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Do the brackets in a template match?

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

for template in ['{"items": [1, 2]}', '{"items": [1, 2}', "(total * (1 - rate)", "rate)"]:
    print(template, balanced(template))

example-2.py · Popping an empty stack

history = ["typed Hello"]
print(history.pop())
print(history.pop())

A queue is first in, first out (FIFO): the item that has waited longest goes next, as in a support desk. A list *can* do this with pop(0), but a list stores its items in one block, so removing the first item moves every other item one place left: O(n) per removal, O(n²) for a whole queue. collections.deque is built for both ends: append adds at the back and popleft takes from the front, both O(1).

example-3.py · A support queue, oldest ticket first

from collections import deque

tickets = deque(["T-101 login", "T-102 refund", "T-103 address"])
tickets.append("T-104 refund")
while tickets:
    ticket = tickets.popleft()
    print("handling", ticket, "| still waiting:", len(tickets))

When to use which: a stack when the newest item must be handled first (undo, matching, walking a tree depth-first); a queue when the oldest must go first (fair processing, retry lines, searching level by level so the nearest answers are found first). Mistakes to avoid: pop() where you meant a queue (silently unfair), list.pop(0) on long queues (slow), and popping without checking for empty.

Review

Stack: append and pop() on a list, newest first (undo, brackets, depth-first walks).
Queue: append and popleft() on a deque, oldest first (fair processing, level-by-level search).
list.pop(0) shifts every remaining item, so a list makes an O(n²) queue.
Next: recursion uses a stack too, the interpreter's own, and that has limits and costs.

Practise this