TopolearnQueues, BFS, undo history and 'last N items' buffers all need cheap operations at both ends.
A list is fast at its end but slow at its start: lst.pop(0) and lst.insert(0, x) shift every element, which is O(n). A deque ("deck", double-ended queue) supports fast operations at both ends:
append(x)andappendleft(x)pop()andpopleft()extend(iterable)andextendleft(iterable)(which reverses the order)
That makes it the right structure for a FIFO queue: append to enqueue, popleft to dequeue.
With maxlen, a deque is a bounded buffer: deque(maxlen=3) keeps only the last three items, automatically discarding from the opposite end when you append. It's ideal for "the last N log lines" or a moving window.
A deque supports len, iteration, in, indexing (d[0], d[-1]) and clear. Indexing near the ends is fast, but access in the middle is O(n), and slicing isn't supported. If you need random access more than end operations, stay with a list.
Popping from an empty deque raises IndexError; check if d: first.
For queues shared between threads, use queue.Queue, which adds blocking get and put with timeouts; for asyncio, asyncio.Queue.
Example
from collections import deque
tasks = deque(["a", "b"])
tasks.append("c") # enqueue at the right
tasks.appendleft("urgent") # jump the queue
print(tasks.popleft()) # urgent
print(list(tasks)) # ['a', 'b', 'c']
recent = deque(maxlen=3)
for line in ["l1", "l2", "l3", "l4", "l5"]:
recent.append(line)
print(list(recent)) # ['l3', 'l4', 'l5']
print(recent[0], recent[-1]) # l3 l5
d = deque()
d.extendleft([1, 2, 3])
print(d) # deque([3, 2, 1])Remember
- deque appends and pops at both ends in O(1)
maxlenkeeps only the most recent N items- Use
queue.Queuefor producer/consumer queues between threads
Watch out for
- Using
list.pop(0)as a queue on large lists, which is O(n) per pop.