Java Queue and Deque Tutorial with Examples

Queue is an interface with an unusual property: most of its operations exist twice, once throwing on failure and once returning a sentinel. Knowing which pair you are using is the difference between a loop that terminates and one that throws at the end of the data.

Written against Java 17.

Two method families

Purpose	Throws on failure	Returns a value
insert	add(e)	offer(e) → false
remove head	remove()	poll() → null
inspect head	element()	peek() → null

Queue<String> queue = new ArrayDeque<>();

queue.offer("a");
String head = queue.poll();      // "a"
String none = queue.poll();      // null — empty queue
String boom = queue.remove();    // NoSuchElementException

Use offer/poll/peek almost always. The draining idiom depends on it:

String task;
while ((task = queue.poll()) != null) {
    process(task);
}

add/remove/element exist because Queue extends Collection, whose contract requires them to throw. They are right when an empty queue is a programming error rather than an expected state.

Note the consequence for null elements: a queue that permits null makes poll() ambiguous — you cannot tell an empty queue from a queue whose head is null. ArrayDeque and the concurrent queues reject null for exactly that reason. LinkedList allows it, which is one more reason not to use it as a queue.

ArrayDeque is the default

Queue<String> queue = new ArrayDeque<>();       // FIFO
Deque<String> stack = new ArrayDeque<>();       // LIFO

ArrayDeque is a growable circular array. Adding and removing at either end is amortised O(1), it has excellent cache locality, and it allocates nothing per element.

LinkedList also implements Queue, and is worse at it: every element is a node with two pointers and an object header, which multiplies memory and scatters access across the heap. It permits null, losing the poll() sentinel. Its only genuine advantage — O(1) removal from the middle given an iterator — is irrelevant to queue use.

Stack is worse still. It is a legacy class extending Vector, synchronised on every method, and it iterates bottom-to-top — the opposite of pop order, which is a real source of confusion. Use ArrayDeque as a stack:

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.pop();        // "b" — LIFO
stack.peek();       // "a"

Deque: both ends, explicitly

Deque<Integer> d = new ArrayDeque<>();

d.offerFirst(1);
d.offerLast(2);
d.peekFirst();     // 1
d.pollLast();      // 2

Deque names the end in every method, which is worth preferring over the inherited Queue and Stack-style aliases — push is addFirst and add is addLast, and reading a mix of the three styles in one file is how off-by-one-end bugs happen.

A sliding-window maximum is the classic use, holding indices in decreasing order of value:

static int[] maxInWindow(int[] a, int k) {
    Deque<Integer> window = new ArrayDeque<>();
    int[] out = new int[a.length - k + 1];

    for (int i = 0; i < a.length; i++) {
        while (!window.isEmpty() && window.peekFirst() <= i - k) {
            window.pollFirst();                       // fell out of the window
        }
        while (!window.isEmpty() && a[window.peekLast()] <= a[i]) {
            window.pollLast();                        // can never be the max again
        }
        window.offerLast(i);
        if (i >= k - 1) {
            out[i - k + 1] = a[window.peekFirst()];
        }
    }
    return out;
}

O(n), because each index is added and removed at most once.

PriorityQueue is not a queue

Queue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5, 1, 4, 2));

pq.poll();     // 1
pq.poll();     // 2  — smallest first, not insertion order

It is a binary heap. poll returns the smallest element by natural ordering, or by a comparator:

Queue<Task> byPriority = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority).reversed()
                  .thenComparing(Task::createdAt));

Two properties that surprise people, and both are documented rather than bugs:

Iteration order is not sorted.

Queue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2));
System.out.println(pq);              // [1, 2, 4, 5] — for this input
pq.forEach(System.out::print);       // heap order, NOT sorted in general

Only the head is guaranteed to be the minimum. The array is heap-ordered, not fully ordered, so printing a PriorityQueue or streaming it gives an order that looks arbitrary. To iterate in priority order you must drain it with poll, which empties it.

Ties are broken arbitrarily. Two elements comparing equal come out in no defined order, and it is not insertion order. For a stable priority queue, add a monotonic sequence number as the final comparator key.

peek and poll are O(1) and O(log n); contains and remove(Object) are O(n).

Blocking queues

BlockingQueue adds operations that wait, which is what makes it the handoff between producer and consumer threads:

BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);

// producer
queue.put(task);                               // blocks while full

// consumer
Task t = queue.take();                         // blocks while empty

// with a timeout
Task maybe = queue.poll(500, TimeUnit.MILLISECONDS);   // null on timeout
boolean added = queue.offer(task, 1, TimeUnit.SECONDS);

Bound it. That is the single most important decision here:

new ArrayBlockingQueue<>(1000)          // bounded: put() blocks when full
new LinkedBlockingQueue<>()             // UNBOUNDED by default
new LinkedBlockingQueue<>(1000)         // bounded

An unbounded queue converts backpressure into memory consumption. When consumers cannot keep up, the queue grows until the heap is exhausted — and the failure is an OutOfMemoryError far from the cause, rather than a producer slowing down where the problem is.

This is also the default trap in Executors:

// unbounded queue: tasks accumulate without limit
ExecutorService a = Executors.newFixedThreadPool(4);

// bounded, with an explicit policy for what happens when it is full
ExecutorService b = new ThreadPoolExecutor(
        4, 4, 0L, TimeUnit.MILLISECONDS,
        new ArrayBlockingQueue<>(500),
        new ThreadPoolExecutor.CallerRunsPolicy());

newFixedThreadPool uses an unbounded LinkedBlockingQueue. CallerRunsPolicy is the useful rejection handler: the submitting thread executes the task itself, which naturally slows the producer down instead of queueing more work.

The specialised implementations:

• SynchronousQueue — zero capacity. Every put waits for a take. Direct handoff, used by newCachedThreadPool.
• PriorityBlockingQueue — unbounded priority heap with blocking take.
• DelayQueue — elements become available only after their delay expires. A scheduler primitive.
• LinkedTransferQueue — transfer waits until a consumer receives the element.

Non-blocking concurrent queues

Queue<String> q = new ConcurrentLinkedQueue<>();
Deque<String> d = new ConcurrentLinkedDeque<>();

Lock-free, unbounded, thread-safe. poll returns null when empty rather than blocking, so a consumer must poll in a loop — which burns CPU if it spins. Use these when consumers have other work to do; use a BlockingQueue when they would otherwise just wait.

Both have an O(n) size(), because there is no consistent count to keep in a lock-free structure. Calling size() in a loop condition on a hot path is a real performance mistake.

Choosing

Need	Use
Plain FIFO, single thread	ArrayDeque
Stack, single thread	ArrayDeque (never Stack)
Order by priority	PriorityQueue
Producer/consumer with backpressure	ArrayBlockingQueue (bounded)
Producer/consumer, unbounded and accepted	LinkedBlockingQueue
Direct handoff, no buffering	SynchronousQueue
Concurrent, consumers have other work	ConcurrentLinkedQueue
Timed release	DelayQueue

Frequently asked questions

What is the difference between add and offer?

add throws when insertion fails (a bounded queue that is full); offer returns false. Same for remove/poll and element/peek, where the second returns null.

Which should I use?

offer/poll/peek in most code — they make an empty or full queue an ordinary condition rather than an exception.

Why does poll() returning null matter?

It is the drain idiom: while ((x = q.poll()) != null). It only works because the queue rejects null elements, which is why ArrayDeque does.

ArrayDeque or LinkedList for a queue?

ArrayDeque. Better locality, no per-element node, and it rejects null so poll is unambiguous. LinkedList’s advantages do not apply to queue use.

Why not use Stack?

It is legacy, synchronised on every method, and iterates bottom-to-top rather than in pop order. ArrayDeque is the modern replacement.

Why is my PriorityQueue not printing in sorted order?

Only the head is guaranteed to be the minimum. The backing array is heap-ordered, not sorted. Drain with poll to get priority order.

How do I break ties in a PriorityQueue?

Add a monotonically increasing sequence number as the last comparator key. Equal elements otherwise come out in no defined order.

Should my BlockingQueue be bounded?

Almost always. An unbounded queue turns a slow consumer into an OutOfMemoryError instead of backpressure on the producer.

Why does newFixedThreadPool queue without limit?

It uses an unbounded LinkedBlockingQueue. Construct a ThreadPoolExecutor with a bounded queue and a rejection policy — CallerRunsPolicy slows the submitter down.

Is ConcurrentLinkedQueue.size() cheap?

No, it is O(n). A lock-free queue keeps no consistent count. Do not call it in a loop condition.

Where should I go next?

ArrayList and HashMap cover the other core collections, and Java concurrency basics covers the threading these blocking queues coordinate.