Queue

Queue / Deque

Back to Index

FIFO (First In, First Out). The backbone of BFS. Use collections.deque in Python for O(1) pops from both ends.

Properties

• Enqueue (right) / Dequeue (left): O(1) with deque
• list.pop(0) is O(n) — always use deque for queues

from collections import deque
 
q = deque()
q.append(val)       # enqueue right
q.appendleft(val)   # enqueue left
q.popleft()         # dequeue left (O(1))
q.pop()             # dequeue right (O(1))
q[0]                # peek front

Deque as Sliding Window Maximum

A monotonic deque can track the maximum of a sliding window in O(1) amortized.

from collections import deque
 
dq = deque()  # stores indices, decreasing order of values
for i, num in enumerate(nums):
    while dq and nums[dq[-1]] < num:
        dq.pop()              # remove smaller elements from back
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()          # remove elements outside window
    if i >= k - 1:
        result.append(nums[dq[0]])  # front is always the max

Patterns That Use This

BFS — level-order traversal, shortest path Monotonic Stack — sliding window max/min uses a monotonic deque

---

Problems Using This Data Structure