Queue Patterns — Micro Drills

Deque gives O(1) operations at both ends. Essential for BFS and sliding window.

from collections import deque
q = deque()
q.append(x)
q.popleft()

42 BFS level-order template 15s

Level-order BFS uses a queue with size tracking. Core pattern for tree breadth-first problems.

from collections import deque
q = deque([root])
while q:
    for _ in range(len(q)):
        node = q.popleft()
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)

43 Sliding window max setup 15s

Monotonic deque maintains window max in O(n). Used for sliding-window-maximum and similar.

from collections import deque
dq = deque()  # indices
for i, x in enumerate(a):
    while dq and dq[0] &lt; i - k + 1:
        dq.popleft()
    while dq and a[dq[-1]] &lt;= x:
        dq.pop()
    dq.append(i)
    if i &gt;= k - 1:
        result.append(a[dq[0]])

44 Rotate deque 5s

Deque rotation is a one-liner for circular shifts. Useful for array rotation problems.

from collections import deque
q = deque([1, 2, 3, 4])
q.rotate(k)

45 Queue from two stacks idea 15s

Two-stack queue amortizes to O(1) per operation. Classic data structure design question.

in_stack, out_stack = [], []

def enqueue(x):
    in_stack.append(x)

def dequeue():
    if not out_stack:
        while in_stack:
            out_stack.append(in_stack.pop())
    return out_stack.pop()