What is PriorityQueue & Deque in Java?

79 / 101

library

intermediate

PriorityQueue & Deque

Use priority-based and double-ended queue implementations for scheduling, BFS, and stack/queue patterns.

Two queues with very different ordering.

PriorityQueue = hospital ER triage (most urgent patient seen first, not first-come-first-served). Deque = a double-door hallway (enter/exit from either end).

Key Concepts

    PriorityQueue   smallest element first   a binary min-heap
    ArrayDeque      both ends                a circular array

PriorityQueue is not FIFO. poll() always returns the smallest:

PriorityQueuepoll()

    var q = new PriorityQueue<Integer>();
    q.addAll(List.of(5, 1, 3));
    q.poll();            // 1
    q.poll();            // 3

    // largest first
    new PriorityQueue<>(Comparator.reverseOrder());
    new PriorityQueue<>(Comparator.comparingInt(Task::priority));

Costs: offer and poll are O(log n), peek is O(1).

offerpollpeek

The trap: iteration is not sorted.

    for (int n : q) print(n);     // 1 5 3 -- heap order, not sorted

Only peek and poll respect the ordering. Printing a PriorityQueue directly shows the array layout, which looks like a bug and is not. To get sorted output, poll until empty.

peekpollPriorityQueue

ArrayDeque is both a stack and a queue, and faster than the alternatives.

    // as a stack (LIFO)
    deque.push(x);  deque.pop();  deque.peek();

ArrayDeque

    // as a queue (FIFO)
    deque.offer(x);  deque.poll();  deque.peek();

    // as a deque
    offerFirst / offerLast    pollFirst / pollLast

Use it instead of Stack and LinkedList.

    Stack          synchronized on every call, and extends Vector
    LinkedList     a node object plus two pointers per element
    ArrayDeque     one array, no locking

StackLinkedList

Stack is effectively deprecated by the Javadoc itself, which points at Deque.

StackDeque

ArrayDeque rejects null. That is deliberate: poll returns null for an empty deque, so a stored null would be indistinguishable from empty. LinkedList allows it and inherits exactly that ambiguity.

ArrayDequenullpollLinkedList

Where each shows up. PriorityQueue for schedulers, Dijkstra and merging sorted streams; ArrayDeque for breadth-first search, undo stacks and sliding windows.

PriorityQueueArrayDeque

What the interviewer is probing.1. "You iterate a PriorityQueue and the output is not sorted. Why?" Probing: what the heap guarantees. Stalls: "It is broken." Moves up: only peek and poll respect the ordering; iteration exposes the array layout of the heap. Poll until empty for sorted output.

2. "Why use ArrayDeque instead of Stack?" Probing: whether you know Stack is discouraged. Stalls: "Stack is fine." Moves up: Stack extends Vector and synchronises every call; the Javadoc itself points at Deque, and ArrayDeque is faster with no locking.

3. "Why does ArrayDeque reject null?" Probing: the ambiguity it avoids. Stalls: "An oversight." Moves up: poll returns null for an empty deque, so a stored null would be indistinguishable from empty — LinkedList allows it and inherits exactly that problem.

4. "How do you make a PriorityQueue return the largest first?" Probing: the comparator. Stalls: "Reverse the list." Moves up: pass Comparator.reverseOrder, or a comparator on the field you want ordered.