Python Stacks and Queues

A stack only adds and removes at one end, the top. That makes it the natural structure for "undo the most recent thing" and for anything nested:

history = []
history.append("add label")       # push
history.append("move label")
history.append("recolour label")
print(history[-1])                # peek: recolour label
print(history.pop())              # pop: recolour label
print(history)                    # ['add label', 'move label']

A Python list is an efficient stack because append() and pop() at the end are O(1) (amortised). history[-1] peeks at the top without removing it.

Stacks appear wherever the most recent item must be handled first: undo and redo histories, the browser back button, matching brackets in an expression, depth-first search, and the call stack that Python itself uses to track function calls. Removing from the front instead would turn it into a queue, with a different order and, for a list, a much higher cost.

A queue adds at the back and removes from the front, so items leave in arrival order. collections.deque (double-ended queue) does both in O(1):

from collections import deque
desk = deque()
desk.append("Nora")               # join the back
desk.append("Idris")
desk.append("Mei")
print(desk.popleft())             # Nora
print(desk[0])                    # peek at the next: Idris
print(len(desk))                  # 2

A list can technically act as a queue with pop(0), but that's O(n): removing the first element shifts every remaining element left. With thousands of items, the difference is dramatic. deque is built as linked blocks, so both ends are cheap.

deque also supports appendleft() and pop() for the other ends, rotate(), and maxlen= to keep only the newest N items, handy for "last 10 visitors" or a rolling window of readings. Indexing into the middle of a deque is O(n), so use it for its ends, not as a general list.

Removing from an empty list or deque raises IndexError, and in a real program that's often a normal situation, such as an undo button pressed with nothing to undo. Decide on a policy and implement it explicitly:

history = []
if history:
    last = history.pop()
else:
    last = None                    # nothing to undo

Or catch the exception where emptiness is unusual:

try:
    next_visitor = desk.popleft()
except IndexError:
    next_visitor = None

Wrapping the structure in a small class with methods such as undo() and is_empty() keeps the policy in one place, so callers don't each have to remember it. Unexpected IndexError: pop from an empty deque in a traceback usually means two parts of the program disagree about whether something should be there.

list and deque are designed for use within one thread of a program. When several threads share work, such as one thread receiving ticket requests and others processing them, use the queue module:

import queue
requests = queue.Queue()
requests.put("ticket for Nora")       # producer
item = requests.get()                 # consumer: waits if empty
requests.task_done()

queue.Queue handles the locking for you, and get() can block, waiting until an item arrives, or time out with get(timeout=5). queue.LifoQueue is a thread-safe stack and queue.PriorityQueue serves the smallest item first. For asyncio programs, asyncio.Queue plays the same role.

A safe collection is only part of a concurrent design. You also need to decide how workers stop, what happens to unfinished items on shutdown, and how errors are reported. Distributed task queues, such as Celery with Redis or RabbitMQ, extend the same idea across processes and machines.

Task: build independent undo and request structures, documenting empty behaviour and operation costs.

from collections import deque

undo = []                 # stack: append/pop at the end, O(1)
requests = deque()        # queue: append/popleft, O(1)

undo.extend(["crop photo", "add caption"])
requests.extend(["Nora", "Idris"])

print(undo.pop(), "|", requests.popleft())          # add caption | Nora
print(undo.pop() if undo else "nothing to undo")    # crop photo
print(undo.pop() if undo else "nothing to undo")    # nothing to undo
print(requests.popleft() if requests else "desk empty")   # Idris

Document the policy beside the code: empty structures return a message instead of raising. For the worked check, a queue follows first in, first out order.

The documentation covers using lists as stacks and queues, collections.deque and the queue module. Continue with linked lists and graph traversal. Practise with the Python exercises and Python quiz.