Java ArrayDeque

ArrayDeque<E> is a circular array that grows on demand. It implements both Queue<E> and Deque<E>, so it can play the role of FIFO queue, LIFO stack, or double-ended queue without code changes. The Javadoc on Stack recommends Deque over the legacy class; the Javadoc on Deque adds the practical recommendation that ArrayDeque should be your default implementation. It's almost always faster than LinkedList, smaller in memory, and the standard library's go-to once you stop needing the List interface.

Why a circular array

A classic "queue from an array" runs into a problem: after a few cycles of add-at-tail, remove-from-head, the array fills up at the tail while empty slots accumulate at the head. A naive fix would shift everything left on every dequeue — O(n) per remove, ruining performance.

The circular-array trick solves it. The class keeps two indices, head and tail, and lets them wrap around:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst decrements head, addLast increments tail, both modulo the array length. removeFirst and removeLast do the reverse. Every operation is O(1); the only cost is doubling the backing array when head would collide with tail, which is amortised away.

The result: no per-element node allocation, no pointer chasing, cache-friendly access. That's the engineering reason ArrayDeque is usually the fastest choice for queue and stack workloads.

The Deque interface refresher

A Deque has two ends. Every operation comes in three variants:

On top of that, the Queue and stack synonyms map onto the head end:

So Deque is one interface that exposes a queue and a stack at the same time, depending on which name you call the head by. We covered these mappings in the Queue and Stack chapters; Deque is where they meet.

What ArrayDeque adds on top

In practice, very little API-wise — that's the point. The class exposes the Deque contract honestly: the two ends, the three error styles per op, and a clear(), iterator(), descendingIterator(), contains, size, isEmpty. Iteration with the standard iterator goes head-to-tail; descendingIterator is the cheap way to walk tail-to-head without reversing.

The constructors mirror ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Pre-size when you know the workload. The default of 16 is rounded up to a power of two, and growth doubles the array — so a million offerLast calls from a default-sized deque triggers about 16 grow-and-copies.

The rules: no nulls, not thread-safe, fail-fast

Three rules you should internalise:

1. ArrayDeque does not allow null elements. Every insert throws NullPointerException. That's how pollFirst() returning null for empty stays unambiguous.
2. Not thread-safe. Two threads mutating the same ArrayDeque will corrupt it. For concurrent use, look at ConcurrentLinkedDeque (lock-free, unbounded) or LinkedBlockingDeque (bounded, blocking).
3. Fail-fast iteration. Modifying the deque outside the iterator while iterating throws ConcurrentModificationException. Use Iterator.remove() or removeIf for safe mutation.

When to pick ArrayDeque over alternatives

The decision flow:

• Need a Queue? → ArrayDeque. Default.
• Need a stack? → ArrayDeque. Default. Use push / pop / peek.
• Need a Deque? → ArrayDeque. Default.
• Need both Deque and List semantics on the same object? → LinkedList. Rare.
• Need a priority order? → PriorityQueue. Different abstraction.
• Need concurrent access? → ConcurrentLinkedDeque (unbounded) or LinkedBlockingDeque (bounded). The right choice depends on whether you need back-pressure.

The Javadoc spells out the recommendation in plain text: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." That's directly from the JDK authors; it's worth taking literally.

A worked example: queue, stack, deque, sliding window

The program below uses one ArrayDeque instance as a FIFO queue, another as a LIFO stack, and a third as the storage behind a sliding window maximum — a classic problem where ArrayDeque is the textbook answer because you need cheap mutation at both ends.

What you can take from this run:

• Sections 1 and 2 are the same class doing two jobs by calling different methods. FIFO queue: offerLast / pollFirst. LIFO stack: push / pop. There's no separate class to learn.
• descendingIterator() is the cheap reverse walk — useful when you've built a deque as a stack and want to print it bottom-to-top.
• The sliding-window function uses both ends in the same loop — pollFirst to drop indices that fell out of the window, pollLast to maintain a monotonic decreasing stack, peekFirst to read the current max. That dual-ended access is why ArrayDeque exists; trying to do this with an ArrayList would be quadratic.

What's next

You've seen how ArrayDeque implements both ends of the queue/stack story. The interface it's been implementing this whole time deserves its own chapter — Deque is the contract that ties together everything we've covered for queue-like collections. We pick that up next session.

Practice