Queue and Deque in Java: ArrayDeque and PriorityQueue

Queue

A Queue holds elements for processing. The usual discipline is first in, first out, but PriorityQueue deliberately breaks that and serves the smallest element first.

Two families of method

Prefer offer, poll and peek. Returning null for an empty queue is easier to handle than catching NoSuchElementException, and it makes bounded queues behave sensibly.

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

jobs.offer("resize-image");
jobs.offer("send-email");
jobs.offer("build-index");

while (!jobs.isEmpty()) {
    System.out.println("Running " + jobs.poll());
}
// resize-image, send-email, build-index

Deque

A double ended queue supports insertion and removal at both ends, so it can act as a queue, as a stack, or as both.

As a stack

Deque<String> history = new ArrayDeque<>();

history.push("page-1");
history.push("page-2");
history.push("page-3");

System.out.println(history.pop());    // page-3, last in first out
System.out.println(history.peek());   // page-2

This is the modern replacement for java.util.Stack. It is faster, is not synchronised, and does not expose list operations that would let a caller insert into the middle.

As a queue

Deque<String> queue = new ArrayDeque<>();
queue.offerLast("first");
queue.offerLast("second");
System.out.println(queue.pollFirst());   // first

ArrayDeque

Backed by a circular array. Both ends are O(1), there is no per element node object, and it is friendly to the processor cache.

• It does not allow null, deliberately, because null is the "empty" signal from poll and peek.
• It is not thread safe. Use ConcurrentLinkedDeque or LinkedBlockingDeque when shared.
• It is preferred over LinkedList for every queue and stack use.

PriorityQueue

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

System.out.println(smallestFirst.poll());   // 10
System.out.println(smallestFirst.poll());   // 20

record Task(String name, int priority) { }

Queue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed());

tasks.offer(new Task("backup", 1));
tasks.offer(new Task("alert", 9));
tasks.offer(new Task("report", 5));

System.out.println(tasks.poll());    // alert, highest priority first

It is a binary heap, so offer and poll are O(log n) and peek is O(1).

Only the head is ordered. Printing a PriorityQueue or iterating it shows the heap array, not sorted order. The order is guaranteed only through repeated poll calls, which surprises people constantly.

System.out.println(smallestFirst);      // e.g. [10, 20, 40, 50] - not a promise

Choosing a queue

A worked example: balanced brackets

public static boolean isBalanced(String text) {
    Deque<Character> open = new ArrayDeque<>();
    String openers = "([{";
    String closers = ")]}";

    for (char c : text.toCharArray()) {
        if (openers.indexOf(c) >= 0) {
            open.push(c);
        } else {
            int index = closers.indexOf(c);
            if (index >= 0) {
                if (open.isEmpty() || open.pop() != openers.charAt(index)) {
                    return false;
                }
            }
        }
    }
    return open.isEmpty();
}

Common mistakes

• Adding null to an ArrayDeque, which throws.
• Expecting a PriorityQueue to iterate in sorted order.
• Using java.util.Stack in new code.
• Using LinkedList as a queue when ArrayDeque is faster in every respect.
• Mixing the throwing and the returning method families and being surprised by an exception.
• Sharing a plain ArrayDeque between threads.

Best practices

• Declare the variable as Queue or Deque, and instantiate ArrayDeque.
• Use offer, poll and peek.
• Give a PriorityQueue an explicit Comparator unless natural order is obviously right.
• Use a blocking queue from java.util.concurrent for producer and consumer designs.
• Drain with while ((item = queue.poll()) != null) rather than checking isEmpty and then removing.

Practice

1. Implement an undo history with a Deque and explain why Stack is a poorer choice.
2. Print a PriorityQueue directly and then drain it, and explain the difference.
3. Why does ArrayDeque forbid null elements?
4. Build a task scheduler that always runs the highest priority task first.
5. Rewrite a bracket matcher using ArrayDeque and handle unmatched closers.

Conclusion

Use ArrayDeque for queues and stacks, PriorityQueue when order of service matters, and a blocking queue when threads hand work to each other. Prefer the methods that return a value over the ones that throw.