🎟️ Queue

One-line summary: First-in first-out (FIFO) — the backbone of BFS, level-order traversal, and rate-limiting.

---

Concept

A queue supports:

• enqueue(x) — add to rear: O(1)
• dequeue() — remove from front: O(1)
• peek() — read front: O(1)

Variants: circular buffer (fixed-size), deque (double-ended), monotonic deque (sliding window max).

---

Diagram

---

Time & Space Complexity

Operation	Time	Space
Enqueue / Dequeue	O(1)	O(1)
BFS traversal	O(V+E)	O(V)

---

Common Patterns

BFS Level Order

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;
}

Monotonic Deque (Sliding Window Max)

function maxSlidingWindow(nums, k) {
  const deque = [],
    result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

---

Pitfalls

• JS array.shift() is O(n) — for performance use a pointer-based deque or linked list
• BFS: process all nodes at current level before moving to next (use size snapshot)

---

Practice Problems

Easy Problems

Problem	Difficulty	Solution
LC 225 — Implement Stack using Queues	Easy
LC 232 — Implement Queue using Stacks	Easy
LC 346 — Moving Average from Data Stream	Easy
LC 637 — Average of Levels in Binary Tree	Easy
LC 933 — Number of Recent Calls	Easy
LC 1700 — Number of Students Unable to Eat Lunch	Easy
LC 1971 — Find if Path Exists in Graph	Easy
LC 2073 — Time Needed to Buy Tickets	Easy
CC — Queue Operations (QUEUEOP)	Easy
CC — Basic Queue (BASICQUE)	Easy
CC — Queue Implementation (QUEIMPL)	Easy

Medium Problems

Problem	Difficulty	Solution
LC 102 — Binary Tree Level Order Traversal	Medium
LC 103 — Binary Tree Zigzag Level Order	Medium
LC 107 — Binary Tree Level Order Traversal II	Medium
LC 116 — Populating Next Right Pointers in Each Node	Medium
LC 117 — Populating Next Right Pointers in Each Node II	Medium
LC 199 — Binary Tree Right Side View	Medium
LC 200 — Number of Islands	Medium
LC 286 — Walls and Gates	Medium
LC 429 — N-ary Tree Level Order Traversal	Medium
LC 515 — Find Largest Value in Each Tree Row	Medium
LC 542 — 01 Matrix	Medium
LC 622 — Design Circular Queue	Medium
LC 641 — Design Circular Deque	Medium
LC 649 — Dota2 Senate	Medium
LC 752 — Open the Lock	Medium
LC 909 — Snakes and Ladders	Medium
LC 950 — Reveal Cards in Increasing Order	Medium
LC 994 — Rotting Oranges	Medium
LC 1091 — Shortest Path in Binary Matrix	Medium
LC 1162 — As Far from Land as Possible	Medium
LC 1161 — Maximum Level Sum of a Binary Tree	Medium
LC 1302 — Deepest Leaves Sum	Medium
LC 1609 — Even Odd Tree	Medium
LC 1823 — Find the Winner of the Circular Game	Medium
LC 1926 — Nearest Exit from Entrance in Maze	Medium
CC — Processing a Queue (QUEUE2)	Medium
CC — Circular Queue (CIRCQUE)	Medium
CC — BFS Problems (BFSPROB)	Medium
CC — Level Order Traversal (LEVELORD)	Medium

Hard Problems

Problem	Difficulty	Solution
LC 126 — Word Ladder II	Hard
LC 127 — Word Ladder	Hard
LC 239 — Sliding Window Maximum	Hard
LC 317 — Shortest Distance from All Buildings	Hard
LC 407 — Trapping Rain Water II	Hard
LC 815 — Bus Routes	Hard
LC 847 — Shortest Path Visiting All Nodes	Hard
LC 864 — Shortest Path to Get All Keys	Hard
LC 1036 — Escape a Large Maze	Hard
LC 1263 — Minimum Moves to Move a Box to Their Target Location	Hard
LC 1293 — Shortest Path in a Grid with Obstacles Elimination	Hard
LC 1345 — Jump Game IV	Hard
LC 1368 — Minimum Cost to Make at Least One Valid Path in a Grid	Hard
LC 1728 — Cat and Mouse II	Hard
CC — Advanced BFS (ADVBFS)	Hard
CC — Multi-source BFS (MULTIBFS)	Hard
CC — Bidirectional BFS (BIBFS)	Hard

---

Related Topics

• Graphs — BFS uses a queue
• Stack — DFS counterpart
• Sliding Window — monotonic deque

← Back to Home · © sparshjaswal