Queue Patterns — First-In, First-Out Workflows
Learn how queues model real-world workflows, feed BFS, and support monotonic optimisations like sliding window maximum.
Problem Statement
Understand queue operations, circular queue implementations, and advanced patterns like monotonic queues to solve sliding window problems.
Why This Problem Matters
- Queues underpin BFS, scheduling, and streaming window problems—interview staples.
- Designing circular queues showcases low-level control when using fixed-size buffers.
- Monotonic queues illustrate how to keep track of extremes in O(1) amortised time.
Thought Process
Start with basic enqueue/dequeue semantics
Model FIFO behaviour explicitly, whether implemented with arrays, linked lists, or two stacks.
Highlight circular queue techniques
Use head/tail pointers modulo capacity to reuse space efficiently.
Introduce monotonic queues for sliding windows
Maintain elements in decreasing order so the front always holds the maximum.
Step-by-Step Reasoning
- Implement enqueue (push to tail) and dequeue (pop from head).
- Track size and capacity if bounded.
- For monotonic queue, pop from back while new value violates order.
- Drop expired indices from the front when they leave the window.
Dry Run
Sliding window maximum on [1,3,-1,-3,5,3,6,7], k = 3
Monotonic queue stores indices of decreasing values, producing maxima [3,3,5,5,6,7].
Circular queue of capacity 3
Enqueue 1,2,3 fills queue. Dequeue removes 1. Enqueue 4 wraps tail to index 0.
Complexity Analysis
Time
O(1) amortised per operation
Space
O(n)
Why
Each element enters and leaves the queue once; monotonic queues only push/pop each element a bounded number of times.
Annotated Solution
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class SlidingWindowQueues {
private static class MonotonicQueue {
private final Deque<Integer> deque = new ArrayDeque<>();
void push(int value) {
while (!deque.isEmpty() && deque.peekLast() < value) {
deque.removeLast();
}
deque.addLast(value);
}
void pop(int value) {
if (!deque.isEmpty() && deque.peekFirst() == value) {
deque.removeFirst();
}
}
int max() {
return deque.peekFirst();
}
}
public static List<Integer> slidingWindowMax(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i += 1) {
if (i >= k) {
window.pop(nums[i - k]);
}
window.push(nums[i]);
if (i >= k - 1) {
result.add(window.max());
}
}
return result;
}
}The monotonic queue keeps potential maxima in descending order. Removing expired values from the front maintains correctness.
Common Pitfalls
- Using plain arrays without managing head/tail leads to O(n) dequeues if you shift per operation.
- Forgetting to drop expired indices results in stale maxima.
- Mismanaging modulo arithmetic in circular queues causes overwrites.
Follow-Up Questions
- Implement a queue using two stacks to achieve amortised O(1) operations.
- Discuss lock-free queue implementations for multi-threaded environments.
- Explain how to extend monotonic queues to track minima simultaneously.