Queues & Deques
FIFO für BFS und Scheduling, und die doppelendige Queue, die Sliding-Window-Maximum in O(n) ermöglicht.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.