Stacks and queues

A data structure is a way of organising data so that certain actions are fast. You already know lists, dicts and sets. Stacks and queues are simpler ideas built on top of them, and they are behind undo buttons, browser history, print queues, ticket counters and task schedulers.

A stack with a list

LIFO stands for Last In, First Out. Adding to a stack is called push; removing the top item is called pop. A Python list does both at its end in O(1): append() pushes and pop() pops. my_list[-1] lets you look at the top without removing it (often called peek).

history = []                    # an empty stack
history.append("home")          # push
history.append("search")
history.append("product page")
print(history[-1])              # peek: product page
print(history.pop())            # back button: product page
print(history.pop())            # search
print(history)                  # ['home']

Checking balanced brackets with a stack

1. Go through the text one character at a time.
2. When you see an opening bracket ( [ or {, push it onto the stack.
3. When you see a closing bracket, the top of the stack must be its matching opener. If the stack is empty or the top does not match, the text is not balanced.
4. At the end, the stack must be empty; leftover openers mean something was never closed.

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

print(is_balanced("total = (price * (1 + gst[0]))"))   # True
print(is_balanced("print((x)"))                         # False

A queue with collections.deque

FIFO stands for First In, First Out. A deque (say "deck", short for double-ended queue) from the collections module adds and removes at both ends in O(1). Use append() to join the back of the queue and popleft() to serve the front.

from collections import deque

counter = deque()
counter.append("Asha")      # joins the line
counter.append("Bilal")
counter.append("Chen")
print(counter.popleft())    # Asha is served first
print(len(counter), "still waiting:", list(counter))

import time
from collections import deque

n = 20_000
items = list(range(n))
start = time.perf_counter()
while items:
    items.pop(0)
list_ms = (time.perf_counter() - start) * 1000

line = deque(range(n))
start = time.perf_counter()
while line:
    line.popleft()
deque_ms = (time.perf_counter() - start) * 1000

print("list.pop(0):", round(list_ms, 1), "ms   deque.popleft():", round(deque_ms, 1), "ms")

Priority queues with heapq

Sometimes the most important item should come out first, not the oldest. That is a priority queue. The heapq module keeps a list arranged as a heap, a tree-like order where the smallest item is always at position 0. heappush and heappop each take O(log n).

import heapq

emergency = []
heapq.heappush(emergency, (3, "sprained ankle"))
heapq.heappush(emergency, (1, "heart attack"))
heapq.heappush(emergency, (2, "high fever"))

while emergency:
    priority, case = heapq.heappop(emergency)
    print(priority, case)          # 1 first, then 2, then 3

The idea of a linked list

A linked list stores items in separate little boxes called nodes. Each node holds a value and a pointer (a reference) to the next node, like a treasure hunt where each clue tells you where the next clue is. Adding or removing at the front is fast, because you only change one pointer, but reaching the 500th item means walking through 499 nodes. Python's deque is built from linked blocks for this reason.