Skip to content
Java collections 5 min read

Deque & ArrayDeque

A Deque (pronounced “deck”) is a double-ended queue — a data structure where you can add or remove elements from both ends in constant time. Java’s ArrayDeque is the fastest general-purpose implementation and is the recommended replacement for both Stack and LinkedList when you need queue or stack behavior.

The Deque Interface

Deque<E> lives in java.util and extends the Queue interface. It adds mirror-image methods for the front (head) and back (tail) of the collection.

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

public class DequeIntro {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        deque.addFirst("B");   // [B]
        deque.addLast("C");    // [B, C]
        deque.addFirst("A");   // [A, B, C]

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

Output:

[A, B, C]
A
C

ArrayDeque: The Go-To Implementation

ArrayDeque<E> backs the deque with a resizable circular array. It is:

  • Faster than LinkedList for most use cases (no node allocation overhead)
  • Faster than Stack for stack operations (Stack is synchronized; ArrayDeque is not)
  • Not thread-safe (use java.util.concurrent.LinkedBlockingDeque for concurrent access)
  • Does not allow null elements
import java.util.ArrayDeque;

public class ArrayDequeBasics {
    public static void main(String[] args) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        // Add to both ends
        dq.offerFirst(10);
        dq.offerLast(20);
        dq.offerFirst(5);

        System.out.println(dq);              // [5, 10, 20]
        System.out.println(dq.pollFirst());  // 5
        System.out.println(dq.pollLast());   // 20
        System.out.println(dq);              // [10]
    }
}

Output:

[5, 10, 20]
5
20
[10]

Key Methods at a Glance

Deque gives you paired methods — one for each end — in two flavors: exception-throwing and null/false-returning.

OperationHead (throws)Head (safe)Tail (throws)Tail (safe)
InsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)
RemoveremoveFirst()pollFirst()removeLast()pollLast()
ExaminegetFirst()peekFirst()getLast()peekLast()

Tip: Prefer the offer/poll/peek family — they return null or false instead of throwing NoSuchElementException when the deque is empty, making your code easier to write defensively.

Using ArrayDeque as a Stack

Before Java 1.6, Stack was the standard. Today, ArrayDeque is the recommended substitute because it is unsynchronized (and therefore faster in single-threaded code).

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

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        // push = addFirst
        stack.push("first");
        stack.push("second");
        stack.push("third");

        // pop = removeFirst
        System.out.println(stack.pop()); // third
        System.out.println(stack.pop()); // second
        System.out.println(stack.peek()); // first (not removed)
    }
}

Output:

third
second
first

Note: push() and pop() are convenience aliases for addFirst() and removeFirst(). The Deque Javadoc explicitly recommends ArrayDeque over Stack for stack use cases.

Using ArrayDeque as a Queue

When used as a standard FIFO queue, add to the tail and remove from the head:

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

public class DequeAsQueue {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();

        // enqueue (add to tail)
        queue.offerLast("Task-1");
        queue.offerLast("Task-2");
        queue.offerLast("Task-3");

        // dequeue (remove from head)
        while (!queue.isEmpty()) {
            System.out.println("Processing: " + queue.pollFirst());
        }
    }
}

Output:

Processing: Task-1
Processing: Task-2
Processing: Task-3

Iterating Over a Deque

You can iterate in both directions. ArrayDeque also implements Iterable, so the for-each loop works naturally:

import java.util.ArrayDeque;
import java.util.Iterator;

public class DequeIteration {
    public static void main(String[] args) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.offerLast(1);
        dq.offerLast(2);
        dq.offerLast(3);

        // Forward (head → tail)
        System.out.print("Forward: ");
        for (int n : dq) System.out.print(n + " ");

        // Reverse (tail → head)
        System.out.print("\nReverse: ");
        Iterator<Integer> it = dq.descendingIterator();
        while (it.hasNext()) System.out.print(it.next() + " ");
    }
}

Output:

Forward: 1 2 3 
Reverse: 3 2 1

Practical Example: Balanced Parentheses Checker

A classic stack algorithm that showcases ArrayDeque in real use:

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

public class BalancedParens {
    public static boolean isBalanced(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : expr.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{')) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("{[()]}"));   // true
        System.out.println(isBalanced("{[(])}"));   // false
        System.out.println(isBalanced("((()"));     // false
    }
}

Output:

true
false
false

Constructors

ArrayDeque has three constructors:

// Default capacity (16 slots internally)
ArrayDeque<String> dq1 = new ArrayDeque<>();

// Hint the initial capacity (avoids early resizing)
ArrayDeque<String> dq2 = new ArrayDeque<>(32);

// Copy from any Collection
List<String> list = List.of("x", "y", "z");
ArrayDeque<String> dq3 = new ArrayDeque<>(list);

Tip: If you know you’ll store roughly n elements, pass n as the initial capacity. This avoids internal array copies during growth — each resize doubles the array.

Under the Hood

ArrayDeque uses a circular buffer (a plain Object[]) with two int pointers: head and tail.

  • Add to tail: store at tail, increment tail (mod capacity).
  • Add to head: decrement head (mod capacity), store there.
  • Remove from head/tail: read, clear the slot, advance the pointer.

Because both operations only move a pointer, they run in O(1) amortized time. When the array fills up, ArrayDeque allocates a new array of double the size and copies elements into the front half — just like ArrayList, but using System.arraycopy for the copy.

Why faster than LinkedList?

LinkedList allocates a Node object for every element. ArrayDeque stores raw references in a contiguous array, which is CPU cache-friendly. Modern CPUs prefetch sequential memory, so iteration and access on ArrayDeque are significantly faster in practice.

Memory comparison (approximate, 64-bit JVM with compressed oops):

StructurePer-element overhead
ArrayDeque~4 bytes (reference in array)
LinkedList~48 bytes (Node object: prev + next + item + header)

Warning: ArrayDeque is not synchronized. If multiple threads share one instance, wrap it with Collections.synchronizedDeque() or switch to java.util.concurrent.LinkedBlockingDeque.

Choosing Between Implementations

ScenarioBest choice
Single-threaded stackArrayDeque
Single-threaded FIFO queueArrayDeque
Double-ended operationsArrayDeque
Need index-based accessArrayList or LinkedList
Thread-safe bounded queueArrayBlockingQueue
Thread-safe unbounded dequeLinkedBlockingDeque
  • Queue & PriorityQueue — the single-ended sibling of Deque and priority-based ordering
  • Stack — the legacy stack class that ArrayDeque replaces
  • LinkedList — also implements Deque, but with node-based storage
  • ArrayList — resizable array for index-based access needs
  • Collections Utility Class — sorting, shuffling, and wrapping collections including deques
  • Iterator — how to traverse collections including descendingIterator() on a Deque
Last updated June 13, 2026
Was this helpful?