Queues, deques and priority queues

A queue is a collection you take things out of in a defined order. Three orders matter: first-in-first-out, last-in-first-out, and smallest-first. Java has a structure for each, and one legacy class you should stop using. This lesson is the interfaces, the ring buffer and the binary heap that implement them, why iterating a PriorityQueue gives you nonsense, and a top-K problem worked through with its arithmetic.

#The Queue and Deque interfaces

Queue offers each operation in two flavours — one that throws on failure, one that returns a special value:

For an unbounded queue they behave the same except on empty. For a bounded one, offer returning false is how you learn it is full without an exception. Deque doubles the set: addFirst/addLast, pollFirst/pollLast, peekFirst/peekLast, plus push/pop as aliases for the first-end stack operations.

#ArrayDeque: the queue and the stack

ArrayDeque is a circular array: a head index, a tail index, and an Object[] that wraps around. Both ends are O(1); memory is contiguous. It is the correct choice for a FIFO queue and for a LIFO stack.

Deque<Task> queue = new ArrayDeque<>();
queue.addLast(t);            // enqueue
Task next = queue.pollFirst(); // dequeue, null if empty
 
Deque<Frame> stack = new ArrayDeque<>();
stack.push(f);               // == addFirst
Frame top = stack.pop();     // == removeFirst, throws if empty

Two rules: it does not accept null (because poll uses null for "empty"), and it is not thread-safe.

#Under the hood: the ring buffer and the heap

ArrayDeque keeps head and tail as indices into one array and moves them with wrap-around arithmetic: addLast writes at tail and advances it (tail = (tail + 1) % length, done with a mask or a conditional); addFirst retreats head and writes there; pollFirst reads at head and advances it, nulling the slot so the element can be collected. Nothing shifts. When head meets tail the array is full: since Java 11 it grows by half (by 2 while small), copying the elements into a fresh array with head at 0. Iteration walks from head to tail with the same wrap, so it is in queue order and, like every array, one cache line per sixteen references.

PriorityQueue is a binary min-heap stored in an array with no pointers: the children of index i are 2i+1 and 2i+2, the parent is (i−1)/2. offer appends at the end and sifts up, swapping with the parent while smaller: O(log n). poll takes index 0, moves the last element there, and sifts down, swapping with the smaller child while larger: O(log n). peek is index 0. The heap invariant is only "every parent ≤ its children"; siblings are unordered, which is why the array, and therefore iterator(), is not sorted. Building a queue from a collection uses heapify, which is O(n) rather than n × log n. There is no decreaseKey: remove(Object) is a linear scan followed by a sift, and contains is a scan.

#Do not use Stack or LinkedList

java.util.Stack extends Vector: every method is synchronized, it exposes index-based access that a stack should not have, and it iterates bottom-to-top, which is not what anyone wants from a stack. It exists for compatibility. LinkedList implements Deque correctly but pays a 24-byte node allocation per element and pointer-chasing on every operation. ArrayDeque is faster than both in every published benchmark.

#PriorityQueue: a binary heap

A PriorityQueue returns the smallest element first, by natural order or a comparator. Iterating it does not give sorted order — the heap property only guarantees the root is smallest — so for (x : pq) is a common bug. Drain it with poll to get sorted output.

PriorityQueue<Job> byDeadline = new PriorityQueue<>(Comparator.comparing(Job::deadline));
byDeadline.offer(job);
Job urgent = byDeadline.poll();      // the earliest deadline
 
// A max-heap is a min-heap with a reversed comparator
PriorityQueue<Integer> largestFirst = new PriorityQueue<>(Comparator.reverseOrder());

Classic uses: scheduling by deadline, Dijkstra's algorithm, top-K of a stream, merging K sorted sources. If you need to update a priority, remove and re-add, or use an indexed heap from a library.

#Walkthrough: the ten largest of a hundred million

A log pipeline needs the 10 slowest requests out of 100 million latency samples streaming past. Three approaches, with the arithmetic:

1. Sort everything. Store 100 million longs (800 MB) and sort: n log n ≈ 2.7 billion comparisons, several seconds, and the memory is the deal-breaker.
2. Keep the top 10 in a sorted list. For each sample, insert into a 10-element list and drop the smallest: up to 10 comparisons and a shift per sample, 1 billion operations, fine for K=10 and O(n × K) in general, which fails at K=10,000.
3. A min-heap of size K. PriorityQueue<Long> top = new PriorityQueue<>(10). For each sample: if the heap has fewer than 10, offer; otherwise, if the sample is larger than peek() (the smallest of the current top 10), poll and offer. The heap holds the ten largest seen so far, and its root is the threshold. Most samples fail the peek comparison in one step; the ones that pass cost log₂(10) ≈ 4 swaps. Memory: 10 boxed Longs. Time: about 100 million comparisons and a few thousand heap operations: well under a second, O(n log K), and K=10,000 costs 14 swaps instead of 4.
4. Why a min-heap for the maximum. The question "should this sample enter the top 10" is "is it bigger than the smallest of the ten", and the smallest is what a min-heap keeps at the root in O(1). A max-heap would put the largest at the root, which answers a question nobody asked. Drain with poll at the end for the ten in ascending order.

The same shape solves "K nearest", "K most frequent" (with a count map first) and "merge K sorted streams" (a heap of K heads).

#Blocking queues

For producer–consumer across threads, java.util.concurrent has queues whose put blocks when full and take blocks when empty:

The unbounded default matters: a thread pool fed by an unbounded LinkedBlockingQueue never rejects work, so a slow consumer means a queue that grows until the heap is gone. The concurrency course returns to this; for now, know that "bounded" is a decision you must make explicitly.

#Choosing

#Try it yourself

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
System.out.println(pq);
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) sb.append(pq.poll()).append(' ');
System.out.println(sb);

#Misconceptions

• "A PriorityQueue is a sorted collection." It is a heap: only the root is guaranteed. Iteration is array order; poll is the only sorted access.
• "Stack is the stack class." It is a synchronised Vector with the wrong iteration order, kept for compatibility. ArrayDeque with push/pop is the stack.
• "Removing from the front of a queue shifts everything." In an ArrayDeque it advances head; nothing moves. Only ArrayList.remove(0) shifts.
• "Top-K needs a max-heap." It needs a min-heap of size K, whose root is the current threshold for entry.
• "offer and add are the same." On a bounded queue add throws when full and offer returns false. Choose the one whose failure mode you will actually handle.

#Going deeper

• ArrayDeque source: addLast, pollFirst, grow and the inc/dec helpers that do the wrap.
• PriorityQueue source: siftUp, siftDown, heapify, and the class comment on iteration order.
• Sedgewick and Wayne, Algorithms, chapter 2.4 (priority queues), for heap analysis with pictures.
• DelayQueue source, for the leader-follower pattern that keeps only one thread sleeping.
• java.util.Stack Javadoc, whose first paragraph tells you to use Deque instead.