Foundation · Module 11 · Lesson 2
Queue & circular queue
FIFO processing, ring buffers, and scheduling.
Lesson 59 of 123
1d streakInteractive Visualization
See how queue & circular queue works
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive data structure
Change the structure and watch the operation
Try an operation and connect the visible movement to its runtime cost.
The FIFO Principle & Circular Ring Buffer Architecture
A Queue enforces First-In, First-Out (FIFO): items are inserted at the rear (tail) and removed from the front (head). Think of a queue at a grocery store checkout: the first person in line is served first. Naive array implementations suffer because removing from index 0 requires shifting all elements ($O(n)$ time). A Circular Queue solves this by wrapping indices around using modulo arithmetic.
Capacity = 8 | Modulo Formula: nextIndex = (index + 1) % Capacity
[ 0 ] : 42 <-- head (front)
[ 7 ] [ 1 ] : 87
[ 6 ] [ 2 ] : 19
[ 5 ] [ 3 ] : 95 <-- tail points here
[ 4 ] : _
Enqueue (Insert at tail):
data[tail] = val;
tail = (tail + 1) % capacity;
Dequeue (Remove from head):
val = data[head];
head = (head + 1) % capacity;
Zero element shifting! Both operations execute in strictly O(1) time.public class MyCircularQueue {
private final int[] data;
private int head = 0;
private int tail = 0;
private int size = 0;
private final int capacity;
public MyCircularQueue(int k) {
this.capacity = k;
this.data = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) return false;
data[tail] = value;
tail = (tail + 1) % capacity;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
head = (head + 1) % capacity;
size--;
return true;
}
public int Front() { return isEmpty() ? -1 : data[head]; }
public int Rear() { return isEmpty() ? -1 : data[(tail - 1 + capacity) % capacity]; }
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == capacity; }
}Active Recall Checkpoint
In a circular queue without an explicit size counter, why can head == tail mean both EMPTY and FULL?
Hint: Consider how tail advances when elements are enqueued.
Show answer & explanation
When the queue is empty, head == tail. When capacity elements are enqueued, tail wraps completely around and equals head again. To resolve this ambiguity, implementations either maintain an explicit size variable or leave 1 slot unused so that (tail + 1) % capacity == head signals full.
Breadth-First Search (BFS) with Queues
Queues are the computational engine of Breadth-First Search (BFS). By processing nodes in order of arrival, a queue guarantees that all nodes at distance $d$ are explored before any node at distance $d + 1$, guaranteeing the shortest path in unweighted graphs and level-by-level tree traversals.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // Snapshot count for current level
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
levels.add(currentLevel);
}
return levels;
}Cost Model
Complexity & Trade-offs
When to use it
- Nested parsing, undo, arrival order, buffering, and nearest-greater queries.
- BFS frontiers and producer/consumer scheduling.
- Maintaining range extremes or constrained access.
Common mistakes
- Reading from an empty structure.
- Confusing the logical front with an array index in a circular buffer.
- Missing the amortized argument for transfers or monotonic pops.
Practice prompts
- Reproduce the worked Queue & circular queue example without looking at the trace.
- Change one input condition and explain whether the Queue & circular queue invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check