Double-Ended Queues with collections.deque
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)When using a standard Python list as a queue, list.pop(0) is an O(N) operation that forces every remaining element to shift in memory. collections.deque (double-ended queue) is implemented as a doubly linked list of fixed-size 64-element memory blocks, providing true O(1) operations from both ends.
Why deque is Faster than list for Queues
Deque (double-ended queue) is a sequence that lets you add and remove items at both ends in O(1) time. Python provides it as collections.deque.
deque is optimized for fast pushes and pops from both ends.
from collections import deque
q = deque()q.append("Task 1") # Add to rightq.append("Task 2")q.appendleft("Urgent") # Add to left (O(1)!)
print("Popped left:", q.popleft()) # O(1) removal from frontprint("Remaining:", list(q))Example 1 · Job queue with a priority job
from collections import deque
# Simulating a job processing queuejobs = deque(["job_101", "job_102", "job_103"])jobs.appendleft("PRIORITY_VIP")
processed = []while jobs: current = jobs.popleft() processed.append(current)
print("Execution order:", processed)Execution order: ['PRIORITY_VIP', 'job_101', 'job_102', 'job_103']
What this code does
appendleftputs the VIP job at the front in O(1) time.popleftprocesses jobs in strict FIFO order in O(1) time.
popleft() and appendleft() take O(1) time regardless of whether the queue holds 10 or 10,000,000 items.
Circular Ring Buffers with maxlen
Ring buffer is a fixed-size queue where adding a new item to a full buffer drops the oldest one.
Pass maxlen to create a bounded queue. When full, adding new items automatically evicts elements from the opposite end.
recent_logs = deque(maxlen=3)for i in range(1, 6): recent_logs.append(f"Log {i}") print(list(recent_logs))Example 2 · Moving average of the last 3 readings
from collections import deque
window = deque(maxlen=3)for reading in [10, 20, 30, 40, 50]: window.append(reading) print(f"{list(window)} average {sum(window) / len(window):.1f}")[10] average 10.0 [10, 20] average 15.0 [10, 20, 30] average 20.0 [20, 30, 40] average 30.0 [30, 40, 50] average 40.0
What this code does
maxlen=3drops the oldest reading automatically.- Summing the window costs O(k), which is fine for a small k.
Notice how older logs are dropped automatically. This is ideal for rolling audit logs, sliding windows, and caching.
In-Place Rotation with rotate()
deque.rotate(n) rotates elements in place in O(k) time.
d = deque([1, 2, 3, 4, 5])d.rotate(2) # Shift right by 2print("Rotate +2:", list(d)) # [4, 5, 1, 2, 3]
d.rotate(-1) # Shift left by 1print("Rotate -1:", list(d)) # [5, 1, 2, 3, 4]Example 3 · Round-robin ticket assignment
from collections import deque
agents = deque(["Aarav", "Diya", "Arjun"])for ticket in range(1, 6): print(f"Ticket {ticket} -> {agents[0]}") agents.rotate(-1)Ticket 1 -> Aarav Ticket 2 -> Diya Ticket 3 -> Arjun Ticket 4 -> Aarav Ticket 5 -> Diya
What this code does
agents[0]is the agent whose turn it is.rotate(-1)moves that agent to the back, so the turns repeat in order.
rotate(k) moves k items from one end to the other, so it takes O(k) time, not O(N).
When to Use list vs deque
Overview of When to Use list vs deque:
- Use
listwhen you need fast random index access (list[5000]), binary search, or sorting in-place. - Use
dequewhen you need FIFO queues, BFS graph traversal, sliding windows, or fast head insertions.
Queue Patterns: BFS and Sliding Windows
Breadth-first search (BFS) visits nodes level by level. Its frontier is a first-in, first-out queue, so a deque fits.
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}queue = deque(["A"])seen = {"A"}order = []while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: if nxt not in seen: seen.add(nxt) queue.append(nxt)print(order)Example 4 · Fewest hops between stations
from collections import deque
routes = {"Central": ["Park", "Mall"], "Park": ["Airport"], "Mall": ["Airport", "Dock"], "Airport": [], "Dock": []}hops = {"Central": 0}queue = deque(["Central"])while queue: station = queue.popleft() for nxt in routes[station]: if nxt not in hops: hops[nxt] = hops[station] + 1 queue.append(nxt)print(hops){'Central': 0, 'Park': 1, 'Mall': 1, 'Airport': 2, 'Dock': 2}What this code does
- BFS reaches every station by the fewest hops first, so the first time you see a station is its shortest distance.
- The
hopsdictionary doubles as the visited set.
Example 5 · Maximum of every window
from collections import deque
def window_max(nums, k): dq = deque() result = [] for i, n in enumerate(nums): while dq and nums[dq[-1]] <= n: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: result.append(nums[dq[0]]) return result
print(window_max([4, 2, 12, 3, 8, 1], 3))[12, 12, 12, 8]
What this code does
- The deque keeps indexes whose values decrease from front to back, so the front is always the window maximum.
- Each index is added and removed once, giving O(N) in total instead of O(N * k).
Each node enters and leaves the queue once, so BFS runs in O(V + E). With list.pop(0) each removal would cost O(N).
Next step
Check your understanding
11 quick questions