TopolearnThese patterns show up constantly in interviews and in real code that processes streams or graphs.
Four patterns cover most uses of deque beyond a plain queue.
Breadth-first search. Put the start node in a deque; repeatedly popleft a node and append its unvisited neighbours. Because the queue is FIFO, nodes are visited in order of distance, so BFS finds shortest paths in unweighted graphs.
Sliding windows. A deque(maxlen=k) holds the last k values of a stream for moving averages or rolling checks. For the classic "maximum of every window" problem, a deque of indices kept in decreasing value order gives O(n) overall.
Round robin. d.rotate(n) rotates right by n steps (negative rotates left). Or pop an item from the left, process it, and append it back at the right, which cycles fairly between tasks or iterators until each is exhausted.
Tail of a file. deque(open(path), maxlen=10) reads through the file once and keeps only the last ten lines, using constant memory.
Since deque iteration over a changing deque raises RuntimeError, collect changes separately or loop with while d: and popleft.
Example
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []}
def shortest_path(start, goal):
queue, came_from = deque([start]), {start: None}
while queue:
node = queue.popleft()
if node == goal:
path = []
while node:
path.append(node)
node = came_from[node]
return path[::-1]
for nxt in graph[node]:
if nxt not in came_from:
came_from[nxt] = node
queue.append(nxt)
print(shortest_path("A", "F")) # ['A', 'B', 'D', 'F']
window = deque(maxlen=3) # moving average of the last 3 values
for x in [3, 6, 9, 12]:
window.append(x)
print(list(window), sum(window) / len(window)) # [6, 9, 12] 9.0
d = deque([1, 2, 3, 4]); d.rotate(1)
print(d) # deque([4, 1, 2, 3])Remember
- BFS uses a deque as a FIFO queue to visit nodes in distance order
deque(maxlen=k)gives a sliding window or a tail of a streamrotate(n)shifts elements cyclically for round-robin scheduling
Watch out for
- Implementing BFS with
list.pop(0), turning an O(V+E) algorithm into a quadratic one.