ArrayDeque Class in Java

Push a million elements onto an ArrayDeque and pop them all: isEmpty() returns true, yet the deque still holds an internal array with more than a million cells. ArrayDeque grows automatically but never shrinks, and unlike ArrayList it has no trimToSize(). Details like this are what the Deque interface does not tell you about its most popular implementation.

ArrayDeque (java.util.ArrayDeque, short for “array double-ended queue”) is a Java 6 class that implements the Deque interface on top of a resizable circular array. Adding and removing elements at both ends takes amortized O(1) time, which makes ArrayDeque the standard choice for a stack and for a FIFO queue in single-threaded code. It does not accept null elements and is not thread-safe.

The methods of the Queue and Deque interfaces — offer(), poll(), peek(), push(), pop() and their First/Last variants — are explained in Queue and Deque Interfaces in Java. This lesson is about how they behave in ArrayDeque specifically.

How ArrayDeque works: a circular array

Inside an ArrayDeque there is a plain Object[] array and two indexes: head and tail. The array is treated as a circle (a ring buffer): when adding at the front moves the index below zero, the element goes into the last cell. That is why adding and removing at either end never shifts the other elements.

Here is a simplified 8-cell array after the calls addLast("A"), addLast("B"), addLast("C") and addFirst("Z"):

index:    0     1     2     3     4     5     6     7
        [ A ] [ B ] [ C ] [   ] [   ] [   ] [   ] [ Z ]
                          ^ tail                  ^ head

addFirst() moved head from 0 to 7, wrapping around the end of the array, while addLast() writes into the tail cell and moves it to the right. The logical order of the elements runs from head around the circle to tail:

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

public class RingBufferDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addLast("A");
        deque.addLast("B");
        deque.addLast("C");
        deque.addFirst("Z");

        System.out.println(deque);                                      // [Z, A, B, C]
        System.out.println(deque.peekFirst() + " " + deque.peekLast()); // Z C
    }
}

Output:

[Z, A, B, C]
Z C

When the array fills up, ArrayDeque allocates a larger one and copies the elements into it. The copy is O(n), but it happens rarely, so adding stays O(1) on average. This is the key difference from ArrayList: a list always keeps its data starting at index 0, so remove(0) shifts the whole array (see How ArrayList works: capacity vs size).

ArrayDeque constructors and capacity

ArrayDeque has three constructors: an empty deque with room for 16 elements, an empty deque with a given initial capacity, and a deque that copies the elements of another collection. Capacity is the size of the internal array, not a limit: the deque grows automatically when it is full.

How the array grows depends on the JDK version. In Java 8 the capacity was always rounded up to a power of two (at least 8) and doubled when full. In modern JDKs (checked on JDK 22) the array always has one more cell than the number of elements it can hold, because one cell stays empty: new ArrayDeque<>() allocates 17 cells for 16 elements, and new ArrayDeque<>(n) allocates n + 1. While the array is smaller than 64 cells it grows to twice its size plus 2, after that by 50%: 17 → 36 → 74 → 111 → 166. The array never shrinks: after poll() or clear() the freed cells are set to null, but the array keeps its length.

ArrayDeque example: queue and stack

The same ArrayDeque class works both as a LIFO stack and as a FIFO queue — it depends only on which methods you call: push()/pop() work with the head, while add() appends to the tail and remove() takes from the head. Declare the variable with the interface type Deque or Queue.

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>(2);
        stack.push("A");
        stack.push("B");
        stack.push("C");
        stack.push("D");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();

        queue.add("A");
        queue.add("B");
        queue.add("C");
        queue.add("D");
        while (!queue.isEmpty()) {
            System.out.print(queue.remove() + " ");
        }
    }
}

Output:

D C B A
A B C D

The stack returned the elements in reverse order: the last one pushed, "D", came out first. The queue kept the insertion order. Note that queue was created with an initial capacity of 2 and still accepted four elements without any error — the array grew by itself.

ArrayDeque as a stack: checking balanced brackets

A classic stack task is checking that the brackets in a string are properly nested. Push every opening bracket; on a closing bracket, pop the top and check that it belongs to the same pair:

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

public class BracketChecker {
    static boolean isBalanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;          // closing bracket without a pair
                }
                char open = stack.pop();
                if ((c == ')' && open != '(')
                        || (c == ']' && open != '[')
                        || (c == '}' && open != '{')) {
                    return false;          // brackets of different kinds
                }
            }
        }
        return stack.isEmpty();            // any brackets left unclosed?
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("list.get(map[key])"));
        System.out.println(isBalanced("{[}]"));
        System.out.println(isBalanced("(("));
        System.out.println(isBalanced(")("));
    }
}

Output:

true
false
false
false

The stack.isEmpty() check before pop() is essential: for the string ")(" without it, pop() on an empty stack would throw NoSuchElementException. As a queue, ArrayDeque is used, for example, in breadth-first traversal of a tree or graph: offer() to the tail, poll() from the head.

ArrayDeque methods and their time complexity

ArrayDeque implements every method of Deque, Queue and Collection; the only public method it adds on top of the interfaces is clone(). Operations at the ends run in O(1), while anything that has to search for an element inside the deque is O(n). There are no index-based methods such as get(int) or set(int, E).

What each method does and how the offer/add and poll/remove pairs differ is shown in the tables of Deque interface in Java. The full API is in the ArrayDeque Javadoc.

null, contains() and equals(): ArrayDeque quirks

ArrayDeque does not store null because empty cells of the circular array are marked with null, and poll() and peek() return null to signal an empty deque. In addition, the class does not override equals() and hashCode(), so two deques are compared by reference.

The ban applies only to writing: offer(null), push(null) and addLast(null) throw NullPointerException, while contains(null) and remove(null) simply return false. Why null in a queue is dangerous and how it breaks a poll() loop is shown in Queue and null: when poll() misleads you.

What does this code print?

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class DequeEquals {
    public static void main(String[] args) {
        Deque<Integer> a = new ArrayDeque<>(List.of(1, 2, 3));
        Deque<Integer> b = new ArrayDeque<>(List.of(1, 2, 3));

        System.out.println(a.equals(b));
        System.out.println(List.copyOf(a).equals(List.copyOf(b)));
        System.out.println(Arrays.equals(a.toArray(), b.toArray()));
        System.out.println(new LinkedList<>(a).equals(new LinkedList<>(b)));
    }
}

Output:

false
true
true
true

ArrayDeque inherits equals() from Object, so a.equals(b) is true only for the same object (the general rule for collections is in When two collections are equal). To compare contents, convert the deques to lists or arrays — the head-to-tail order is preserved. For the same reason an ArrayDeque cannot serve as a HashMap key or a HashSet element if you expect content-based comparison. LinkedList does not have this problem: it implements List and compares elements.

Thread safety and fail-fast iterators

ArrayDeque is not thread-safe: if two threads add or remove elements at the same time, the head and tail indexes can get out of sync with the array contents, and elements are lost. For a queue shared between threads use ConcurrentLinkedDeque or the blocking LinkedBlockingDeque.

The iterators of ArrayDeque are fail-fast: if the deque is modified during iteration other than through iterator.remove(), the iterator usually throws ConcurrentModificationException. The documentation stresses that this is a best-effort check: the exception is not guaranteed, so program logic must never depend on it.

ArrayDeque vs LinkedList vs Stack

For a stack or a queue in single-threaded code, ArrayDeque is the best fit: its Javadoc states that it is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue. Choose LinkedList when you need null elements or the List interface; Stack belongs only in legacy code.

Why ArrayDeque beats LinkedList although both are O(1) at the ends comes down to memory: array elements sit next to each other and stay in the CPU cache, while LinkedList allocates a separate node object for every element and puts extra load on the garbage collector. The performance of all collection classes side by side is in Choosing an implementation.

When to use ArrayDeque

Use ArrayDeque by default whenever single-threaded code needs a stack (undo history, depth-first search, expression parsing) or a FIFO queue (breadth-first search, a task buffer, a sliding window of the last N values). Pick another implementation only when one of the requirements below directly contradicts its properties.