ArrayDeque in Java
Introduction
In some scenarios, you need to add or remove elements from both ends of a queue—for example, managing browser history navigation (forward and back) or implementing a card sorting game.
To address this, Java provides the Deque (Double-Ended Queue) interface, and its most efficient implementation is ArrayDeque. An ArrayDeque uses a circular array buffer that dynamically expands as elements are added.
Why ArrayDeque?
ArrayDeque is highly versatile: it can act as a standard FIFO Queue, a Double-Ended Queue (Deque), or a LIFO Stack:
- Stack Performance:
ArrayDequeis significantly faster than the legacyStackclass because it is not synchronized. - Queue Performance: It is faster than
LinkedListbecause it stores elements in a contiguous array rather than allocating individual node objects.
The Deque Principle
A Deque supports insertion, deletion, and inspection operations at both the head (front) and tail (back):
Creating an ArrayDeque
1. Declaring as a Queue (FIFO Queue)
2. Declaring as a Deque (Double-Ended Queue)
import java.util.ArrayDeque;
import java.util.Deque;
Deque<String> doubleEndedQueue = new ArrayDeque<>();
3. Declaring as a Stack (LIFO Stack)
Common Methods
Because it is a double-ended queue, ArrayDeque provides dedicated methods for both ends:
Double-Ended Operations:
| Operation | Head (Front) | Tail (Back) |
|---|---|---|
| Insert | addFirst(e) / offerFirst(e) | addLast(e) / offerLast(e) |
| Remove | removeFirst() / pollFirst() | removeLast() / pollLast() |
| Examine | getFirst() / peekFirst() | getLast() / peekLast() |
Stack Operations:
push(e): Adds an element to the head (equivalent toaddFirst(e)).pop(): Removes and returns the head element (equivalent toremoveFirst()).
Complete Programs
Example: Using ArrayDeque as a Stack and Deque
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeDemo {
public static void main(String[] args) {
// 1. Using Deque for double-ended operations
Deque<String> deque = new ArrayDeque<>();
deque.addLast("Middle");
deque.addFirst("Front");
deque.addLast("Back");
System.out.println("Deque View: " + deque); // [Front, Middle, Back]
System.out.println("Polled Head: " + deque.pollFirst()); // Front
System.out.println("Polled Tail: " + deque.pollLast()); // Back
// 2. Using Deque as a Stack (LIFO)
Deque<String> stack = new ArrayDeque<>();
stack.push("Card A");
stack.push("Card B");
System.out.println("Stack View: " + stack); // [Card B, Card A]
System.out.println("Popped: " + stack.pop()); // Card B
}
}
Best Practices
- Use ArrayDeque for Stacks: Never use the legacy
java.util.Stackclass because its methods are synchronized, creating unnecessary overhead. UseArrayDequeinstead. - Specify Initial Capacity: If you know the maximum size, set it in the constructor to avoid array resizing:
Common Mistakes
- Stack Method Names: When using
ArrayDequeas a Stack, usepush()andpop()rather thanoffer()andpoll()to keep the LIFO stack behavior clear in your code. - No Null Elements:
ArrayDequedoes not allow null elements (throwsNullPointerExceptionbecausenullis used by methods likepoll()to indicate the queue is empty).
Key Takeaways
ArrayDequeimplements theDequeinterface, supporting double-ended operations.- It is the recommended implementation for Stacks and standard FIFO Queues.
- It performs basic operations in
O(1)constant time.
Back to Queues Home: Queues Index