Queues, Deques and Priority Queues

Ends-first data structures, why ArrayDeque replaced Stack, and how a priority queue really orders.

Advanced11 min read

Read these first

The Collections Framework

Why this matters

ArrayDeque is the correct replacement for both Stack and LinkedList, and most code has not caught up.
Queue offers two methods for every operation — one throwing, one returning a sentinel — and picking the wrong one produces either noisy exceptions or silently ignored failures.
PriorityQueue's iteration order surprises nearly everyone the first time they print one.

Queue and Deque

Queue — FIFO

offer() → tail

poll() ← head

Deque — both ends

addFirst / addLast

pollFirst / pollLast

PriorityQueue — heap

Smallest leaves firstOrder of arrival ignored

Iteration order is not sorted — only polling is.

A queue serves the front, a deque serves either end, and a priority queue ignores arrival order and serves the smallest element first.

Queue is first-in-first-out. You add at the tail and remove from the head.
Deque — double-ended queue — allows adding and removing at both ends, so it serves as a queue and a stack.
ArrayDeque is a circular array implementation. It is the right default for both roles.
PriorityQueue is a binary heap; the head is always the smallest element by the ordering, not the oldest.

Two methods for every operation

Each queue operation comes in a throwing form and a sentinel-returning form.

Aspect	Operation	Throwing vs returning
Add to tail	add(e) — throws if capacity-bound and full	offer(e) — returns false
Remove from head	remove() — throws NoSuchElementException	poll() — returns null
Inspect head	element() — throws NoSuchElementException	peek() — returns null

Add to tail
Operationadd(e) — throws if capacity-bound and full
Throwing vs returningoffer(e) — returns false
Remove from head
Operationremove() — throws NoSuchElementException
Throwing vs returningpoll() — returns null
Inspect head
Operationelement() — throws NoSuchElementException
Throwing vs returningpeek() — returns null

Prefer the sentinel forms. An empty queue is a normal state, not an error.

Java

Queue<String> tasks = new ArrayDeque<>();

tasks.offer("compile");
tasks.offer("test");
tasks.offer("deploy");

System.out.println(tasks.peek());     // compile — look without removing
System.out.println(tasks.poll());     // compile — removed
System.out.println(tasks.size());     // 2

while (!tasks.isEmpty()) {
    System.out.println("Running " + tasks.poll());
}

System.out.println(tasks.poll());     // null — no exception

ArrayDeque as a stack

Java

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);          // addFirst
stack.push(2);
stack.push(3);

System.out.println(stack.peek());    // 3 — peekFirst
System.out.println(stack.pop());     // 3 — removeFirst
System.out.println(stack);           // [2, 1] — head first, so top first

Because push and pop both work at the head, last-in-first-out falls out naturally.

Aspect	ArrayDeque	java.util.Stack
Backing structure	Circular array	Vector — synchronised
Locking	None	Every method, even single-threaded
Indexed access	Not exposed	Inherited from Vector — a design leak
Iteration order	Head to tail, so top first	Bottom to top — the reverse of what you expect
Recommended	Yes	No — legacy since Java 1.0

Backing structure
ArrayDequeCircular array
java.util.StackVector — synchronised
Locking
ArrayDequeNone
java.util.StackEvery method, even single-threaded
Indexed access
ArrayDequeNot exposed
java.util.StackInherited from Vector — a design leak
Iteration order
ArrayDequeHead to tail, so top first
java.util.StackBottom to top — the reverse of what you expect
Recommended
ArrayDequeYes
java.util.StackNo — legacy since Java 1.0

Stack's iteration order being bottom-to-top is a genuine trap in otherwise correct-looking code.

PriorityQueue

Elements come out in priority order, smallest first by default. It is a binary heap, not a sorted list.

Java

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.addAll(List.of(50, 10, 40, 20, 30));

System.out.println(queue.peek());    // 10 — the smallest

while (!queue.isEmpty()) {
    System.out.print(queue.poll() + " ");   // 10 20 30 40 50
}

Java

// Largest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Ordered by a field, with a tie-breaker
PriorityQueue<Task> byPriority = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority)
                  .thenComparing(Task::createdAt));

Costs

offer and poll are O(log n) — the heap sifts the element up or down.
peek is O(1).
contains and remove(Object) are O(n) — there is no index to search by.
It is unbounded and grows as needed, and it rejects null.

A representative use: keep the k largest items from a large stream using a min-heap of size k.

Java

PriorityQueue<Integer> topK = new PriorityQueue<>();     // min-heap
for (int value : hugeStream) {
    topK.offer(value);
    if (topK.size() > k) {
        topK.poll();                 // drop the smallest, keeping the k largest
    }
}

This uses O(k) memory rather than sorting the whole input, which is the standard answer to "top k elements" problems.

Blocking queues

For producer-consumer work across threads, java.util.concurrent adds queues that block instead of returning null.

Java

BlockingQueue<Task> pipeline = new LinkedBlockingQueue<>(100);   // bounded

// Producer: waits if the queue is full
pipeline.put(task);

// Consumer: waits if the queue is empty
Task next = pipeline.take();

// With a timeout, when waiting forever is not acceptable
Task maybe = pipeline.poll(5, TimeUnit.SECONDS);     // null if nothing arrives

The main variants

ArrayBlockingQueue — fixed capacity, a single lock, backed by an array.
LinkedBlockingQueue — optionally bounded, separate locks for head and tail so producers and consumers contend less.
PriorityBlockingQueue — unbounded, ordered by priority.
SynchronousQueue — zero capacity; each put waits for a matching take. A direct hand-off.
DelayQueue — elements only become available once their delay expires. Useful for scheduling.

Common misreadings

"LinkedList is the queue implementation." It implements Deque, but ArrayDeque is faster for every queue and stack operation.
"Stack is fine for a stack." Its iteration order is bottom-to-top and every method is synchronised. Use ArrayDeque.
"A PriorityQueue is sorted." Only the head is guaranteed. Iteration reflects the heap array.
"add and offer are the same." For unbounded queues they behave alike, but offer returns false where add throws.
"poll on an empty queue throws." It returns null; remove() is the throwing form.
"ArrayDeque accepts nulls." It does not, because null is the sentinel meaning "empty".

Quick recall

Everything you need if you only revisit this box.

Queue is FIFO at the ends; Deque works at both ends and serves as a stack too.
Prefer the sentinel methods — offer, poll, peek — over add, remove, element.
ArrayDeque replaces both Stack and LinkedList. Stack is synchronised and iterates bottom-to-top.
PriorityQueue is a binary heap: O(log n) offer and poll, O(1) peek, O(n) contains, and iteration is not sorted.
A size-k min-heap solves "top k" in O(k) memory.
Blocking queues make producer-consumer work safe: put and take block, and poll accepts a timeout.
Bound your queues — an unbounded queue in front of a slow consumer hides the problem until the heap runs out.
Neither ArrayDeque nor PriorityQueue accepts null.

Test yourself

Answer these before moving on — recall is what makes it stick.