[Advanced Java] Queue, Deque, Stack and PriorityQueue in Java

A List lets you touch any element at any position. The four types in this article do the opposite: each one restricts where you are allowed to insert and where you are allowed to take, and that restriction is the whole feature. A Queue gives you the front, a Deque gives you both ends, and a PriorityQueue gives you the smallest element under some ordering.

Those restrictions come with a contract that is easy to use wrongly, because almost every operation exists twice under two different names with two different failure behaviours. This article covers that contract method by method, the legacy Stack class and the specific way its design leaks, and the single most common misunderstanding in the whole framework — that a PriorityQueue holds a sorted collection. It does not.

Every line of output, every exception and every comparison count below was produced by compiling and running the code on OpenJDK 21.0.6. No wall-clock timings appear anywhere; where cost matters it is expressed structurally, as counted comparisons and counted array copies.

Where these four types sit

Queue is an interface directly under Collection. Deque extends Queue, and in Java 21 it also extends SequencedCollection. ArrayDeque and LinkedList implement Deque; PriorityQueue implements Queue through AbstractQueue; Stack is the odd one out and extends Vector.

import java.util.*;

public class Hierarchy {
    static void show(Class<?> c) {
        System.out.printf("%-16s extends %-22s implements %s%n",
            c.getSimpleName(),
            c.getSuperclass() == null ? "-" : c.getSuperclass().getSimpleName(),
            Arrays.stream(c.getInterfaces()).map(Class::getSimpleName).toList());
    }
    public static void main(String[] args) {
        show(ArrayDeque.class);
        show(LinkedList.class);
        show(PriorityQueue.class);
        show(Stack.class);
        System.out.println();
        System.out.println("Queue interfaces:  " + Arrays.toString(Queue.class.getInterfaces()));
        System.out.println("Deque interfaces:  " + Arrays.toString(Deque.class.getInterfaces()));
        System.out.println("ArrayDeque is a List? " + List.class.isAssignableFrom(ArrayDeque.class));
        System.out.println("Stack is a List?   " + List.class.isAssignableFrom(Stack.class));
    }
}

ArrayDeque       extends AbstractCollection     implements [Deque, Cloneable, Serializable]
LinkedList       extends AbstractSequentialList implements [List, Deque, Cloneable, Serializable]
PriorityQueue    extends AbstractQueue          implements [Serializable]
Stack            extends Vector                 implements []

Queue interfaces:  [interface java.util.Collection]
Deque interfaces:  [interface java.util.Queue, interface java.util.SequencedCollection]
ArrayDeque is a List? false
Stack is a List?   true

Two lines there are worth holding on to. ArrayDeque is not a List, so it has no get(i) and no add(i, e) — the restriction is enforced by the type. Stack is a List, which is the entire subject of a later section.

Two families of Queue methods: throw, or return a special value

Queue declares six methods, and they are three operations written twice. Insert, remove and examine each come in a version that throws when it cannot do the job and a version that reports failure by returning a value.

The six methods

add returns true on success and offer returns true or false. remove and poll both return the removed element. element and peek both return the head without removing it.

On an empty queue

This is where the difference becomes visible, because "empty" is a state every queue passes through.

import java.util.*;

public class EmptyQueue {
    public static void main(String[] args) {
        Queue<String> q = new ArrayDeque<>();
        System.out.println("empty queue: " + q);
        System.out.println("poll()    -> " + q.poll());
        System.out.println("peek()    -> " + q.peek());
        try { q.remove(); } catch (Exception e) { System.out.println("remove()  -> " + e); }
        try { q.element(); } catch (Exception e) { System.out.println("element() -> " + e); }
    }
}

empty queue: []
poll()    -> null
peek()    -> null
remove()  -> java.util.NoSuchElementException
element() -> java.util.NoSuchElementException

NoSuchElementException carries no message, which makes it a poor thing to meet in production logs — the stack trace is all you get. poll and peek return null instead.

On a bounded queue

ArrayDeque, LinkedList and PriorityQueue are all unbounded: they grow rather than refuse. So add and offer behave identically on them, and the difference only appears once a queue has a capacity. The standard bounded implementation is ArrayBlockingQueue, used here purely as a capacity-limited Queue with no threads involved.

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class BoundedQueue {
    public static void main(String[] args) {
        Queue<String> bounded = new ArrayBlockingQueue<>(2);
        System.out.println("offer(x) -> " + bounded.offer("x"));
        System.out.println("offer(y) -> " + bounded.offer("y"));
        System.out.println("offer(z) -> " + bounded.offer("z"));
        try { bounded.add("z"); } catch (Exception e) { System.out.println("add(z)   -> " + e); }
        System.out.println("bounded: " + bounded);
    }
}

offer(x) -> true
offer(y) -> true
offer(z) -> false
add(z)   -> java.lang.IllegalStateException: Queue full
bounded: [x, y]

offer returned false and dropped the element on the floor; add threw IllegalStateException: Queue full. Both left the queue holding [x, y]. The dangerous version is offer, because a program that ignores the returned boolean silently loses data.

java.util.concurrent also has BlockingQueue, which adds a third pair of operations that wait for space or for an element instead of failing — that belongs with concurrency and is not covered here.

Which family to use

Pick by what an empty or full queue means in your program:

• If it means a bug, use remove and element. The exception stops execution at the mistake instead of letting a null travel several frames before something dereferences it.
• If it is an ordinary state — a worker draining a queue that is often empty — use poll and peek, and check the result at every call site.
• For inserting into an unbounded queue the choice does not matter, because neither can fail. Pick one and be consistent; most code uses offer.

Mixing the two families inside one loop is where the bugs come from: while (!q.isEmpty()) { process(q.poll()); } is safe, but the same loop with a second consumer can see isEmpty() return false and poll() return null anyway.

Deque: one structure, opened at both ends

A Deque — "double ended queue", usually pronounced "deck" — allows insert, remove and examine at both the head and the tail. That single generalisation replaces both of the classic structures: use one end and it is a stack, use one end for input and the other for output and it is a queue.

The full method table

Every Queue operation appears twice, once per end, and each of those still comes in a throwing and a special-value form. That is twelve methods, laid out on a completely regular grid.

The inherited Queue methods are aliases for the head-and-tail pair that gives FIFO order: add is addLast, offer is offerLast, remove is removeFirst, poll is pollFirst, element is getFirst, peek is peekFirst.

import java.util.*;

public class DequeBasics {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.addFirst("B");
        d.addLast("C");
        d.offerFirst("A");
        d.offerLast("D");
        System.out.println("deque: " + d);
        System.out.println("getFirst()  -> " + d.getFirst());
        System.out.println("getLast()   -> " + d.getLast());
        System.out.println("pollFirst() -> " + d.pollFirst());
        System.out.println("pollLast()  -> " + d.pollLast());
        System.out.println("deque: " + d);

        Deque<String> empty = new ArrayDeque<>();
        System.out.println("pollFirst() -> " + empty.pollFirst());
        try { empty.getFirst(); } catch (Exception e) { System.out.println("getFirst()  -> " + e); }
    }
}

deque: [A, B, C, D]
getFirst()  -> A
getLast()   -> D
pollFirst() -> A
pollLast()  -> D
deque: [B, C]
pollFirst() -> null
getFirst()  -> java.util.NoSuchElementException

push, pop and peek: the stack view

Deque also declares three methods with stack names. They are defined as head operations: push is addFirst, pop is removeFirst, and the stack-flavoured peek is peekFirst. Because the head is the top, iteration runs from the most recently pushed element downwards — the same order as popping.

import java.util.*;

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println("stack: " + stack);
        System.out.println("peek() -> " + stack.peek());
        System.out.println("for-each order:");
        for (String e : stack) System.out.println("  " + e);
        System.out.println("pop() -> " + stack.pop());
        System.out.println("pop() -> " + stack.pop());
        System.out.println("stack: " + stack);
        System.out.println("descendingIterator gives bottom-to-top if you want it:");
        Iterator<String> it = stack.descendingIterator();
        while (it.hasNext()) System.out.println("  " + it.next());
    }
}

stack: [top, middle, bottom]
peek() -> top
for-each order:
  top
  middle
  bottom
pop() -> top
pop() -> middle
stack: [bottom]
descendingIterator gives bottom-to-top if you want it:
  bottom

pop on an empty ArrayDeque throws java.util.NoSuchElementException, not the EmptyStackException that the legacy class throws. There is no special-value spelling of pop; use pollFirst when empty is expected.

ArrayDeque or LinkedList

Both implement Deque, and they differ in what a single element costs. ArrayDeque holds one Object[] and two indices, head and tail, that wrap around the end of the array — that is what "circular array" means. Nothing shifts when you insert or remove at either end; only an index moves. Reading the private fields back shows it directly:

import java.lang.reflect.Field;
import java.util.*;

public class Circular {
    static Field ELEMENTS, HEAD, TAIL;
    static {
        try {
            ELEMENTS = ArrayDeque.class.getDeclaredField("elements"); ELEMENTS.setAccessible(true);
            HEAD = ArrayDeque.class.getDeclaredField("head"); HEAD.setAccessible(true);
            TAIL = ArrayDeque.class.getDeclaredField("tail"); TAIL.setAccessible(true);
        } catch (Exception e) { throw new RuntimeException(e); }
    }
    static void dump(String label, ArrayDeque<?> d) throws Exception {
        Object[] es = (Object[]) ELEMENTS.get(d);
        System.out.printf("%-24s head=%d tail=%d  capacity=%d  %s%n",
            label, HEAD.getInt(d), TAIL.getInt(d), es.length, Arrays.toString(es));
    }
    public static void main(String[] args) throws Exception {
        ArrayDeque<String> d = new ArrayDeque<>(5);
        dump("new ArrayDeque<>(5)", d);
        d.addLast("a"); d.addLast("b"); d.addLast("c");
        dump("addLast a, b, c", d);
        d.pollFirst(); d.pollFirst();
        dump("pollFirst twice", d);
        d.addLast("d"); d.addLast("e"); d.addLast("f");
        dump("addLast d, e, f", d);
        d.addLast("g");
        dump("addLast g", d);
        System.out.println("                         iteration: " + d);
        d.addLast("h");
        dump("addLast h (resize)", d);
        System.out.println("                         iteration: " + d);
    }
}

Run it with the module open, because the fields are private:

java --add-opens java.base/java.util=ALL-UNNAMED Circular

new ArrayDeque<>(5)      head=0 tail=0  capacity=6  [null, null, null, null, null, null]
addLast a, b, c          head=0 tail=3  capacity=6  [a, b, c, null, null, null]
pollFirst twice          head=2 tail=3  capacity=6  [null, null, c, null, null, null]
addLast d, e, f          head=2 tail=0  capacity=6  [null, null, c, d, e, f]
addLast g                head=2 tail=1  capacity=6  [g, null, c, d, e, f]
                         iteration: [c, d, e, f, g]
addLast h (resize)       head=10 tail=2  capacity=14  [g, h, null, null, null, null, null, null, null, null, c, d, e, f]
                         iteration: [c, d, e, f, g, h]

g landed at index 0 while the logical first element sat at index 2 — the array wrapped. The two pollFirst calls did not move anything; they nulled a slot and advanced head. When the array finally filled, it was replaced with a larger one and the contents copied.

Those copies are the only structural cost ArrayDeque has that LinkedList does not, and there are very few of them. This one also needs --add-opens:

import java.lang.reflect.Field;
import java.util.*;

public class CopyCost {
    public static void main(String[] args) throws Exception {
        Field f = ArrayDeque.class.getDeclaredField("elements"); f.setAccessible(true);
        int n = 1_000_000;
        ArrayDeque<Integer> d = new ArrayDeque<>();
        int last = ((Object[]) f.get(d)).length, resizes = 0; long copied = 0;
        for (int i = 0; i < n; i++) {
            d.addLast(i);
            int cap = ((Object[]) f.get(d)).length;
            if (cap != last) { resizes++; copied += i; last = cap; }
        }
        System.out.printf("ArrayDeque: %d addLast -> %d resizes, %d elements copied, final capacity %d%n",
            n, resizes, copied, last);
        System.out.printf("LinkedList: %d addLast -> %d Node objects allocated, 0 copies%n", n, n);
    }
}

ArrayDeque: 1000000 addLast -> 26 resizes, 2475359 elements copied, final capacity 1237734
LinkedList: 1000000 addLast -> 1000000 Node objects allocated, 0 copies

Twenty-six resizes and about 2.5 references copied per element added, against one heap-allocated node object per element with two extra reference fields each. That is why ArrayDeque is the default choice for both stack and queue work, and why the ArrayDeque documentation says it is faster than Stack when used as a stack and faster than LinkedList when used as a queue.

Reach for LinkedList only when you actually need the List half of it — indexed access, ListIterator, or null elements.

ArrayDeque rejects null, and poll returns null

ArrayDeque refuses null on every insertion method:

import java.util.*;

public class NullTrace {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.push(null);
    }
}

Exception in thread "main" java.lang.NullPointerException
	at java.base/java.util.ArrayDeque.addFirst(ArrayDeque.java:285)
	at java.base/java.util.ArrayDeque.push(ArrayDeque.java:578)
	at NullTrace.main(NullTrace.java:6)

That looks like an inconvenience and is actually the point. poll, peek, pollFirst and peekLast all use null to mean "there was nothing there", so a collection that could also contain null makes the return value ambiguous. LinkedList permits null, and the ambiguity is real:

import java.util.*;

public class NullQueue {
    public static void main(String[] args) {
        Deque<String> ll = new LinkedList<>();
        ll.add(null);
        System.out.println("size = " + ll.size() + ", isEmpty = " + ll.isEmpty());
        System.out.println("poll() -> " + ll.poll() + "   (a real element)");
        System.out.println("poll() -> " + ll.poll() + "   (now genuinely empty)");
    }
}

size = 1, isEmpty = false
poll() -> null   (a real element)
poll() -> null   (now genuinely empty)

Two identical return values, two different meanings. ArrayDeque removes the possibility at the door.

⚠️ The same argument applies to PriorityQueue, which also throws NullPointerException on offer(null).

Stack is legacy: what extends Vector costs you

java.util.Stack has been in the JDK since 1.0 and still works. It is also the standard example of inheritance used where composition was needed, and the consequences are visible from ordinary code.

The declaration is class Stack<E> extends Vector<E>, and Vector implements List. So a Stack is a List: it has get, set, add(int, E), remove(int), insertElementAt, subList, indexOf and everything else, all public, all applying to the same storage that push and pop use.

Every Vector method is on your stack

import java.util.*;

public class StackMess {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        s.push("bottom");
        s.push("middle");
        s.push("top");
        System.out.println("stack: " + s);

        s.insertElementAt("SMUGGLED", 1);
        System.out.println("after insertElementAt(\"SMUGGLED\", 1): " + s);
        System.out.println("s.get(0)       -> " + s.get(0));
        System.out.println("s.elementAt(1) -> " + s.elementAt(1));
        s.set(2, "REWRITTEN");
        System.out.println("after set(2, \"REWRITTEN\"): " + s);
        s.remove(0);
        System.out.println("after remove(0): " + s);
        System.out.println("pop() -> " + s.pop());
        System.out.println("stack now: " + s);
    }
}

stack: [bottom, middle, top]
after insertElementAt("SMUGGLED", 1): [bottom, SMUGGLED, middle, top]
s.get(0)       -> bottom
s.elementAt(1) -> SMUGGLED
after set(2, "REWRITTEN"): [bottom, SMUGGLED, REWRITTEN, top]
after remove(0): [SMUGGLED, REWRITTEN, top]
pop() -> top
stack now: [SMUGGLED, REWRITTEN]

An element was inserted into the middle of a stack, another was overwritten in place, and the bottom one was deleted — none of which a stack is supposed to permit. Every one of those calls compiles without a warning, because the type genuinely offers them. A method that takes your Stack as a parameter can do all of it, and the type system will not object.

Iteration order is the reverse of pop order

The second surprise is quieter and therefore worse. Stack inherits Vector's iterator, which walks the list from index 0 upwards — and index 0 is the bottom of the stack.

import java.util.*;

public class StackOrder {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        s.push("bottom");
        s.push("middle");
        s.push("top");

        System.out.println("for-each order:");
        for (String e : s) System.out.println("  " + e);

        System.out.println("pop order:");
        @SuppressWarnings("unchecked")
        Stack<String> copy = (Stack<String>) s.clone();
        while (!copy.isEmpty()) System.out.println("  " + copy.pop());
    }
}

for-each order:
  bottom
  middle
  top
pop order:
  top
  middle
  bottom

Printing a Stack, streaming it, copying it into a List or writing it to a log all produce the reverse of the order in which the elements will actually come out. toString() shows [bottom, middle, top] while pop() yields top first. The ArrayDeque in the previous section prints [top, middle, bottom] and pops in exactly that order.

For completeness, the empty-stack behaviour is also its own thing — neither of the two Queue families:

import java.util.*;

public class StackQuirks {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        try { s.peek(); } catch (Exception e) { System.out.println("empty.peek() -> " + e); }
        try { s.pop(); }  catch (Exception e) { System.out.println("empty.pop()  -> " + e); }
        System.out.println("EmptyStackException extends " + EmptyStackException.class.getSuperclass().getName());
        s.push(null);
        s.push("a");
        System.out.println("Stack accepts null:  " + s);
        System.out.println("search(\"a\")  -> " + s.search("a"));
        System.out.println("search(\"zz\") -> " + s.search("zz"));
    }
}

empty.peek() -> java.util.EmptyStackException
empty.pop()  -> java.util.EmptyStackException
EmptyStackException extends java.lang.RuntimeException
Stack accepts null:  [null, a]
search("a")  -> 1
search("zz") -> -1

EmptyStackException extends RuntimeException directly and exists solely for this class. search(Object) returns a 1-based distance from the top rather than an index, and -1 when absent — conventions that appear nowhere else in the framework.

One last cost: Vector synchronizes its methods, so pop() and peek() are synchronized and push delegates to the synchronized addElement. You pay for that lock on every single-threaded call, and it still does not make a compound sequence such as "check isEmpty, then pop" atomic.

The replacement is ArrayDeque

This is not a matter of taste. The JDK's own documentation for Stack states that a more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, "which should be used in preference to this class". The migration is mechanical, and the resulting code is shorter:

Declare the variable as Deque, not as ArrayDeque, so the rest of the code sees only the operations a stack should have. Keep Stack only when an existing API forces the type on you.

PriorityQueue is a binary heap, not a sorted list

PriorityQueue returns elements in priority order from poll, and that one true statement gets generalised into a false one: that the collection is sorted. It is not. It is a binary heap stored in an array, and the only property it maintains is that every element is less than or equal to its two children.

toString prints the array, not the order

import java.util.*;

public class HeapOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int[] input = {5, 1, 8, 3, 9, 2, 7, 4, 6};
        for (int n : input) pq.offer(n);
        System.out.println("inserted:  " + Arrays.toString(input));
        System.out.println("toString:  " + pq);
        System.out.println("toArray:   " + Arrays.toString(pq.toArray()));
        System.out.println("copy:      " + new ArrayList<>(pq));
        System.out.println("peek():    " + pq.peek());

        PriorityQueue<Integer> c = new PriorityQueue<>(pq);
        StringJoiner j = new StringJoiner(", ", "[", "]");
        while (!c.isEmpty()) j.add(String.valueOf(c.poll()));
        System.out.println("poll loop: " + j);
    }
}

inserted:  [5, 1, 8, 3, 9, 2, 7, 4, 6]
toString:  [1, 3, 2, 4, 9, 8, 7, 5, 6]
toArray:   [1, 3, 2, 4, 9, 8, 7, 5, 6]
copy:      [1, 3, 2, 4, 9, 8, 7, 5, 6]
peek():    1
poll loop: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Read that carefully. toString() printed [1, 3, 2, 4, 9, 8, 7, 5, 6] — the smallest element is first, and after that the order is neither the insertion order nor the sorted order. It is the array layout of the heap: index 0 is the root, and the children of index i live at 2i+1 and 2i+2. So index 0 holds 1, its children at 1 and 2 hold 3 and 2, their children at 3, 4, 5, 6 hold 4, 9, 8, 7, and so on. Every parent is smaller than both children, and nothing more is guaranteed.

The peek() line above shows the exact trap in miniature: the first element of toString() really is the next one out, which is why the illusion survives so long. Only the full poll loop produces [1, 2, 3, 4, 5, 6, 7, 8, 9].

Building the heap one offer at a time shows where the layout comes from — each new value goes at the end and then swaps upwards while it is smaller than its parent:

offer(5) -> [5]
offer(1) -> [1, 5]
offer(8) -> [1, 5, 8]
offer(3) -> [1, 3, 8, 5]
offer(9) -> [1, 3, 8, 5, 9]
offer(2) -> [1, 3, 2, 5, 9, 8]
offer(7) -> [1, 3, 2, 5, 9, 8, 7]
offer(4) -> [1, 3, 2, 4, 9, 8, 7, 5]
offer(6) -> [1, 3, 2, 4, 9, 8, 7, 5, 6]

offer(2) is the interesting step: 2 was appended at index 5, compared with its parent 8 at index 2, swapped, then compared with the root 1 and left alone. Two comparisons, and the whole array reordered exactly as much as it had to.

Iterating does not visit in priority order

Since toString() walks the backing array, so does everything else built on the iterator. There is no sorted view anywhere.

import java.util.*;

public class HeapIteration {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 8, 3, 9, 2, 7, 4, 6));
        System.out.print("for-each:         ");
        for (int n : pq) System.out.print(n + " ");
        System.out.println();
        System.out.println("stream().toList() " + pq.stream().toList());
        System.out.println("stream().sorted() " + pq.stream().sorted().toList());
    }
}

for-each:         1 3 2 4 9 8 7 5 6 
stream().toList() [1, 3, 2, 4, 9, 8, 7, 5, 6]
stream().sorted() [1, 2, 3, 4, 5, 6, 7, 8, 9]

The for-each loop and stream().toList() both returned the raw heap array. Only sorted() produced ascending values, and that is a sort being performed on the way past, not a property of the queue. PriorityQueue documents that its iterator is not guaranteed to traverse the elements in any particular order, so draining the queue is the only ordered read it offers:

while (!pq.isEmpty()) {
    process(pq.poll());
}

If you need the elements in order and need to keep them, poll into a List, or copy the collection and sort the copy. Do not iterate and hope.

Where the ordering comes from

Either the elements implement Comparable, or you hand a Comparator to the constructor. With neither, the first offer fails:

import java.util.*;

record Task(String name, int priority) {}

public class NoOrdering {
    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>();
        try { pq.offer(new Task("A", 1)); } catch (Exception e) { System.out.println(e); }
    }
}

java.lang.ClassCastException: class Task cannot be cast to class java.lang.Comparable (Task is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

A ClassCastException for a call that never mentioned a cast — the cast is inside siftUpComparable. Supplying a Comparator fixes it, and reversing that comparator turns the min-heap into a max-heap:

import java.util.*;

public class MaxHeap {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int n : new int[]{5, 1, 8, 3, 9, 2, 7}) maxHeap.offer(n);
        System.out.println("toString: " + maxHeap);
        System.out.print("poll:     ");
        while (!maxHeap.isEmpty()) System.out.print(maxHeap.poll() + " ");
        System.out.println();
    }
}

toString: [9, 8, 7, 1, 3, 2, 5]
poll:     9 8 7 5 3 2 1 

Same class, same array layout rules, opposite direction. The heap invariant now reads "every parent is greater than or equal to its children", and toString() is just as unsorted as before.

Equal priorities have no defined order

PriorityQueue is not stable: two elements that compare equal come out in whatever order the heap operations happened to leave them in. This is easy to demonstrate and easy to be bitten by, because for small inputs it often looks like insertion order.

import java.util.*;

record Task(String name, int priority) {
    @Override public String toString() { return name + "(" + priority + ")"; }
}

public class Ties {
    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        String[] names = {"A", "B", "C", "D", "E", "F"};
        int[] prios = {2, 1, 2, 1, 2, 1};
        for (int i = 0; i < names.length; i++) pq.offer(new Task(names[i], prios[i]));
        System.out.println("offered: A(2) B(1) C(2) D(1) E(2) F(1)");
        System.out.println("heap:    " + pq);
        System.out.print("poll:    ");
        while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
        System.out.println();
    }
}

offered: A(2) B(1) C(2) D(1) E(2) F(1)
heap:    [B(1), D(1), F(1), A(2), E(2), C(2)]
poll:    B(1) D(1) F(1) A(2) E(2) C(2) 

The three priority-1 tasks came out in insertion order, B D F. The three priority-2 tasks did not: they went in A C E and came out A E C. Nothing about that is a bug — the comparator said those three are equal, so the heap was free to arrange them any way that satisfied the invariant, and it did.

The fix is to make the tie impossible. Give each element a monotonically increasing sequence number and compare on it second:

Comparator<Job> order = Comparator.comparingInt(Job::priority)
                                  .thenComparingLong(Job::seq);

Now no two elements ever compare equal, and the order is fully determined by your comparator instead of by the heap's internals.

Unbounded, and no nulls

PriorityQueue grows on demand; the constructor argument is an initial capacity, not a limit. A capacity of zero is rejected outright, and null is refused for the same reason ArrayDeque refuses it — with a second reason here, since null cannot be compared.

import java.util.*;

public class PQLimits {
    public static void main(String[] args) {
        PriorityQueue<Integer> g = new PriorityQueue<>(3);
        for (int i = 0; i < 100_000; i++) g.offer(i);
        System.out.println("capacity 3, after 100000 offers: size=" + g.size() + " peek=" + g.peek());
        try { new PriorityQueue<Integer>(0); } catch (Exception e) { System.out.println("new PriorityQueue<>(0) -> " + e); }
        try { g.offer(null); } catch (Exception e) { System.out.println("offer(null)            -> " + e); }
    }
}

capacity 3, after 100000 offers: size=100000 peek=0
new PriorityQueue<>(0) -> java.lang.IllegalArgumentException
offer(null)            -> java.lang.NullPointerException

Neither exception carries a message, so a NullPointerException from deep inside a scheduling loop is usually a null that reached offer from somewhere else entirely.

What offer and poll actually cost

A heap does not keep the collection ordered; it keeps just enough order to know the smallest element. That shows up as a very small number of comparisons per insert and a larger but still logarithmic number per removal. Counting them needs no timing at all — wrap the comparator:

import java.util.*;

public class HeapCost {
    static long comparisons = 0;
    public static void main(String[] args) {
        for (int n : new int[]{1000, 10_000, 100_000}) {
            Random r = new Random(42);
            Integer[] data = new Integer[n];
            for (int i = 0; i < n; i++) data[i] = r.nextInt(1_000_000);

            comparisons = 0;
            PriorityQueue<Integer> pq =
                new PriorityQueue<>((a, b) -> { comparisons++; return Integer.compare(a, b); });
            for (Integer v : data) pq.offer(v);
            long ins = comparisons;

            comparisons = 0;
            while (!pq.isEmpty()) pq.poll();
            long ext = comparisons;

            System.out.printf("n=%-7d offer total=%-9d avg=%.2f  poll total=%-9d avg=%.2f  log2(n)=%.1f%n",
                n, ins, (double) ins / n, ext, (double) ext / n, Math.log(n) / Math.log(2));
        }
    }
}

n=1000    offer total=2232      avg=2.23  poll total=14994     avg=14.99  log2(n)=10.0
n=10000   offer total=22593     avg=2.26  poll total=216736    avg=21.67  log2(n)=13.3
n=100000  offer total=227662    avg=2.28  poll total=2831463   avg=28.31  log2(n)=16.6

Insertion costs about 2.3 comparisons on average regardless of size: a new value usually stops after one or two swaps, because most positions in a heap are near the bottom. Removal is the expensive half — the last element is moved to the root and sifted down, and each level costs two comparisons, one to pick the smaller child and one to compare it against the value being sifted. The measured averages confirm that shape exactly: log2(n) grows from 10.0 to 16.6 across the three runs while the average poll grows from 14.99 to 28.31, a slope of almost precisely two comparisons per extra level.

Two operations do not scale at all: contains(Object) and remove(Object) are linear scans of the array, because a heap has no index by value. peek() is a single array read.

That last row is measurable with the same technique: building a heap from a 100,000-element list costs 188,424 comparisons, against 227,662 for the same values offered one at a time. Prefer the collection constructor when you already have the data.

Three worked examples

A priority task scheduler

A scheduler is the natural shape for a PriorityQueue: jobs arrive in any order, the next job to run is always the most urgent one, and running a job may enqueue more work. The sequence number in the comparator is what makes equal priorities run first-come-first-served instead of arbitrarily.

import java.util.*;

public class Scheduler {
    record Job(String name, int priority, long seq) {}

    public static void main(String[] args) {
        Comparator<Job> byPriorityThenArrival =
            Comparator.comparingInt(Job::priority).thenComparingLong(Job::seq);

        PriorityQueue<Job> queue = new PriorityQueue<>(byPriorityThenArrival);
        long seq = 0;
        queue.offer(new Job("send-invoice", 5, seq++));
        queue.offer(new Job("page-oncall", 1, seq++));
        queue.offer(new Job("rebuild-index", 9, seq++));
        queue.offer(new Job("refund-charge", 1, seq++));
        queue.offer(new Job("warm-cache", 5, seq++));

        while (!queue.isEmpty()) {
            Job job = queue.poll();
            System.out.printf("run %-14s priority=%d arrived=%d%n",
                job.name(), job.priority(), job.seq());
            if (job.name().equals("page-oncall")) {
                queue.offer(new Job("escalate", 1, seq++));
            }
        }
    }
}

run page-oncall    priority=1 arrived=1
run refund-charge  priority=1 arrived=3
run escalate       priority=1 arrived=5
run send-invoice   priority=5 arrived=0
run warm-cache     priority=5 arrived=4
run rebuild-index  priority=9 arrived=2

escalate was enqueued during the loop at priority 1 and still ran before every priority-5 job, without anything being re-sorted. A sorted List would have needed an insertion at the right index on every offer; the heap needed a handful of comparisons.

Merging sorted inputs

The other classic use is a k-way merge. Keep one cursor per input in the heap, take the smallest, and push that cursor's successor back. The heap never holds more than one entry per input, so merging a hundred files costs a heap of a hundred elements no matter how long the files are.

import java.util.*;

public class MergeSorted {
    record Cursor(List<Integer> src, int idx) {
        int value() { return src.get(idx); }
        Cursor next() { return idx + 1 < src.size() ? new Cursor(src, idx + 1) : null; }
    }

    public static void main(String[] args) {
        List<List<Integer>> inputs = List.of(
            List.of(1, 4, 9, 12),
            List.of(2, 3, 10),
            List.of(5, 6, 7, 8, 11));

        PriorityQueue<Cursor> heap = new PriorityQueue<>(Comparator.comparingInt(Cursor::value));
        for (List<Integer> in : inputs) if (!in.isEmpty()) heap.offer(new Cursor(in, 0));

        List<Integer> merged = new ArrayList<>();
        while (!heap.isEmpty()) {
            Cursor c = heap.poll();
            merged.add(c.value());
            Cursor n = c.next();
            if (n != null) heap.offer(n);
        }
        System.out.println("inputs: " + inputs);
        System.out.println("merged: " + merged);
        System.out.println("heap never held more than " + inputs.size() + " cursors");
    }
}

inputs: [[1, 4, 9, 12], [2, 3, 10], [5, 6, 7, 8, 11]]
merged: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
heap never held more than 3 cursors

Browser history with two deques

Back and forward are two stacks and one current value. Going back pushes the current page onto the forward stack and pops the back stack; going forward does the mirror image; visiting a new page pushes the current page onto the back stack and clears forward. That last rule is the one people forget, and it is one line.

import java.util.*;

public class History {
    private final Deque<String> back = new ArrayDeque<>();
    private final Deque<String> forward = new ArrayDeque<>();
    private String current;

    History(String home) { current = home; }

    void visit(String url) {
        back.push(current);
        current = url;
        forward.clear();
    }

    void back() {
        if (back.isEmpty()) { System.out.println("  back: nothing to go back to"); return; }
        forward.push(current);
        current = back.pop();
    }

    void forward() {
        if (forward.isEmpty()) { System.out.println("  forward: nothing to go forward to"); return; }
        back.push(current);
        current = forward.pop();
    }

    @Override public String toString() {
        return String.format("back=%s current=%s forward=%s", back, current, forward);
    }

    public static void main(String[] args) {
        History h = new History("/home");
        System.out.println("start          " + h);
        h.visit("/docs");    System.out.println("visit /docs    " + h);
        h.visit("/docs/io"); System.out.println("visit /docs/io " + h);
        h.visit("/pricing"); System.out.println("visit /pricing " + h);
        h.back();            System.out.println("back           " + h);
        h.back();            System.out.println("back           " + h);
        h.forward();         System.out.println("forward        " + h);
        h.visit("/blog");    System.out.println("visit /blog    " + h);
        h.forward();
        System.out.println("forward        " + h);
    }
}

start          back=[] current=/home forward=[]
visit /docs    back=[/home] current=/docs forward=[]
visit /docs/io back=[/docs, /home] current=/docs/io forward=[]
visit /pricing back=[/docs/io, /docs, /home] current=/pricing forward=[]
back           back=[/docs, /home] current=/docs/io forward=[/pricing]
back           back=[/home] current=/docs forward=[/docs/io, /pricing]
forward        back=[/docs, /home] current=/docs/io forward=[/pricing]
visit /blog    back=[/docs/io, /docs, /home] current=/blog forward=[]
  forward: nothing to go forward to
forward        back=[/docs/io, /docs, /home] current=/blog forward=[]

The printed deques read top-first, so back=[/docs/io, /docs, /home] says the next back step goes to /docs/io — exactly the order the user would see. That readability is a direct consequence of ArrayDeque iterating from the head. The same structure with two Stack objects would print backwards.

An undo history is the same class with different names: undo and redo instead of back and forward, and a bounded variant that calls pollLast() after each push to drop the oldest entry once the deque exceeds its limit.

Choosing between them

Two rules cover most of it. Declare the variable as Queue or Deque rather than as the implementation class, so the restriction is enforced by the compiler. And reach for ArrayDeque unless you have a specific reason not to.

FAQ

What is the difference between add and offer in a Java Queue?

They insert the same element in the same place and differ only in how they report failure. add(e) throws java.lang.IllegalStateException: Queue full when the queue has no room; offer(e) returns false. On ArrayDeque, LinkedList and PriorityQueue — all unbounded — neither can fail, so the two are interchangeable. The difference matters only for capacity-limited queues such as ArrayBlockingQueue.

What is the difference between poll and remove in a Java Queue?

Both remove and return the head. On an empty queue, poll() returns null and remove() throws java.util.NoSuchElementException, which carries no message. Use poll when empty is a normal state and you will check the result; use remove when empty means a bug and you want the program to stop there. The same split applies to peek and element, which return the head without removing it.

Should I use Stack or ArrayDeque in Java?

ArrayDeque, in new code without exception. Stack extends Vector, so it is also a List: get(i), set(i, e) and insertElementAt(e, i) all work on it and let callers modify the middle of your stack. Its iteration and toString() order is bottom-to-top, the reverse of pop order. And every method is synchronized, which costs you a lock on every call without making a check-then-pop sequence atomic. ArrayDeque with push, pop and peek has none of those problems.

Why does printing a PriorityQueue not show sorted values?

Because toString() walks the backing array, and that array is a binary heap rather than a sorted sequence. Offering 5 1 8 3 9 2 7 4 6 gives [1, 3, 2, 4, 9, 8, 7, 5, 6]: index 0 is the smallest element, and after that the only rule is that the element at index i is less than or equal to the elements at 2i+1 and 2i+2. Repeated poll() gives [1, 2, 3, 4, 5, 6, 7, 8, 9]; nothing else does.

Why does iterating a PriorityQueue not give priority order?

The iterator returns the backing array in index order, and PriorityQueue explicitly does not guarantee any traversal order. A for-each loop, stream(), toArray() and new ArrayList<>(pq) all produce the same unsorted heap layout. To read the elements in priority order you must drain the queue with poll(), or copy it and sort the copy — pq.stream().sorted().toList() works, but it is a sort, not a property of the queue.

Can a Java Queue contain null?

ArrayDeque and PriorityQueue both throw java.lang.NullPointerException on insertion of null. LinkedList allows it, and that is a trap rather than a feature: poll() returns null to mean "the queue was empty", so a queue that can also hold a null element makes the return value ambiguous. Stack, being a Vector, also accepts null.

How do I make a max-heap with PriorityQueue in Java?

Pass a reversed comparator to the constructor: new PriorityQueue<>(Comparator.reverseOrder()) for naturally ordered elements, or Comparator.comparingInt(Task::priority).reversed() for your own type. The class is unchanged; only the invariant flips, so every parent becomes greater than or equal to its children and poll() returns the largest element. toString() remains unsorted either way.

Does PriorityQueue keep elements with equal priority in insertion order?

No. Ties are broken arbitrarily by whatever the heap operations happened to do. Offering A(2) B(1) C(2) D(1) E(2) F(1) with a comparator on priority alone polls B(1) D(1) F(1) A(2) E(2) C(2) — the priority-1 group happened to keep insertion order and the priority-2 group did not. If arrival order matters, remove the tie: add a monotonically increasing sequence number to each element and chain it with thenComparingLong.

Conclusion

The four types in this article are one idea applied at four strengths. Queue takes away every position except the front. Deque gives back the other end and nothing more, which is enough to be a stack, a queue, or both at once. PriorityQueue replaces position with an ordering. Stack predates all of it and gives away the restriction entirely, which is why it survives only in old code.

The three things worth remembering are the ones runtime teaches painfully. The Queue methods come in pairs, and choosing between poll and remove is a decision about whether an empty queue is a bug or a state. ArrayDeque refuses null precisely so that a null from poll can only mean one thing. And a PriorityQueue is a heap: its head is the smallest element and everything behind the head is in an order that exists to make the next poll cheap, not to be read.

Next in this series: Iterator and ListIterator — how iteration actually works underneath the for-each loop, what ConcurrentModificationException really detects, and the difference between fail-fast and fail-safe iterators.