What's the difference between Queue and Deque, and where does PriorityQueue fit in?
8 minintermediatequeuedequepriorityqueue
Quick Answer
Queue models FIFO processing with offer()/poll()/peek() at one end. Deque (double-ended queue) generalizes this with explicit addFirst/addLast/removeFirst/removeLast, letting it act as both a queue and a stack (replacing the legacy Stack class). PriorityQueue is a Queue implementation that orders elements by priority (natural order or a Comparator) rather than insertion order, backed by a binary heap, so poll() always returns the smallest/highest-priority element.
Detailed Answer
Queue<E>: models FIFO (first-in-first-out) processing withoffer(e)/poll()/peek()(non-throwing) andadd(e)/remove()/element()(throwing variants for full/empty cases).Deque<E>("double-ended queue"): extends the queue concept to both ends —addFirst/addLast,removeFirst/removeLast,peekFirst/peekLast. Because of this, aDequecan act as either a FIFO queue (add at one end, remove from the other) or a LIFO stack (add/remove from the same end viapush/pop), which is whyArrayDequeis the JDK-recommended replacement for the legacy, synchronizedStackclass.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.pop(); // 2 — LIFO
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll(); // 1 — FIFO
PriorityQueue<E>: aQueueimplementation backed by a binary heap, wherepoll()/peek()always return the smallest element per natural ordering (Comparable) or a suppliedComparator— not insertion order. Insertion is O(log n); it's the standard structure behind algorithms like Dijkstra's shortest path or "top-K" problems.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.addAll(List.of(5, 1, 3));
minHeap.poll(); // 1 — smallest first, regardless of insertion order
Note PriorityQueue is not a Deque — it only supports removal from the "front" (highest priority), and its iterator makes no ordering guarantee at all.