Stacks, Queues

Data Structures in Practice

Chapter 4 · Stacks, Queues

Stacks and queues are not new containers so much as rules about which end you use. A stack takes and gives from the same end. A queue takes at one end and gives from the other. Choosing the right underlying structure (Data Structures in Practice 1 and 2) is what makes those rules cheap.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings are claimed; costs are described as patterns, as in earlier chapters.

Stack: Last In, First Out

The most recently added item is the first one out, like a pile of plates. A Python list is a fine stack: append pushes and pop() pops, both at the end, which Data Structures in Practice 2 showed to be cheap (amortised constant).

Queue: First In, First Out

The oldest item leaves first, like a line at a counter. A list is a poor queue because pop(0) shifts every remaining item. collections.deque is built for both ends: append and popleft are both constant cost.

from collections import deque

stack = []
stack.append("a"); stack.append("b"); stack.append("c")
print(stack.pop(), stack.pop(), stack)

q = deque()
q.append("a"); q.append("b"); q.append("c")
print(q.popleft(), q.popleft(), q)

try:
    [].pop()
except IndexError as e:
    print("IndexError:", e)
try:
    deque().popleft()
except IndexError as e:
    print("IndexError:", e)
    

c b ['a']
a b deque(['c'])
IndexError: pop from empty list
IndexError: pop from an empty deque
    

Same three items in, opposite order out. Popping an empty stack or queue raises IndexError, so test for emptiness first (if stack:) or catch the error.

Need	Good choice	Avoid
Stack	list (`append`, `pop`) or deque	Inserting or removing at the front of a list
Queue	deque (`append`, `popleft`)	`list.pop(0)`: shifts everything
Queue shared between threads	queue.Queue	A bare list or deque with hand-made locking
Keep only the last N items	deque(maxlen=N)	Slicing a list after every append

Stack in Action: Matching Brackets

Anything that must be closed in the reverse order it was opened is a stack problem. Push each opener; on a closer, the top of the stack must be its partner.

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

for s in ["(a[b]{c})", "(]", "((", "))", ""]:
    print(repr(s), balanced(s))
    

'(a[b]{c})' True
'(]' False
'((' False
'))' False
''  True
    

Three failure modes are covered: a wrong partner ("(]"), a closer with nothing open ("))", caught by not st), and openers left over at the end ("((", caught by the final not st). The same pattern underlies the call stack, expression evaluation and back-tracking.

Two Stacks: Undo and Redo

Undo history is a stack of earlier states. Redo needs a second stack that catches whatever undo removes. A new edit invalidates the redo history, so it is cleared.

class Editor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []

    def type(self, s):
        self.undo_stack.append(self.text)
        self.redo_stack.clear()
        self.text += s

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

e = Editor()
e.type("Hi"); e.type(" there")
print(repr(e.text))
e.undo(); print(repr(e.text))
e.redo(); print(repr(e.text))
e.undo(); e.type("!"); e.redo(); print(repr(e.text))
    

'Hi there'
'Hi'
'Hi there'
'Hi!'
    

In the last line the redo did nothing: typing "!" after an undo cleared the redo stack, which is how editors behave. (This stores whole snapshots for clarity; a real editor would store small changes.)

Deque: Both Ends, and a Size Limit

With maxlen, a deque silently drops from the opposite end when full. That is a ready-made "most recent N" buffer. rotate moves items around the ring, which suits round-robin turns.

recent = deque(maxlen=3)
for i in range(1, 6):
    recent.append(i)
print(recent)

rr = deque(["A", "B", "C"])
order = []
for _ in range(5):
    order.append(rr[0])
    rr.rotate(-1)
print(order, rr)
    

deque([3, 4, 5], maxlen=3)
['A', 'B', 'C', 'A', 'B'] deque(['C', 'A', 'B'])
    

Indexing the middle of a deque

A deque is quick at both ends, but reaching an item in the middle by index is not its strength (unlike a list). If you find yourself indexing a deque in the middle, you probably want a different structure.

The queue Module: Task Queues

queue.Queue wraps the same idea with locking, so several threads can safely put and get. It offers put, get, qsize, empty, an optional maxsize (a full queue makes put wait, or raise queue.Full with put_nowait), and queue.LifoQueue for a thread-safe stack.

import queue

tq = queue.Queue()
for t in ["t1", "t2", "t3"]:
    tq.put(t)
print(tq.qsize(), tq.get(), tq.get(), tq.empty())

try:
    queue.Queue().get_nowait()
except queue.Empty:
    print("queue.Empty")

lq = queue.LifoQueue()
for t in [1, 2, 3]:
    lq.put(t)
print(lq.get(), lq.get())

bq = queue.Queue(maxsize=1)
bq.put("x")
try:
    bq.put_nowait("y")
except queue.Full:
    print("queue.Full")
    

3 t1 t2 False
queue.Empty
3 2
queue.Full
    

The classic use is producer and worker: one side puts tasks, a worker thread gets and processes them, and a None acts as a "stop" signal.

import threading

results = []
wq = queue.Queue()

def worker():
    while True:
        item = wq.get()
        if item is None:
            break
        results.append(item * item)

th = threading.Thread(target=worker)
th.start()
for n in [1, 2, 3, 4]:
    wq.put(n)
wq.put(None)
th.join()
print(results)
    

[1, 4, 9, 16]

Because there is one worker and a first-in-first-out queue, results arrive in submission order. With several workers the order of results would not be guaranteed. For a single-threaded program, a plain deque is simpler and avoids the locking overhead.

A decision habit

Ask which item you need next. "The newest" is a stack. "The oldest" is a queue. "The most urgent" is neither, and is the subject of Data Structures in Practice 6.

Challenges

Exercise 1

Write rpn(expr) that evaluates a postfix expression such as "3 4 + 2 *" using a stack: push numbers, and on +, - or * pop two values (the second pop is the left operand) and push the result. Check that "3 4 + 2 *" gives 14 and "5 1 2 + 4 * + 3 -" gives 14.

📄 View solution

Exercise 2

Write last_n(lines, n) that returns the last n items of any iterable using deque(maxlen=n), so it never holds more than n at once. Test it on range(10) with n=3, on a list shorter than n, and with n=1. Then say what happens with list.pop(0) as a queue on a very long list and why deque avoids it.

📄 View solution

Exercise 3

Write hot_potato(names, k) using a deque: repeatedly rotate so the k-th person is at the front, remove them, and record the order of removal until one remains. Return the list of removed names and the survivor. For ["Ann", "Bob", "Cy", "Dee", "Eve"] with k=3, work out the answer by hand first, then check it.

📄 View solution

Quick Reference

Stack (LIFO): list.append and list.pop()
Queue (FIFO): deque.append and deque.popleft(); avoid list.pop(0)
Empty pop raises IndexError; check first
deque(maxlen=N): keeps the latest N, drops from the other end
rotate(k): shifts the ring, handy for round-robin
queue.Queue / LifoQueue: thread-safe, with maxsize, queue.Empty and queue.Full
Undo and redo: two stacks; a new edit clears redo

Coming next

Data Structures in Practice 5 covers linked lists: nodes and pointers, how they work, and why in Python they rarely beat the list.