Queues & Deques
FIFO for BFS and scheduling, and the double-ended queue that powers sliding-window-maximum in O(n).
On this page
If a stack is last-in-first-out, a queue is its mirror: first in, first out, like a line at a counter. Queues drive breadth-first search and scheduling, and their more flexible cousin - the deque (double-ended queue) - powers one of the slickest O(n) algorithms in interviews: sliding-window maximum.
FIFO and the BFS connection
A queue supports offer (add to the back) and poll (remove from the front), both O(1). In Java,
ArrayDeque is again the tool. The defining use is breadth-first search: process nodes in the
order they were discovered, which naturally explores a graph or tree level by level.
// BFS over a tree, level by level — the queue enforces FIFO order
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // front: oldest-discovered
process(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}Because the queue hands back nodes in discovery order, BFS finds the shortest path in an unweighted graph - the first time you reach a node is via the fewest edges. (You'll use this heavily in the graphs module.)
The deque: add and remove from both ends
A deque allows O(1) insertion and removal at both ends. That flexibility solves the sliding-window-maximum problem in O(n): as the window slides, keep a deque of indices whose values are in decreasing order, so the front is always the current maximum.
// maximum of each sliding window of size k — O(n)
int[] maxSlidingWindow(int[] a, int k) {
Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing
int[] result = new int[a.length - k + 1];
for (int i = 0; i < a.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() == i - k) dq.pollFirst(); // drop out-of-window
while (!dq.isEmpty() && a[dq.peekLast()] < a[i]) dq.pollLast(); // drop smaller values
dq.offerLast(i);
if (i >= k - 1) result[i - k + 1] = a[dq.peekFirst()]; // front = window max
}
return result;
}The insight: a value that's smaller than a later value in the window can never be the maximum, so we discard it immediately. Each index is added and removed once → O(n), beating the O(n·k) brute force of re-scanning every window.
One class, three roles
ArrayDeque is your stack, your queue, and your deque - push/pop for LIFO, offer/poll for FIFO, and
the First/Last variants for both ends. Prefer it over Stack (legacy, synchronized) and
LinkedList (slower, more memory). Knowing this one class covers most interview needs.
A single-file ticket queue is strict FIFO: whoever lined up first is served first, no cutting. A deque is a hallway with a door at each end - people can enter or leave from either side. That second door is what makes sliding-window maximum efficient: as the window moves, you evict stale people from the front (they've fallen out of the window) and shove aside anyone at the back who's 'shorter' than a newcomer (they can never be the tallest again), so the front of the hallway is always the current tallest.
The brute force for sliding-window maximum re-scans each window of size k, giving O(n·k). Explain how the monotonic deque achieves O(n), and why it's safe to discard an element that is smaller than a later one in the window.
Why is a queue (FIFO) the right structure for breadth-first search?
Key takeaways
- A queue is FIFO (offer to the back, poll from the front, both O(1)); it drives BFS and scheduling.
- BFS with a queue explores level by level and finds shortest paths in unweighted graphs.
- A deque adds/removes at both ends in O(1) - more flexible than a plain queue.
- A monotonic deque solves sliding-window maximum in O(n) by discarding values that can never be the max.
- ArrayDeque serves as stack, queue, and deque - prefer it over the legacy Stack and LinkedList.