Given a concurrency or capacity requirement, how do you choose among Queue/Deque implementations (ArrayDeque, PriorityQueue, the concurrent and blocking variants)?
answer
- Three axes: ordering, concurrency, capacity/blocking
- ArrayDeque single-thread; PriorityQueue = binary heap, least-first, not FIFO/not thread-safe
- ConcurrentLinkedQueue/Deque = lock-free, unbounded, non-blocking
- BlockingQueue adds put/take (block) + timed offer/poll: ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, DelayQueue, SynchronousQueue
- SynchronousQueue = zero capacity hand-off; DelayQueue = available after delay
basics
~20 sFor 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 sPick 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// 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 emptygo deeper
Can pick ArrayDeque for simple queues and knows PriorityQueue exists for priority ordering.
Distinguishes single-threaded vs concurrent needs and knows BlockingQueue offers put/take for producer-consumer scenarios.
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.
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` — when you also need `List` semantics, or `null` storage, which `Queue`'s Javadoc advises against. ## 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` never returns `false` (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`** — an **optionally bounded**, blocking **deque** (defaults to `Integer.MAX_VALUE`). ## 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.
- 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)
- java.util.concurrent.BlockingQueue
- Java 1.5
- java.util.ArrayDeque
- Java 1.6
context
- java.util.concurrent (Java SE 27 & JDK 27)docs.oracle.com
- BlockingQueue (Java SE 27 & JDK 27)docs.oracle.com
- ArrayDeque (Java SE 27 & JDK 27)docs.oracle.com