Queues
Understand FIFO ordering, why queues are the right structure for BFS, and why collections.deque beats a list for queue operations.
- Define a queue and explain the FIFO (first-in, first-out) principle
- Explain why BFS uses a queue to process nodes level by level
- Describe why collections.deque is preferred over a list for queue operations
A queue is a sequence where items enter at one end (the back) and leave from the other end (the front). The first item in is the first item out — FIFO: first in, first out. This is exactly how a real queue works: the person who arrives first is served first.
Compare to a stack: a stack is LIFO — you take from the same end you put in. A queue is FIFO — you take from the opposite end. The difference sounds small but leads to completely different traversal behaviour.
Why BFS uses a queue
Breadth-first search (BFS) explores a graph level by level: all nodes at distance 1 from the start, then all nodes at distance 2, then distance 3, and so on. A queue enforces this ordering automatically.
When you reach a node, you enqueue all its neighbours. Because newer nodes go to the back and you always dequeue from the front, you finish every node at distance d before any node at distance d+1. The queue's FIFO property is what makes BFS produce shortest paths in an unweighted graph — no node at a farther level can "cut in line."
If you replaced the queue with a stack in BFS, you would get depth-first search: the most recently discovered node is explored next, driving deep into one path before coming back.
The problem with list.pop(0)
A Python list can simulate a queue: append() adds to the back, pop(0) removes
from the front. The problem is that pop(0) is O(n).
When you call pop(0), Python must shift every remaining element one position
left to fill the gap. On a list with 10 000 items, that is 10 000 copies per
dequeue. A BFS over 10 000 nodes would do roughly 50 million copies just to
maintain the queue — accidental O(n²) behaviour from a one-line oversight.
collections.deque
collections.deque is a double-ended queue backed by a doubly linked list of
fixed-size blocks. Both append() (add to right) and popleft() (remove from
left) are O(1), regardless of size.
from collections import deque
q = deque()
q.append('a') # enqueue → deque(['a'])
q.append('b') # enqueue → deque(['a', 'b'])
q.append('c') # enqueue → deque(['a', 'b', 'c'])
front = q.popleft() # dequeue → 'a', deque(['b', 'c'])
front = q.popleft() # dequeue → 'b', deque(['c'])deque also supports appendleft() and pop() for the other end, which is why
it is called double-ended. For a plain queue you only need append and
popleft.
The rule of thumb: use a deque any time you need to remove from the front of
a sequence. Use a list when you only remove from the end (stack pattern). The
wrong choice costs you O(n) per operation.
Recognising queue problems
Ask: "do I need to process things in the order they arrived?" If yes, use a queue. BFS is the textbook case, but task schedulers, print spoolers, and rate-limited request buffers all follow the same pattern: first request in, first request handled.
Where to go next
Next: queues in practice — implementing a task queue and BFS shortest-path
on an adjacency-list graph using collections.deque.