PYTHON / DATA STRUCTURES AND ALGORITHMS
Queues and deques
Build correct FIFO queues in Python with collections.deque, know why list.pop(0) is the wrong tool, and when queue.Queue is needed instead.
What you will learn
- Replace list.pop(0) with deque.popleft() to avoid O(n) shifting on every dequeue
- Use deque(maxlen=n) for a rolling window that discards from the opposite end
- Drive BFS and round-robin scheduling with popleft, append and rotate
- Choose queue.Queue when threads must block waiting for work; deque cannot wait
Understanding Queues and deques
A queue serves items in the order they arrived: you add at one end and remove from the other, first in first out. A Python list can do this, but only badly in one direction. A list keeps its elements in a single contiguous array, so list.pop(0) has to move every remaining element one slot toward the front, and list.insert(0, x) has to move them all the other way. Each of those operations is O(n), which means draining an n-item queue built on a list costs O(n squared).
collections.deque solves this by storing elements in a doubly linked chain of fixed-size blocks (64 slots per block in CPython) with direct pointers to the first and last block. append, appendleft, pop and popleft therefore touch only one end block and run in O(1) with no shifting and no whole-structure reallocation. The trade-off is the middle: d[k] has to walk block by block from whichever end is nearer, so random access degrades to O(n), and slicing is not implemented at all, so d[1:3] raises TypeError.
Being double-ended makes deque more than a plain queue. appendleft puts an item back at the front when you decide not to process it, rotate(k) shifts the whole sequence without copying it, and maxlen turns the deque into a fixed-size window that silently drops from the far end as you push. For threads, note that a single append or popleft is atomic under the GIL, but there is no way to wait for an item to appear; queue.Queue wraps a deque in a lock plus condition variables and adds blocking get, put and join.
from collections import deque
queue = deque(["ada", "bob", "cy"])
queue.append("dee")
print("serving:", queue.popleft())
print("waiting:", list(queue))
# double-ended: an item you decided not to handle goes back to the front
skipped = queue.popleft()
queue.appendleft(skipped)
print("back at front:", queue[0])
# bounded deque: pushing past maxlen drops from the opposite end
recent = deque(maxlen=3)
for n in range(1, 6):
recent.append(n)
print(n, list(recent))A queue is a discipline (first in, first out) and deque is the data structure that makes both ends O(1) so you never pay a list's element-shifting cost.
Worked examples
Breadth-first traversal
Shows the classic use of a FIFO queue: visiting a graph level by level.
from collections import deque
graph = {"a": ["b", "c"], "b": ["d"], "c": ["d", "e"], "d": ["e"], "e": []}
def bfs(start):
order = []
seen = {start}
q = deque([start])
while q:
node = q.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
return order
print(bfs("a"))Example explained
Line 1q.popleft() takes the oldest discovered node, which is what makes the traversal breadth-first rather than depth-first.
Line 2Nodes are marked in seen at enqueue time, not at dequeue time, so d is never queued twice even though both b and c point at it.
Line 3while q: is the empty check; popleft on an exhausted deque would raise IndexError instead of returning None.
Line 4Swapping popleft() for pop() with no other change turns this same code into a depth-first walk.
Round-robin turns with rotate
Uses rotate to cycle a fixed set of participants without copying the sequence.
from collections import deque
turns = deque(["red", "green", "blue"])
for _ in range(4):
print(turns[0])
turns.rotate(-1)
print(list(turns))Example explained
Line 1turns[0] is cheap because index 0 is an end position; a middle index would force a block walk.
Line 2rotate(-1) moves the front item to the back by repointing ends, so nothing is copied and the deque length never changes.
Line 3A positive argument rotates the other way: rotate(1) would move the last item to the front.
Line 4After four prints the deque has rotated four times over three items, leaving it one step past its starting arrangement.
queue.Queue for a worker thread
Demonstrates the blocking queue you need when the consumer runs in another thread.
import queue
import threading
work = queue.Queue()
results = []
def worker():
while True:
item = work.get()
if item is None:
work.task_done()
break
results.append(item * item)
work.task_done()
t = threading.Thread(target=worker)
t.start()
for n in range(1, 6):
work.put(n)
work.put(None)
work.join()
t.join()
print(results)Example explained
Line 1work.get() blocks until an item exists, so the worker never busy-loops and never sees an empty-queue error.
Line 2None is a sentinel: a queue has no end-of-stream signal of its own, so you send one explicitly.
Line 3Every get must be matched by a task_done, because join() returns only when the unfinished-task count reaches zero.
Line 4Results come out in submission order because a single FIFO consumer processes them one at a time.
Important notes
deque append and popleft are individually atomic under the GIL, but a check-then-pop pair is not; two threads can both pass 'if q:' and one gets IndexError.
deque has no sort or slice support and no O(1) middle insert; if you need those, a list or a different structure is the right choice.
Common mistakes
Using a list with pop(0) or insert(0, x) as a queue: it works for a hundred items and then stalls, because each call shifts every remaining element and the total cost grows as O(n squared).
Treating a deque like a list: d[len(d)//2] quietly costs O(n) because it walks blocks from the nearest end, and d[1:3] raises TypeError since deque supports no slicing.
Expecting deque(maxlen=3) to signal when it is full: it discards the item at the opposite end without any error, so pushing five values leaves only the last three and the first two are gone.
Try it yourself
Change, predict, then run
Write a hot-potato game: put six names in a deque and repeatedly rotate(-1) three times then popleft the eliminated player, printing each elimination until one name remains.
Open the Python workspaceCheck your understanding
You keep only the newest 1000 log lines as they stream in. Why is deque(maxlen=1000) faster than appending to a list and then doing lines = lines[-1000:] each time?
- The deque discards the oldest item in constant time, while the slice copies 1000 elements into a new list on every single line.
- The deque stores lines in a hash table, so discarding the oldest becomes an amortised O(1) lookup.
- The list version is slower only because rebinding the name lines adds an extra reference-count update.
- The deque keeps the lines sorted by arrival time, which makes finding the oldest one cheaper than scanning.
Show answer
Every slice builds a fresh 1000-element list and copies the references, so the list version does O(1000) work per line while the deque just drops one item from its head block in O(1). The hash table answer is tempting because dict-based structures do give O(1) operations, but a deque is a doubly linked chain of fixed-size blocks with no hashing involved, and both structures already hold lines in arrival order, so sorting plays no part.