Queues, Deques and BlockingQueues

Queues are where the collections framework meets concurrency. The interface itself is small; the interesting part is that every method comes in three variants, and choosing between them is how you decide what your system does when it is overloaded.

The three method families#

The blocking column exists only on BlockingQueue. That single distinction is the whole reason the interface hierarchy splits the way it does.

BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);
 
queue.add(task);                          // IllegalStateException if full — rarely what you want
boolean accepted = queue.offer(task);     // false if full — you decide what to do
queue.put(task);                          // waits for room — backpressure onto the producer
queue.offer(task, 100, MILLISECONDS);     // waits, then gives up — usually the best of the three

put is the one that shapes system behaviour. When the consumer falls behind, put blocks the producer, which slows the upstream source, which is exactly what you want — the alternative is accumulating work in memory until the process dies. That is backpressure, and being able to explain it in these terms is a strong interview answer.

Choosing a BlockingQueue#

ArrayBlockingQueue allocates its array up front, never resizes and produces no garbage per element. It uses a single lock for both ends, so a producer and a consumer contend with each other.

LinkedBlockingQueue uses two locks — one for the head, one for the tail — so a producer and a consumer can operate simultaneously. That makes it faster under contention, at the cost of a node allocation per element. Its capacity defaults to Integer.MAX_VALUE, which is where the danger is:

// Executors.newFixedThreadPool uses new LinkedBlockingQueue<Runnable>()
// — effectively unbounded. Tasks accumulate until OutOfMemoryError.
ExecutorService dangerous = Executors.newFixedThreadPool(10);
 
// Bounded, with an explicit answer for overload.
ExecutorService safe = new ThreadPoolExecutor(
        10, 10, 0L, MILLISECONDS,
        new LinkedBlockingQueue<>(1000),
        new ThreadPoolExecutor.CallerRunsPolicy());

This is covered in depth in ExecutorService and thread-pool sizing, and it is the single most consequential collections decision in a Java server.

SynchronousQueue#

SynchronousQueue<String> handoff = new SynchronousQueue<>();
 
handoff.offer("x");    // false — nobody is waiting to take
handoff.put("x");      // blocks until another thread calls take()

A SynchronousQueue holds nothing. Every put waits for a matching take, and vice versa. It is a rendezvous point rather than a buffer.

Its main appearance is inside Executors.newCachedThreadPool(): because the queue can never hold a task, submitting work either hands it directly to an idle thread or forces the pool to create a new one. That is why a cached pool grows without limit under load — and why it is unsuitable for a server with unpredictable traffic.

PriorityQueue#

Queue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
queue.addAll(List.of(new Task(5), new Task(1), new Task(3), new Task(2)));
 
queue.peek();       // priority 1 — the head is always the smallest
queue.toString();   // [1, 2, 3, 5] here, but heap order in general — NOT sorted
 
// The only way to get sorted output:
while (!queue.isEmpty()) process(queue.poll());

PriorityQueue is an array-backed binary min-heap. offer and poll are O(log n), peek is O(1), and remove(Object) is O(n) because it must search. It is unbounded and grows like an ArrayList.

Two facts that regularly appear as trick questions. Iteration order is not sorted — the iterator walks the backing array, which satisfies the heap property but nothing stronger. And it is not stable: two elements of equal priority come out in unspecified order, so if fairness matters, add a sequence number as a tie-break in the comparator.

PriorityBlockingQueue is the thread-safe version. Note it is unbounded, so it does not provide backpressure even though it is a BlockingQueue — put never blocks.

DelayQueue and scheduling#

record RetryTask(String id, Instant runAt) implements Delayed {
    @Override public long getDelay(TimeUnit unit) {
        return unit.convert(Duration.between(Instant.now(), runAt));
    }
    @Override public int compareTo(Delayed other) {
        return Long.compare(getDelay(NANOSECONDS), other.getDelay(NANOSECONDS));
    }
}
 
DelayQueue<RetryTask> retries = new DelayQueue<>();
retries.put(new RetryTask("order-1", Instant.now().plusSeconds(30)));
 
RetryTask due = retries.take();   // blocks for ~30 seconds, then returns

take() returns only elements whose delay has elapsed. This is the building block behind ScheduledThreadPoolExecutor, and it is a clean answer to "how would you implement a retry queue without a scheduler?" in a system-design round.

Deques, and the Stack question#

Deque allows insertion and removal at both ends, which makes it both a queue and a stack.

Deque<String> stack = new ArrayDeque<>();
stack.push("a");        // addFirst
stack.push("b");
stack.pop();            // removeFirst -> "b"
 
Deque<String> queue = new ArrayDeque<>();
queue.offer("a");       // addLast
queue.poll();           // removeFirst -> "a"

ArrayDeque is a resizable circular array with no per-element node allocation. It beats LinkedList as a deque and beats Stack as a stack — Stack extends Vector, so every operation is synchronised, and it iterates bottom-to-top, which is the opposite of what a stack should do.

The JDK documentation says so directly: "ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." Quoting that is a good way to close the "which stack implementation?" question.

ArrayDeque rejects null elements, because poll() returning null is how it signals emptiness.

Non-blocking concurrent queues#

Queue<Event> q = new ConcurrentLinkedQueue<>();       // unbounded, lock-free, FIFO
Deque<Event> d = new ConcurrentLinkedDeque<>();       // both ends

These use CAS rather than locks and never block, which suits a producer that must not be slowed down — an event bus, a metrics buffer. The trade-off is that they are unbounded, so they offer no backpressure, and size() is O(n) because it walks the chain. Never call size() on one in a hot path or a monitoring loop.

What gets asked#

The reliable questions are: the difference between add, offer and put; which BlockingQueue you would put behind a thread pool and why it must be bounded; and whether a PriorityQueue iterates in sorted order. The second is the one with real stakes — an unbounded queue turning a traffic spike into an OutOfMemoryError is a genuine production failure, covered in Thread-pool starvation.