Interview frequency: ⭐⭐⭐⭐☆
Today we'll learn queues from a real coding interview perspective, not just definitions.
This topic is important because queues are the foundation of BFS (Breadth-First Search), which is used in trees, graphs, grids, shortest-path problems, and many coding assessments.
1. What is a Queue?
A queue follows FIFO:
First In, First Out.
Think of people standing in a line. The person who enters first leaves first.
Queue visualization
10
20
30
← Dequeue (front)
Enqueue (rear) →
Basic operations
Meaning
Enqueue
Add element
Dequeue
Remove front element
Front / Peek
See first element
IsEmpty
Check if empty
2. Python Queue: deque
Use collections.deque for an efficient queue.
Python
Run
from collections import deque
q = deque()
q.append(10)
q.append(20)
q.append(30)
print(q.popleft()) # 10
print(q) # deque([20, 30])
Complexity
Time
append()
O(1)
popleft()
O(1)
q[0]
O(1)
len(q)
O(1)
Important interview mistake
Don't use:
Python
Run
q.pop(0)
Python lists don't support pop(0) efficiently. Removing the first element requires shifting the remaining elements, which is O(n).
Use:
Python
Run
q.popleft()
3. Queue vs Stack
| |
Stack
Queue
Rule
LIFO
FIFO
Python
list
deque
Add
append()
append()
Remove
pop()
popleft()
Common use
DFS, brackets
BFS, scheduling
Remember: DFS usually explores deeply; BFS explores level by level.
4. BFS — The Most Important Part ⭐⭐⭐⭐⭐
BFS stands for Breadth-First Search.
It explores all nodes at the current distance or level before moving to the next.
Example tree:
1
/ \
2 3
/ \ \
4 5 6
BFS order:
1 → 2 → 3 → 4 → 5 → 6
Level by level:
Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]
A queue makes this natural.
5. Interview Problem: Binary Tree Level Order Traversal
LeetCode 102 — Medium
Problem
Given the root of a binary tree, return its level-order traversal.
Expected:
Python
Run
[[1],[2,3],[4,5,6]]Interview thinking
When you see:
Level order
Minimum number of steps
Shortest path in an unweighted graph
Nearest / closest
Spread to neighboring cells
Think:
BFS + Queue
Python solution
Python
Run
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
Complexity
For n nodes:
Time: O(n) — each node is processed once.
Space: O(n) — queue and output can hold O(n) elements.
Important trick: for _ in range(len(q))
This processes exactly the nodes in the current level.
Why not simply use:
Python
Run
while q:
You can, but then you need another way to separate levels. The len(q) trick is the standard interview approach.
6. BFS on a Grid
This is extremely common in online assessments.
Problem: Number of Islands
LeetCode 200 — Medium
Given a grid:
1 1 0 0
1 0 0 1
0 0 1 1
1 0 0 0
1= Land0= Water
Find the number of islands.
An island consists of connected land cells in the four directions:
Up
Down
Left
Right
Interview approach
Visit every cell.
If it's land (
1), you found a new island.Start BFS to visit all connected land.
Mark visited cells.
Continue scanning.
Python solution
Python
Run
from collections import deque
def num_islands(grid):
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
islands += 1
q = deque([(r, c)])
grid[r][c] = "0"
while q:
x, y = q.popleft()
for dx, dy in [
(1, 0),
(-1, 0),
(0, 1),
(0, -1)
]:
nx = x + dx
ny = y + dy
if (
0 <= nx < rows
and 0 <= ny < cols
and grid[nx][ny] == "1"
):
grid[nx][ny] = "0"
q.append((nx, ny))
return islands
Complexity
Let the grid have R rows and C columns.
Time: O(R × C)
Space: O(R × C) worst case for the queue.
Interview insight
Mark a cell visited when you add it to the queue, not when you remove it. This prevents adding the same cell multiple times.
7. BFS for Shortest Path
This is a very important pattern.
Example
You have a grid with obstacles:
S . . #
# . . #
# . . E
Find the minimum number of steps from S to E.
If every move costs exactly 1, BFS finds the shortest path.
Why?
BFS visits cells in order of distance:
Distance 0
↓
Distance 1
↓
Distance 2
↓
Distance 3
The first time you reach the destination, you have found a shortest path.
Important: This applies to unweighted graphs (or edges with equal cost). For weighted edges, use algorithms such as Dijkstra when appropriate.
8. Multi-Source BFS ⭐⭐⭐⭐☆
This is an advanced BFS pattern.
Instead of starting from one source, you start from multiple sources simultaneously.
Example: Rotting Oranges
LeetCode 994 — Medium
2 = Rotten orange
1 = Fresh orange
0 = Empty
2 1 1
1 1 0
0 1 1
Every minute, rotten oranges infect their adjacent fresh oranges.
Find the time until all oranges are rotten.
Interview clue
If the question says:
Spread simultaneously
Minimum minutes
Multiple starting points
Nearest distance from any source
Think:
Multi-Source BFS
Initialize the queue with every rotten orange, then process one level at a time.
9. BFS Template for Interviews
Tree or graph BFS
Python
Run
from collections import deque
def bfs(start):
q = deque([start])
visited = {start}
while q:
node = q.popleft()
for neighbor in neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
Grid BFS
Python
Run
from collections import deque
q = deque([(start_r, start_c)])
visited = {(start_r, start_c)}
while q:
r, c = q.popleft()
for dr, dc in directions:
nr = r + dr
nc = c + dc
# Check bounds and validity
# Mark visited
# Add to queue
10. How to Recognise BFS vs DFS
Preferred approach
Level order traversal
BFS
Shortest path, unweighted graph
BFS
Minimum number of moves
BFS
Spread in minutes
Multi-source BFS
Explore all connected components
BFS or DFS
Explore deep paths / backtracking
DFS
Tree height / recursive subtree calculations
Often DFS
Very important: BFS is not always the only correct solution. Some problems can be solved with either BFS or DFS.
11. Real Interview Problems to Practice
Easy
Binary Tree Level Order Traversal — LeetCode 102
Flood Fill — LeetCode 733
Medium
Number of Islands — LeetCode 200
Rotting Oranges — LeetCode 994
Shortest Path in Binary Matrix — LeetCode 1091
Open the Lock — LeetCode 752
Binary Tree Zigzag Level Order Traversal — LeetCode 103
Advanced
Word Ladder — LeetCode 127
01 Matrix — LeetCode 542
Walls and Gates — classic multi-source BFS problem
12. Exam Cheat Sheet
Queue
FIFO. Use deque in Python.
BFS
Explore level by level using a queue.
Grid problems
Use directions, bounds checks, and visited tracking.
Practice question
Try this before looking at the solution:
Rotting Oranges
Python
Run
grid = [
[2, 1, 1],
[1, 1, 0],
[0, 1, 1]
]
Return the minimum minutes required to rot all oranges. If impossible, return -1.
Hint: Use multi-source BFS.
Next topic: Linked Lists
We'll cover linked list structure, reversing a linked list, fast and slow pointers, detecting cycles, and the classic interview question Reverse Linked List.