Stacks and queues

Why it matters

Stacks and queues are lists with a rule about which end you use. That small rule makes them the right model for a lot of real systems: the browser back button and "undo" are stacks; print jobs, web request handling and message brokers are queues. Your Python interpreter keeps a call stack of functions, which is why a traceback lists the calls in order. Matching brackets with a stack is a classic first problem, and the same idea powers code editors, linters and parsers.

Stack: last in, first out (LIFO)

Picture a stack of plates. You add (push) to the top and remove (pop) from the top. The last plate you put on is the first one you take off.

A Python list is a good stack, because adding and removing at the end are both O(1):

stack = []
stack.append("a")    # push
stack.append("b")
stack.append("c")
top = stack[-1]      # peek: "c"
stack.pop()          # "c"
stack.pop()          # "b"
len(stack) == 0      # is it empty? not yet, "a" is left

Calling pop() on an empty list raises IndexError, so check if stack: first.

Queue: first in, first out (FIFO)

Picture a line at a shop. You join at the back (enqueue) and leave from the front (dequeue).

Do not use list.pop(0) for this: removing the front of a list shifts every other item, which is O(n). Use collections.deque ("deck"), which is O(1) at both ends:

from collections import deque

queue = deque()
queue.append("job1")     # enqueue at the back
queue.append("job2")
queue.append("job3")
queue.popleft()          # "job1": first in, first out
queue[0]                 # peek at the front: "job2"

You will use a deque as the queue in breadth-first search later in this course.

Worked example: balanced brackets

A string is balanced if every opening bracket (, [ or { is closed by the matching bracket in the right order. "([]{})" is balanced. "(]" and "([)]" are not, and neither is "((" (never closed) or ")(" (closed before opened).

The insight: the most recent unclosed bracket is the one that must close next. "Most recent" means a stack.

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[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack

Trace "{[()]}":

End of string and the stack is empty, so it is balanced. With "([)]", the ) arrives while [ is on top, so it fails immediately.

Three checks catch every bad case:

1. A closer arrives and the stack is empty (")(").
2. A closer does not match the top ("(]").
3. The stack is not empty at the end ("((").

Characters that are not brackets are skipped, so "print(x[0])" works. The whole thing is one pass: O(n) time, O(n) space in the worst case.

Choosing between them

• Need to undo, backtrack or match nested things? Stack.
• Need to process things in arrival order, or explore level by level? Queue.
• Need the highest priority first instead of the oldest? That is a priority queue (Python's heapq), a topic for later.

Common mistakes

• Using list.pop(0) as a queue. It works but is O(n) per call; use deque.popleft().
• Popping an empty stack. Check if stack: before pop() or stack[-1].
• Forgetting the final check. "((" never triggers a mismatch; only return not stack catches it.
• Counting instead of stacking. Counting opens and closes passes "([)]", which is wrong. Order matters, so you need the stack.

Quick recap

• Stack = LIFO: append and pop on a list, both O(1).
• Queue = FIFO: deque.append and deque.popleft, both O(1).
• Bracket matching: push openers, match closers against the top, and end with an empty stack.

Try it

In the Do tab, write is_balanced and a small queue function. The checks cover the empty string, single brackets, nesting, wrong order and text mixed in.