FIFO structures powering BFS, level order traversal, and sliding window maximum.
A queue (FIFO) processes elements in the order they arrive. It is the backbone of BFS. A deque (double-ended queue) allows push/pop from both ends in O(1), enabling the sliding window maximum pattern and palindrome checks.
Enqueue/Dequeue O(1)
O(n) for n elements
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when you need to process a tree or graph one level at a time, such as when computing level averages, right-side views, or shortest path step counts
Add the root to the queue, then in each outer loop iteration snapshot the current queue length to determine how many nodes belong to the current level. This snapshot trick is essential because the queue keeps growing as you process each level.
Problem Binary Tree Level Order Traversal. Capture the queue length before the inner loop so you process exactly the nodes at the current depth.
// BFS level order — Binary Tree Level Order Traversal
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const level = [], size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}Use this when the graph has no edge weights and you need the minimum number of steps between two nodes
BFS explores nodes in exact order of their distance from the source, so the first time you reach the target is always the shortest path. Each level increment corresponds to one additional step.
Problem Shortest Path in Binary Matrix. Start BFS from (0, 0) and expand to all valid 8-directional neighbors, tracking the step count as the level.
// BFS shortest path — Shortest Path in Binary Matrix
function shortestPathBinaryMatrix(grid) {
const n = grid.length;
if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
const queue = [[0, 0, 1]];
grid[0][0] = 1;
while (queue.length) {
const [r, c, dist] = queue.shift();
if (r === n-1 && c === n-1) return dist;
for (const [dr, dc] of dirs) {
const nr = r+dr, nc = c+dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
grid[nr][nc] = 1; queue.push([nr, nc, dist+1]);
}
}
}
return -1;
}Use this when the problem has multiple valid starting points and you want to find the distance from each cell to the nearest source
Instead of running BFS from every source individually, add all sources to the queue at once with distance zero and let BFS spread outward. This correctly computes the minimum distance to any source in one pass.
Problem 01 Matrix. Initialize all zeroes in the queue at distance 0, then BFS outward to assign distances to all 1-cells.
// Multi-source BFS — 01 Matrix (distance to nearest 0)
function updateMatrix(mat) {
const rows = mat.length, cols = mat[0].length;
const dist = mat.map(row => row.map(v => v === 0 ? 0 : Infinity));
const queue = [];
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (mat[r][c] === 0) queue.push([r, c]);
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of dirs) {
const nr = r+dr, nc = c+dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]);
}
}
}
return dist;
}Use this when you need the maximum (or minimum) of every fixed-size window in a single O(n) pass
A deque of indices maintains a decreasing order of values: before pushing a new index, remove from the back any index whose value is smaller than the new element. Remove from the front any index that has slid out of the window. The front is always the index of the current window maximum.
Problem Sliding Window Maximum. For each new element, evict stale left indices from the front, prune smaller values from the back, then record the front as the window maximum once the window is full.
// Deque sliding window max — Sliding Window Maximum
function maxSlidingWindow(nums, k) {
const deque = [], result = [];
for (let i = 0; i < nums.length; i++) {
// remove out-of-window indices from front
while (deque.length && deque[0] < i - k + 1) deque.shift();
// remove smaller values from back
while (deque.length && nums[deque.at(-1)] <= nums[i]) deque.pop();
deque.push(i);
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}Use this when you need a fixed-size queue that reuses memory without shifting elements, making all operations O(1)
Track head, tail, and count (or use modular arithmetic). Enqueue writes at the tail index and advances tail mod capacity; dequeue reads the head index and advances head.
Problem Design Circular Queue. Use an array with head and size variables so enqueue and dequeue never require memory allocation. class MyCircularQueue { constructor(k) { this.data = new Array(k); this.head = 0; this.size = 0; this.cap = k; } enQueue(val) { if (this.isFull()) return false; this.data[(this.head + this.size) % this.cap] = val; this.size++; return true; } deQueue() { if (this.isEmpty()) return false; this.head = (this.head + 1) % this.cap; this.size--; return true; } Front() { return this.isEmpty() ? -1 : this.data[this.head]; } Rear() { return this.isEmpty() ? -1 : this.data[(this.head + this.size - 1) % this.cap]; } isEmpty() { return this.size === 0; } isFull() { return this.size === this.cap; } }
// Circular queue — Design Circular Queue
class MyCircularQueue {
constructor(k) { this.data = new Array(k); this.head = 0; this.size = 0; this.cap = k; }
enQueue(val) { if (this.isFull()) return false; this.data[(this.head + this.size) % this.cap] = val; this.size++; return true; }
deQueue() { if (this.isEmpty()) return false; this.head = (this.head + 1) % this.cap; this.size--; return true; }
Front() { return this.isEmpty() ? -1 : this.data[this.head]; }
Rear() { return this.isEmpty() ? -1 : this.data[(this.head + this.size - 1) % this.cap]; }
isEmpty() { return this.size === 0; }
isFull() { return this.size === this.cap; }
}Use this when the problem models a process that handles requests or tasks in order, such as a CPU scheduler, print queue, or task reordering problem
A queue naturally models FIFO processing, and you can extend it with priorities or round-robin logic using index tracking.
Problem Task Scheduler. Simulate using a queue of tasks by cycle: always process the highest-frequency task first, then fill idle slots, tracking how many cycles were used.
// Queue task simulation — Task Scheduler
function leastInterval(tasks, n) {
const freq = new Array(26).fill(0);
for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
freq.sort((a, b) => b - a);
const maxFreq = freq[0];
const maxCount = freq.filter(f => f === maxFreq).length;
const intervals = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(intervals, tasks.length);
}