skip to content

Queue & Deque

FIFO, LIFO and priority structures: the Queue and Deque contracts, ArrayDeque, and PriorityQueue. Interviewers ask about them whenever a problem needs a stack, a work queue or a heap.

part ofJavaread it →
on this pageshow

explore

questions

12

What is a PriorityQueue in Java and how do you get elements out in priority order?

level: juniorimportance: must knowfreq 70%

answer

  1. Min-heap by default: smallest out first
  2. Natural order OR a Comparator
  3. poll removes head, peek looks
  4. poll/peek return null; remove/element throw
  5. No nulls, not thread-safe, unbounded

basics

~20 s

A PriorityQueue is a queue where the smallest element (by natural order or a Comparator) always comes out first. You add with offer/add and remove the highest-priority element with poll. peek looks at the head without removing it.

solid answer

~40 s

PriorityQueue is a Queue implementation backed by a binary heap. Instead of FIFO, the element at the head is always the one with the highest priority - by default the smallest by natural ordering, or by a Comparator you pass to the constructor. You enqueue with offer (or add) and dequeue the highest-priority element with poll, which returns and removes the head; peek returns it without removing. poll/peek return null when empty (unlike remove/element, which throw). It is unbounded and grows automatically, is not thread-safe (use PriorityBlockingQueue for concurrency), and does not permit null elements. Typical uses: scheduling, Dijkstra's shortest path, top-K, and merging sorted streams - anywhere you repeatedly need the current minimum or maximum.

go deeper

for a junior

Knows it returns the smallest first by default, uses offer/poll/peek, and that it isn't FIFO.

for a middle

Distinguishes natural order vs Comparator, builds a max-queue, knows the null/throws vs null-return behavior and no-null rule.

for a senior

Explains the heap backing, thread-safety (PriorityBlockingQueue), comparator consistency, and chooses it for greedy/top-K problems.

for a principal

Reasons about comparator stability, memory/resize cost, alternatives (TreeSet, indexed heaps for decrease-key) and API contract guarantees across the JDK.

## What problem it solves An ordinary queue is **FIFO** (first-in, first-out): the order you take things out matches the order you put them in. Sometimes you instead want to always pull out the *most important* item next, regardless of when it arrived - e.g. the next task to run, the closest node to explore. A **priority queue** does exactly this: each element has a **priority**, and the *dequeue* operation always returns the element with the best priority. ## What "priority" means here Java's `java.util.PriorityQueue<E>` is a **min-priority queue by default**: the element that is *smallest* according to ordering is the one returned first. "Smallest" is decided one of two ways: - **Natural ordering** - the element type implements `Comparable<E>` (e.g. `Integer`, `String`), so the JDK can call `a.compareTo(b)`. - **A `Comparator`** you pass to the constructor: `new PriorityQueue<>(comparator)`. This overrides natural order and lets you do anything, including a *max*-queue with `Comparator.reverseOrder()`. ## The core operations - `offer(e)` / `add(e)` - insert an element. Both insert; `add` is the `Collection` method and `offer` is the `Queue` method. For an unbounded queue like `PriorityQueue` they behave the same. - `poll()` - remove **and return** the head (the highest-priority element). Returns `null` if empty. - `peek()` - return the head **without** removing it. Returns `null` if empty. - `remove()` / `element()` - same as poll/peek but **throw** `NoSuchElementException` when empty instead of returning null. The "head" is always the minimum (or your Comparator's first element). After you `poll`, the queue reorganizes so the *new* minimum becomes the head. ## Other characteristics - **Cost**: the Javadoc's implementation note gives O(log n) time for `offer`, `add`, `poll` and `remove()`, constant time for `peek`, `element` and `size`, and linear time for `remove(Object)` and `contains(Object)`. - **Unbounded**: it grows automatically; there is no fixed capacity limit (the constructor's `initialCapacity` is only a sizing hint). - **No nulls**: inserting `null` throws `NullPointerException`, even with a comparator that could order it, such as `Comparator.nullsFirst(...)`. `poll` and `peek` use `null` to signal an empty queue, so a stored null would be ambiguous. - **Not thread-safe**: concurrent modification can corrupt it; use `java.util.concurrent.PriorityBlockingQueue` for multi-threaded use. - **Comparator must be consistent**: if your Comparator returns 0 for two different elements, they are treated as equal-priority and may come out in any relative order. ## Worked example ``` PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.offer(5); pq.offer(1); pq.offer(3); pq.poll(); // 1 (smallest) pq.poll(); // 3 pq.poll(); // 5 ``` Repeated `poll` or `remove()` gives this order by draining the queue. The iterator, which a for-each loop and `toString` use, is "not guaranteed to traverse the elements of the priority queue in any particular order": printed right after the three offers, this queue shows `[1, 5, 3]` on JDK 27. For ordered traversal, the Javadoc suggests `Arrays.sort(pq.toArray())`. For a max-queue, pass `Comparator.reverseOrder()` so `poll` returns the largest. ## When to reach for it Greedy algorithms (Dijkstra, Prim, Huffman coding), event/task scheduling by time or priority, and "top-K largest/smallest" problems all rely on cheaply getting the current best element again and again.

  • How do you make a max-priority queue?
    Pass a reversing comparator, e.g. new PriorityQueue<>(Comparator.reverseOrder()), or for objects Comparator.comparingInt(...).reversed().
  • What's the difference between poll() and remove() on an empty queue?
    poll() returns null; remove() throws NoSuchElementException. Same split applies to peek() (null) vs element() (throws).

  • Saying it returns the largest by default (it returns the smallest)
  • Thinking it behaves FIFO like a normal queue
  • Claiming it is thread-safe
  • Assuming it can store null elements

java.util.PriorityQueue
Java 1.5

context

open as a page

What is Java's Queue interface, and how do its two families of insert, remove and inspect operations differ on failure?

level: juniorimportance: must knowfreq 70%

basics

~10 s

Queue is the java.util interface for holding elements before processing, typically FIFO. add/remove/element throw when they cannot act; offer/poll/peek report a full or empty queue by returning false or null.

open as a page

Why is iterating over a PriorityQueue not the same as getting elements in sorted order?

level: middleimportance: must knowfreq 62%

basics

~20 s

Iterating (for-each, iterator, toArray, toString) walks the internal heap array, which is only partially ordered - just the head is guaranteed smallest. Repeatedly calling poll() drains them in priority order; sorting a copy leaves the queue intact.

open as a page

What is a Deque, and how do its head and tail operations let it act as both a queue and a stack?

level: middleimportance: must knowfreq 65%

basics

~20 s

A Deque (double-ended queue) lets you add and remove from both ends. You can use it FIFO like a queue (add at one end, remove from the other) or LIFO like a stack (add and remove from the same end).

open as a page

How do you control PriorityQueue ordering (e.g. build a max-heap or order by an object field), and what must the Comparator guarantee?

level: middleimportance: should knowfreq 58%

basics

~10 s

Pass a Comparator to the constructor: PriorityQueue<>(Comparator.reverseOrder()) for a max-heap, or Comparator.comparingInt(Task::getPriority) to order by a field. Without one it uses the element's natural ordering, so the type must be Comparable.

open as a page

How does Java's PriorityQueue work inside: its heap array, sifting on offer and poll, array growth, and bulk-constructor heapify?

level: middleimportance: should knowfreq 46%

basics

~20 s

PriorityQueue keeps a binary min-heap in an Object array: offer sifts the new element up from the end, poll sifts the last element down from the root. The array grows by copying, and building from an unordered collection runs O(n) heapify.

open as a page

How does Java's ArrayDeque work inside: its circular array, how head and tail move and wrap, how it grows, and why it refuses null?

level: middleimportance: should knowfreq 34%

basics

~20 s

ArrayDeque is a circular Object array with head and tail indices that wrap at its ends, keeping one slot null between calls. An insert that fills that slot grows the array. Null is refused because a null cell means empty.

open as a page

Why is ArrayDeque recommended over the legacy java.util.Stack class for stack behavior?

level: middleimportance: should knowfreq 60%

basics

~10 s

Stack is old and extends Vector, so every stack operation takes a lock and it exposes index-based methods that break stack semantics. ArrayDeque is likely faster, unsynchronized, and gives a clean push/pop/peek stack API.

open as a page

What are the time complexities of PriorityQueue's offer, poll, peek, and contains/remove(Object) operations, and why?

level: seniorimportance: should knowfreq 55%

basics

~20 s

offer and poll are O(log n) because they bubble an element up or down the heap. peek is O(1) - the head is at index 0. contains(o) and remove(o) are O(n) because they have to scan the array linearly.

open as a page

What are the thread-safety and mutable-key pitfalls of PriorityQueue, and how do you address them?

level: seniorimportance: should knowfreq 40%

basics

~20 s

PriorityQueue is not thread-safe - concurrent use can corrupt it, so use PriorityBlockingQueue or external locking. Also, if you change a field used for ordering after inserting an element, the queue won't re-sort and its order can break.

open as a page

What is ArrayDeque, how does it store elements, and why is it generally preferred over LinkedList for a FIFO queue?

level: seniorimportance: should knowfreq 45%

basics

~20 s

ArrayDeque is a resizable circular-array Deque. Holding references in one array, it is likely faster and lighter than LinkedList, which wraps every element in a two-pointer node, so it is the better default for a plain queue.

open as a page

Given a concurrency or capacity requirement, how do you choose among Queue/Deque implementations (ArrayDeque, PriorityQueue, the concurrent and blocking variants)?

level: seniorimportance: should knowfreq 40%

basics

~20 s

For a single-threaded queue or stack use ArrayDeque. For priority ordering use PriorityQueue. For multiple threads use a concurrent queue like ConcurrentLinkedQueue, and when you need blocking/capacity limits use a BlockingQueue such as ArrayBlockingQueue or LinkedBlockingQueue.

open as a page