Arrays, stacks and queues

A Python list is an array: its elements sit next to each other in memory, so reaching index i is a predictable computation and costs $O(1)$ no matter how long the list is. Almost every other structure in this chapter either extends that array or trades it away. Stacks and queues are the two simplest disciplines you can put on top of it.

Push, pop, enqueue and dequeue below and watch the same numbers leave in opposite orders.

The cost of touching each end #

For a Python list used as an array:

• a[i] is $O(1)$ — one address calculation.
• a.append(x) is amortised $O(1)$ — occasionally the array is full and must be reallocated and copied, but spread over many appends the average is constant.
• a.pop() from the end is $O(1)$.
• a.pop(0) or a.insert(0, x) is $O(n)$ — every other element must shift.

That last line is the reason a list is a fine stack but a poor queue: dequeuing from the front re-shuffles the whole array each time, making $n$ dequeues $O(n^2)$.

Queue done right #

collections.deque is a doubly linked list of fixed-size blocks, so it offers $O(1)$ append and pop at both ends:

from collections import deque
 
q = deque()
q.append("a")        # enqueue at the back
q.append("b")
first = q.popleft()  # dequeue from the front, O(1)

Use a deque whenever you need a queue; use a list when you need a stack or random access.

Where each is used #

• Stack: undo/redo, matching brackets, depth-first search, the function call stack itself.
• Queue: task scheduling, buffering, breadth-first search, printer spools.

Where next: linked lists — giving up cheap indexing to make insertion and deletion cheap anywhere.