Java ArrayDeque as Stack and Queue Explained

Introduction

The Java ArrayDeque class was added to the collections framework in Java 6 (2006) under bug JDK-6323346, completing the Deque interface that had been requested for years. ArrayDeque is a resizable-array implementation of the Deque interface with no capacity restrictions, growing as needed to absorb new elements. It offers amortised O(1) performance for addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast. The class is not thread-safe; the thread-safe counterpart is ConcurrentLinkedDeque and LinkedBlockingDeque. The java arraydeque implementation is the recommended Stack replacement and the recommended single-threaded Queue replacement, dethroning both the legacy Stack class and the use of LinkedList as a queue.

For a Java learner, ArrayDeque is the right tool whenever you need a stack (LIFO), a queue (FIFO), or a double-ended queue (deque) without random access in the middle. Two legacy options used to fill this niche: java.util.Stack, which extends Vector and is synchronised on every operation, and java.util.LinkedList used as a Queue or Deque, which allocates a Node object per element. ArrayDeque beats both: it is faster than Stack because there is no synchronisation overhead, and it is faster than LinkedList because contiguous arrays pack better in CPU cache lines. This post walks through the circular-buffer implementation and demonstrates both stack and queue idioms.

What is Java ArrayDeque?

The java arraydeque class is an array-backed implementation of the java.util.Deque interface. The Deque interface (pronounced "deck") specifies a linear collection that supports element insertion and removal at both ends. ArrayDeque provides six core methods in three pairs: addFirst and addLast, removeFirst and removeLast, peekFirst and peekLast. The class also exposes the historical Queue methods (offer, poll, peek) and the historical Stack methods (push, pop, peek) for backward compatibility, all of which map onto the underlying six.

ArrayDeque belongs to the array-based collection family alongside ArrayList and ArrayBlockingQueue. It is distinct from LinkedList (which also implements Deque) because ArrayDeque uses a single Object array rather than a doubly linked list of Node objects. It is distinct from ArrayBlockingQueue because ArrayDeque is unbounded and not thread-safe; ArrayBlockingQueue is bounded and thread-safe. The class disallows null elements because null is used as a sentinel in some internal operations and because allowing null would make peek ambiguous.

How Java ArrayDeque Works - Step by Step

Step 1: The backing array is treated as a circular buffer with two indices, head and tail. The head index points to the first occupied slot; the tail index points to the next free slot at the end. Adding at the head decrements head (with wraparound via modulo arithmetic); adding at the tail writes to slot tail and increments tail. Both operations are O(1) amortised.

Step 2: When head and tail would collide, the buffer is full. ArrayDeque doubles the capacity by allocating a new array and copying elements in linear order starting from head, so that the new array has head at index 0 and tail at the logical end. This copy is O(n), but it happens rarely (every n inserts), so amortised cost per insert is O(1).

Step 3: push(x) is exactly addFirst(x). The element is written to slot (head - 1 + length) modulo length, and head is updated. This is the LIFO end. pop() is removeFirst(): read slot head, null it out to allow garbage collection, then increment head.

Step 4: offer(x) is exactly addLast(x). The element is written to slot tail, then tail is incremented with wraparound. This is the FIFO end. poll() is removeFirst(), the same as pop(). This convention makes ArrayDeque a drop-in replacement for the Queue interface used in producer-consumer pipelines.

Step 5: Iteration is O(n) and walks the circular buffer from head to tail, normalising the index arithmetic so that the iteration order is logical (first to last) rather than physical (slot 0 to slot length-1). The iterator is a snapshot-style iterator: it does not throw ConcurrentModificationException on subsequent modification, but it does not reflect later changes either.

Java Program for ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        // Use as a Stack (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        stack.push("first-in");
        stack.push("second-in");
        stack.push("third-in");
        System.out.println("Stack pop order:");
        while (!stack.isEmpty()) System.out.println("  " + stack.pop());

        // Use as a Queue (FIFO)
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first-in");
        queue.offer("second-in");
        queue.offer("third-in");
        System.out.println("Queue poll order:");
        while (queue.peek() != null) System.out.println("  " + queue.poll());

        // Use as a Deque (both ends)
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addFirst(2);
        deque.addLast(5);
        deque.addFirst(1);
        deque.addLast(6);
        deque.addFirst(0);
        System.out.println("Deque front-to-back:");
        for (Integer v : deque) System.out.print(v + " ");
        System.out.println();
        System.out.println("Remove from both ends:");
        System.out.println("  pollFirst = " + deque.pollFirst());
        System.out.println("  pollLast  = " + deque.pollLast());
    }
}

Code Explanation - Line by Line

The first block uses ArrayDeque as a Stack. The push method calls addFirst under the hood, prepending the element to the head of the circular buffer. The pop method calls removeFirst, which reads and clears slot head. The result is last-in-first-out behaviour: the third-in element comes out first, then the second-in, then the first-in. The Deque interface type is used as the compile-time type so that swapping to LinkedList is a one-character change.

The second block uses ArrayDeque as a Queue. The offer method calls addLast, appending to the tail of the circular buffer. The poll method calls removeFirst, reading the head. The result is first-in-first-out behaviour: the first-in element comes out first, then the second-in, then the third-in. The peek() guard in the while loop avoids the NoSuchElementException that would be thrown by the no-arg remove on an empty queue.

The third block uses ArrayDeque as a true double-ended queue, mixing addFirst and addLast calls. The order of insertions interleaves front and back so that the final buffer reads 0, 1, 2, 5, 6 from front to back. The for-each loop walks the logical order, not the physical slot order, so the output is the same as if you had called pollFirst repeatedly until empty.

The pollFirst and pollLast methods at the end demonstrate removal from both ends. pollFirst removes index 0 (the 0), and pollLast removes the last index (the 6). After these two removals, the deque would contain 1, 2, 5 in logical order. The same pattern underlies palindromic checking, sliding-window algorithms, and the work-queue stealer used by the ForkJoinPool.

Notice that no synchronisation is needed in this program. ArrayDeque is single-threaded by contract; if you need a thread-safe deque, switch to ConcurrentLinkedDeque for non-blocking code or LinkedBlockingDeque for a blocking variant with bounded capacity.

Sample Input and Output

Input:
  Stack pushes: "first-in", "second-in", "third-in"
  Queue offers: "first-in", "second-in", "third-in"
  Deque ops: addFirst(2), addLast(5), addFirst(1), addLast(6), addFirst(0)

Output:
  Stack pop order:
    third-in
    second-in
    first-in
  Queue poll order:
    first-in
    second-in
    third-in
  Deque front-to-back:
    0 1 2 5 6
  Remove from both ends:
    pollFirst = 0
    pollLast  = 6

The first block confirms that the Stack usage is LIFO: the last element pushed is the first popped. The second block confirms that the Queue usage is FIFO: the first element offered is the first polled. The third block confirms that mixing addFirst and addLast interleaves elements at the front and back as expected. The final two removals show that the front is index 0 and the back is index 6 after the interleaved inserts.

Common Mistakes to Avoid

Mistake 1: Using the legacy Stack class instead of ArrayDeque. The Stack class extends Vector, which means every method is synchronised on this. The synchronisation is wasted in single-threaded code and insufficient in multi-threaded code (you should use a BlockingQueue or a ConcurrentLinkedDeque instead). The Java documentation explicitly recommends ArrayDeque as the modern Stack replacement.

Mistake 2: Using LinkedList as a Queue for performance-critical code. LinkedList allocates a Node object per element, which puts pressure on the garbage collector and breaks CPU cache locality. ArrayDeque is consistently two to three times faster than LinkedList in micro-benchmarks of offer/poll workloads because it packs elements into a single backing array.

Mistake 3: Calling element() or getFirst() on an empty deque without try-catch. These methods throw NoSuchElementException; peek(), peekFirst(), and peekLast() return null. For non-throwing pipelines, prefer the peek/poll variants and check for null explicitly.

Mistake 4: Adding null elements. ArrayDeque disallows null and throws NullPointerException on any add, offer, push, addFirst, or addLast call with a null argument. The reason is partly that null is used as a sentinel in some internal operations, and partly that allowing null would make peek return values ambiguous. If you need a nullable deque, wrap the elements in Optional or use a sentinel object of your own.

Real-World Applications

ArrayDeque is the default Stack replacement in modern Java codebases. Spring Framework's internal expression evaluator uses ArrayDeque for operand and operator stacks during parsing. The Java compiler itself uses ArrayDeque internally for token buffering. Anywhere you see explicit LIFO or FIFO control flow, ArrayDeque is the right data structure.

Tree traversal algorithms use ArrayDeque as the work queue. Breadth-first search uses ArrayDeque as a FIFO queue (offer at the tail, poll from the head); depth-first search uses ArrayDeque as a LIFO stack (push at the head, pop from the head). The same data structure serves both patterns with a change of method names, which is a major ergonomic win.

Sliding-window algorithms use ArrayDeque as a monotonic queue. The classic example is "sliding window maximum" where a deque stores indices in decreasing order of value, allowing O(1) amortised query of the maximum of every window. The same pattern appears in LeetCode-style problems and in production code that processes streaming time-series data.

Work-stealing schedulers such as the one inside ForkJoinPool use a deque per worker thread. Each worker pushes new tasks onto the private end (the tail) and pops them from the same end (LIFO for cache locality); when idle, a worker steals from the front (head) of another worker's deque. ArrayDeque is the single-threaded analogue of this pattern; the production version uses a specialised padded deque that avoids false sharing on multi-core CPUs.

Conclusion

The java arraydeque class is an array-backed circular-buffer implementation of the Deque interface. It serves as a faster Stack than the legacy Stack class and as a faster Queue than LinkedList, with amortised O(1) performance at both ends. To go further, study ConcurrentLinkedDeque for the non-blocking thread-safe variant and LinkedBlockingDeque for the blocking bounded variant used in producer-consumer pipelines.