Queue

Queue & Deque — FIFO

First In, First Out. Essential for BFS. Always use deque, never list.pop(0) which is O(n).

Queue Operations (FIFO)
FRONT (dequeue here) → → → BACK (enqueue here)
Queue is empty. Enqueue some values!

Why Deque, Not List?

Operationlistcollections.deque
Add to backO(1)O(1)
Remove from frontO(n) — shifts all!O(1) ✓
Add to frontO(n)O(1)
Remove from backO(1)O(1)
Never do this
queue.pop(0) — shifts all n elements left. Always use from collections import deque and deque.popleft().
BFS — Level Order Traversal

BFS explores level by level using a queue. Each node is processed before its children are explored.

Queue: []
Press Animate BFS to see level-order traversal.

BFS = Shortest Path (Unweighted)

Why BFS gives shortest path
BFS explores all nodes at distance d before any node at distance d+1. So the first time you reach a node, it's via the shortest path. DFS does NOT guarantee this.
Mark visited BEFORE enqueuing
Mark a node visited when you ADD it to the queue, not when you process it. Otherwise the same node gets added multiple times, causing incorrect results.

Deque Operations

from collections import deque

q = deque()
q.append(x)      # enqueue back — O(1)
q.popleft()      # dequeue front — O(1)
q.appendleft(x)  # add front — O(1)
q.pop()          # remove back — O(1)
q[0]             # peek front — O(1)
q[-1]            # peek back — O(1)
not q            # True if empty

# BFS template (graph)
def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        # process node
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)   # mark BEFORE enqueue
                q.append(nei)

Level Order Tree Traversal

def level_order(root):
    if not root: return []
    q, res = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):  # process one level
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

LeetCode Problems

  • EasyBinary Tree Level Order TraversalBFS with level grouping
  • EasyNumber of IslandsBFS flood fill
  • MediumRotting OrangesMulti-source BFS
  • MediumWalls and GatesMulti-source BFS
  • MediumSliding Window MaximumMonotonic deque
  • HardShortest Path in Binary MatrixBFS on grid