1. Overview
An ArrayDeque (also known as an “Array Double Ended Queue”, pronounced as “ArrayDeck”) is a special kind of a growable array that allows us to add or remove an element from both sides.
An ArrayDeque implementation can be used as a Stack (Last-In-First-Out) or a Queue (First-In-First-Out). Example can be found here.
2. The API at a Glance
For each operation, we basically have two options.
The first group consists of methods that throw exception if the operation fails. The other group returns a status or a value:
| Operation | Method | Method Throwing Exception |
|---|---|---|
| Insertion from Head | offerFirst(e) | addFirst(e) |
| Removal from Head | pollFirst() | removeFirst() |
| Retrieval from Head | peekFirst | getFirst() |
| Insertion from Tail | offerLast(e) | addLast(e) |
| Removal from Tail | pollLast() | removeLast() |
| Retrieval from Tail | peekLast() | getLast() |
3. Using Methods
3.1 Using ArrayDeque as a Stack
Push an element:
@Test
public void whenPush_addsAtFirst() {
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
assertEquals("second", stack.getFirst());
}
Pop an element:
@Test
public void whenPop_removesLast() {
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
assertEquals("second", stack.pop());
}
The pop method throws NoSuchElementException when a stack is empty.
3.2 Using ArrayDeque as a Queue
Offer an element:
@Test
public void whenOffer_addsAtLast() {
Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
assertEquals("second", queue.getLast());
}
Poll an element:
@Test
public void whenPoll_removesFirst() {
Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
assertEquals("first", queue.poll());
}
The poll method returns a null value if a queue is empty.
4. How’s ArrayDeque Implemented
Under the hood, the ArrayDeque is backed by an array which doubles its size when it gets filled.
Initially, the array is initialized with a size of 16. It’s implemented as a double-ended queue where it maintains two pointers namely a head and a tail.
4.1 ArrayDeque as Stack
As can be seen, when a user adds in an element using the push method, it moves the head pointer by one.
When we pop an element, it sets the element at the head position as null so the element could be garbage collected, and then moves back the head pointer by one.
4.2 ArrayDeque as Queue
When we add in an element using the offer method, it moves the tail pointer by one.
While when user polls an element, it sets the element at the head position to null so the element could be garbage collected, and then moves the head pointer.
4.3 Notes on ArrayDeque
Finally, a few more notes worth understanding and remembering about this particular implementation:
- It’s not thread-safe
- Null elements are not accepted
- Works significantly faster than the synchronized Stack
- Is a faster queue than LinkedList due to the better locality of reference
- Most operations have amortized constant time complexity
- An Iterator returned by an ArrayDeque is fail-fast
- ArrayDeque automatically doubles the size of an array when head and tail pointer meets each other while adding an element
