skip to content

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%

answer

  1. Three axes: ordering, concurrency, capacity/blocking
  2. ArrayDeque single-thread; PriorityQueue = binary heap, least-first, not FIFO/not thread-safe
  3. ConcurrentLinkedQueue/Deque = lock-free, unbounded, non-blocking
  4. BlockingQueue adds put/take (block) + timed offer/poll: ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, DelayQueue, SynchronousQueue
  5. SynchronousQueue = zero capacity hand-off; DelayQueue = available after delay

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.

solid answer

~40 s

Pick by three axes: ordering, concurrency, and capacity. For single-threaded FIFO or LIFO, ArrayDeque is the default (fast, unsynchronized). When elements must come out by priority rather than insertion order, use PriorityQueue, a binary-heap implementation where poll returns the least element by natural ordering or a Comparator (it is not FIFO and is not thread-safe). For concurrent access without blocking, ConcurrentLinkedQueue (and ConcurrentLinkedDeque) are lock-free, unbounded, high-throughput choices. When you need producer-consumer back-pressure or bounded capacity, use a BlockingQueue: ArrayBlockingQueue (bounded, array-backed), LinkedBlockingQueue (optionally bounded), PriorityBlockingQueue (unbounded priority), DelayQueue (elements available after a delay), and SynchronousQueue (zero capacity, a direct hand-off). Blocking queues add put/take, which block when full/empty, and offer/poll overloads with timeouts. Match the structure to whether you need ordering, thread safety, blocking semantics, and a capacity bound.

code

java · 16 lines
java
// Priority ordering (min-heap by default)
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll();  // 1 (least), not insertion order

// Bounded producer-consumer with back-pressure
BlockingQueue<Task> work = new ArrayBlockingQueue<>(100);
// producer thread:
work.put(task);     // blocks if 100 items already queued
// consumer thread:
Task t = work.take(); // blocks until an item is available

// Lock-free concurrent FIFO, unbounded
Queue<Event> events = new ConcurrentLinkedQueue<>();
events.offer(e);    // never blocks
Event next = events.poll(); // null if empty

go deeper

for a junior

Can pick ArrayDeque for simple queues and knows PriorityQueue exists for priority ordering.

for a middle

Distinguishes single-threaded vs concurrent needs and knows BlockingQueue offers put/take for producer-consumer scenarios.

for a senior

Selects correctly across ordering/concurrency/capacity axes, knows the main implementations and their bounded/unbounded and blocking traits, and uses offer/put appropriately for back-pressure.

for a principal

Designs pipelines around the right queue (bounded blocking queues for back-pressure, SynchronousQueue for hand-off, ConcurrentLinkedQueue for lock-free throughput), reasons about size() approximation, fairness, and how thread-pool executors use these queues internally.

## The decision axes Choosing a queue/deque implementation comes down to a few orthogonal questions: 1. **Ordering**: FIFO? LIFO? By priority? 2. **Concurrency**: single-threaded, or accessed by multiple threads? 3. **Capacity & blocking**: unbounded, or bounded with back-pressure? Do producers/consumers need to *block* and wait? ## Single-threaded, no special ordering - **`ArrayDeque`** — the default for both FIFO queues and LIFO stacks. Resizable circular array, unsynchronized, amortized O(1) at both ends, cache-friendly. Use this unless a requirement pushes you elsewhere. - `LinkedList` — only if you also need `List` semantics or `null` storage (see the ArrayDeque-vs-LinkedList topic). ## Priority ordering - **`PriorityQueue`** — a **binary heap** (a tree-shaped array). `poll()` always returns the **least** element according to the elements' **natural ordering** (`Comparable`) or a supplied **`Comparator`**. It is **not FIFO** (insertion order is not preserved among unequal-priority items, and ties are not ordered), **not thread-safe**, and forbids `null`. Offer/poll are O(log n); peek is O(1). Use it for 'always process the highest-priority item next' (schedulers, Dijkstra, etc.). ## Concurrent, non-blocking When multiple threads share the queue and you want high throughput without locks: - **`ConcurrentLinkedQueue`** — an unbounded, **lock-free** (CAS-based) FIFO queue. Great for many producers/consumers; `size()` is O(n) and only approximate under concurrency. - **`ConcurrentLinkedDeque`** — the double-ended, lock-free counterpart (use as a concurrent stack/deque, e.g. work-stealing). These never block: `offer` always succeeds (unbounded), `poll` returns `null` when empty. ## Concurrent, blocking / bounded (`BlockingQueue`) The `java.util.concurrent.BlockingQueue` interface adds operations that **block**: - `put(e)` — blocks while the queue is full. - `take()` — blocks while the queue is empty. - timed `offer(e, time, unit)` / `poll(time, unit)` — block up to a timeout. This is the backbone of producer-consumer pipelines and thread-pool work queues, giving natural **back-pressure**. Implementations: - **`ArrayBlockingQueue`** — **bounded**, array-backed, single lock; fixed capacity set at construction; optional fairness. - **`LinkedBlockingQueue`** — linked nodes, **optionally bounded** (defaults to effectively unbounded `Integer.MAX_VALUE`); separate put/take locks for higher throughput. - **`PriorityBlockingQueue`** — an **unbounded**, thread-safe priority queue (blocking `take`, but `put` never blocks since it's unbounded). - **`DelayQueue`** — elements implement `Delayed`; an element is only available from `take`/`poll` **after its delay elapses**. Good for scheduled tasks/expirations. - **`SynchronousQueue`** — **zero capacity**: each `put` waits for a matching `take` (a direct hand-off). Used by cached thread pools. - **`LinkedBlockingDeque`** — a bounded, blocking **deque**. ## A quick decision guide - Single-thread FIFO/LIFO -> **ArrayDeque**. - Need priority order -> **PriorityQueue** (single-thread) or **PriorityBlockingQueue** (concurrent). - Concurrent, never block, unbounded -> **ConcurrentLinkedQueue/Deque**. - Producer-consumer with back-pressure / bounded -> **ArrayBlockingQueue** (fixed) or **LinkedBlockingQueue** (optionally bounded). - Direct hand-off, no buffering -> **SynchronousQueue**. - Time-delayed availability -> **DelayQueue**. ## Cross-cutting reminders - Most of these **forbid null** (it collides with the null-means-empty signal). `LinkedList` is the notable exception. - For bounded queues, prefer `offer` (or timed `offer`) over `add` so a full queue is a testable condition rather than an exception, and use `put` when you want the producer to block. - `size()` on concurrent queues may be approximate; don't use it for correctness.

  • What does poll() return from a PriorityQueue, and based on what ordering?
    The least element according to the elements' natural ordering (Comparable) or the Comparator supplied at construction. It is a min-heap by default, not FIFO.
  • Which BlockingQueue gives you a direct producer-to-consumer hand-off with no buffering, and where is it used?
    SynchronousQueue: it has zero capacity, so each put blocks until a take takes the element (and vice versa). Executors.newCachedThreadPool uses it to hand tasks straight to threads.
  • How does a BlockingQueue provide back-pressure?
    With a bounded capacity plus put()/take(): when the queue is full, producers calling put block until space frees up, throttling fast producers to consumer speed instead of growing memory without bound.

saying these in an interview costs you the question

  • Calling PriorityQueue FIFO or assuming ties keep insertion order
  • Using a plain ArrayDeque/PriorityQueue across threads without synchronization
  • Thinking ConcurrentLinkedQueue can be bounded or that its size() is exact
  • Believing SynchronousQueue can buffer one element (it has zero capacity)

context

resolving links…