Stacks and Queues

The library has a chain of books and a librarian who can splice in a new card anywhere along it. That much freedom is a problem. Some jobs only make sense if you take the freedom away. The reading-room cart at the end of the day works one way: every book the visitors return gets dropped on top of the cart, and the librarian picks them up from the top to reshelve, newest-returned-first. The hold queue at the front desk works the other way: the first patron in line gets the next available copy, the next patron after them gets the one after that, no cutting. The cart is a stack. The hold queue is a queue. They are the same chain underneath, with one rule about which end you may touch.

The shape goes back to Alan Turing's 1946 design notes for ACE, the computer he proposed at the British National Physical Laboratory. He needed a way for a function to call another function and remember where to come back to. His answer was a stack of return addresses: every call pushes a new address on top, every return pops the top address off. Every modern programming language still works this way. When you call f() from inside main(), the runtime pushes main's position on a stack of frames; when f returns, the runtime pops back. Recursion exists at all because the stack lets the same function pile its own return points on top of itself. The queue arrived a few years later from operations research — early operating systems in the 1960s used queues to schedule print jobs, a discipline still alive every time a page comes out of an office printer in the order it was sent.

A returns cart and a hold-line at the library: stack on the left, queue on the right.

You already wrote the chain. Reuse it. Open stack_queue.py and paste in the LinkedList class from the previous lesson — the same Node, the same head pointer, the same append and prepend. Then build both new shapes on top of it.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        cursor = self.head
        while cursor.next is not None:
            cursor = cursor.next
        cursor.next = new_node
 
    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
 
    def pop_head(self):
        if self.head is None:
            raise IndexError("empty")
        value = self.head.value
        self.head = self.head.next
        return value
 
    def pop_tail(self):
        if self.head is None:
            raise IndexError("empty")
        if self.head.next is None:
            value = self.head.value
            self.head = None
            return value
        cursor = self.head
        while cursor.next.next is not None:
            cursor = cursor.next
        value = cursor.next.value
        cursor.next = None
        return value
 
    def show(self):
        parts = []
        cursor = self.head
        while cursor is not None:
            parts.append(str(cursor.value))
            cursor = cursor.next
        return "[" + ", ".join(parts) + "]"
 
 
class Stack:
    def __init__(self):
        self._chain = LinkedList()
 
    def push(self, value):
        self._chain.prepend(value)
 
    def pop(self):
        return self._chain.pop_head()
 
    def peek(self):
        if self._chain.head is None:
            raise IndexError("empty")
        return self._chain.head.value
 
    def show(self):
        print(f"stack top -> {self._chain.show()}")
 
 
class Queue:
    def __init__(self):
        self._chain = LinkedList()
 
    def enqueue(self, value):
        self._chain.append(value)
 
    def dequeue(self):
        return self._chain.pop_head()
 
    def show(self):
        print(f"queue front -> {self._chain.show()}")

The Stack pushes onto the head and pops from the head, so the most recent book is always closest to the entry point. The Queue appends to the tail and pops from the head, so the oldest book leaves first. Same chain. One rule difference. Run both through the same plates.

print("--- stack ---")
s = Stack()
s.show()
for plate in ["A", "B", "C"]:
    s.push(plate); s.show()
print("peek:", s.peek())
print("pop:", s.pop()); s.show()
print("pop:", s.pop()); s.show()
 
print("--- queue ---")
q = Queue()
q.show()
for plate in ["A", "B", "C"]:
    q.enqueue(plate); q.show()
print("dequeue:", q.dequeue()); q.show()
print("dequeue:", q.dequeue()); q.show()

Output:

--- stack ---
stack top -> []
stack top -> [A]
stack top -> [B, A]
stack top -> [C, B, A]
peek: C
pop: C
stack top -> [B, A]
pop: B
stack top -> [A]
--- queue ---
queue front -> []
queue front -> [A]
queue front -> [A, B]
queue front -> [A, B, C]
dequeue: A
queue front -> [B, C]
dequeue: B
queue front -> [C]

Notice the stack shows newest on the left because new plates land at the head. The queue shows oldest on the left because new plates go to the tail and the head is whatever has been waiting longest. The single difference between the two classes is which end of the chain each operation touches.

The call stack from Turing's notes is sitting inside Python the whole time you write code. Watch it move with one print.

import traceback
 
def countdown(n):
    print(f"--- entering countdown({n}) ---")
    traceback.print_stack()
    if n == 0:
        return
    countdown(n - 1)
 
countdown(2)

Output (truncated for clarity):

--- entering countdown(2) ---
  File "stack_queue.py", line 110, in <module>
    countdown(2)
  File "stack_queue.py", line 107, in countdown
    countdown(n - 1)
  File "stack_queue.py", line 105, in countdown
    traceback.print_stack()
--- entering countdown(1) ---
  ...
  File "stack_queue.py", line 107, in countdown
    countdown(n - 1)
  File "stack_queue.py", line 107, in countdown
    countdown(n - 1)
  File "stack_queue.py", line 105, in countdown
    traceback.print_stack()
--- entering countdown(0) ---
  ...

Each call to countdown adds another frame to the top of Python's own call stack. Watch the bottom of each printed stack grow taller as the recursion gets deeper. When n hits zero and the function returns, the runtime pops the top frame off and resumes the previous one. That is the same pop from the Stack class you just wrote, written in C and built into the language.

Python's own call stack growing as recursive calls pile up.

Now meet the built-ins. A Python list is already a perfectly good stack — append is push, pop is pop, [-1] is peek. For a queue, list is a trap, because removing from the front of a list shifts every other element down by one. Use collections.deque instead: append for the back, popleft for the front, both in constant time.

from collections import deque
 
py_stack = []
for plate in ["A", "B", "C"]:
    py_stack.append(plate); print("stack:", py_stack)
print("pop:", py_stack.pop(), "stack:", py_stack)
 
py_queue = deque()
for plate in ["A", "B", "C"]:
    py_queue.append(plate); print("queue:", list(py_queue))
print("popleft:", py_queue.popleft(), "queue:", list(py_queue))

Output:

stack: ['A']
stack: ['A', 'B']
stack: ['A', 'B', 'C']
pop: C stack: ['A', 'B']
queue: ['A']
queue: ['A', 'B']
queue: ['A', 'B', 'C']
popleft: A queue: ['B', 'C']

Question: a web browser's "back" button — is that a stack or a queue?

Answer: a stack. Every page you visit gets pushed on top. "Back" pops the top page off and shows you the one underneath. The page you visited longest ago sits at the bottom and is the last one you can return to.

Stacks and queues let you reach a known book in the chain by knowing how it got there. They do not help you when the question is "where is the book called Moby Dick?" and you have no idea which shelf it is on. Walking the chain to find a name takes as long as the chain is. The next shape in the library lets you jump straight from a name to a shelf.