Queue
FIFO data structure powering BFS and level-order processing
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
A is a First-In, First-Out (FIFO) structure — the first element you add is the first one you get back. Think of a checkout line: first in, first served.
In Python, always use `collections.deque` for a queue. A plain list works but list.pop(0) is O(n) — it shifts every element. deque.popleft() is O(1).
from collections import deque
queue = deque()
queue.append(1) # enqueue → deque([1])
queue.append(2) # enqueue → deque([1, 2])
queue.append(3) # enqueue → deque([1, 2, 3])
front = queue[0] # peek front → 1 (unchanged)
val = queue.popleft() # dequeue → 1 (queue becomes deque([2, 3]))
val = queue.popleft() # dequeue → 2 (queue becomes deque([3]))Core operations — all O(1) with deque:
| Operation | Python (deque) | What it does | |---|---|---| | Enqueue | q.append(x) | Add to back | | Dequeue | q.popleft() | Remove + return front | | Peek | q[0] | Read front without removing | | Is empty | len(q) == 0 | Check if empty |
When to reach for a queue:
- BFS traversal — process nodes level by level (see {href=/atoms/algo-bfs})
- Level-order tree traversal — visit a tree one level at a time
- Sliding window minimum/maximum — monotonic deque pattern
- Task scheduling — process tasks in order received
BFS using a queue — the canonical pattern: ``python from collections import deque def bfs(graph, start): visited = {start} queue = deque([start]) # seed with start node while queue: node = queue.popleft() # FIFO — process in arrival order for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # explore later def bfs_shortest_path(graph, start, target): visited = {start} queue = deque([(start, 0)]) # (node, distance) while queue: node, dist = queue.popleft() if node == target: return dist for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist + 1)) return -1 # not found
Stack vs Queue — the key difference:
| | Stack | Queue | |---|---|---| | Order | LIFO — last in, first out | FIFO — first in, first out | | Python | list + append/pop | deque + append/popleft | | Traversal | DFS — goes deep first | BFS — goes wide first | | Use cases | DFS, undo, brackets | BFS, scheduling, level-order |
Examples
Level-order tree traversal
Recording len(queue) at the start of each outer loop iteration isolates exactly one level.
from collections import deque
def level_order(root):
"""Return nodes grouped by level."""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # nodes at this level
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
# Tree: 1
# / \
# 2 3
# / \
# 4 5
# → [[1], [2, 3], [4, 5]]Rotting Oranges — multi-source BFS
Seed the queue with all starting points at once — BFS naturally finds the shortest time from any of them.
from collections import deque
def oranges_rotting(grid):
"""Minimum minutes until all oranges rot (BFS from all rotten at once)."""
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # seed ALL rotten oranges
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue:
r, c, t = queue.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
minutes = max(minutes, t + 1)
queue.append((nr, nc, t + 1))
return minutes if fresh == 0 else -1How well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Linked List