Java Reference ยท Collections
The ArrayDeque class
Reference for java.util.ArrayDeque: a resizable circular-array Deque that is the default choice for stacks and queues, with examples and pitfalls.
ArrayDeque<E> implements Deque<E> with a resizable circular array. Adding and removing at either end takes amortized constant time, and there are no per-element node objects, so it is faster and lighter than LinkedList for almost every stack or queue workload.
It is the usual answer to "which class should I use for a stack or a queue?". It does not accept null elements and it is not thread-safe.
Deque<String> stack = new ArrayDeque<>(); Queue<String> queue = new ArrayDeque<>(64);
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, java.io.Serializable
| Constructor | Description |
|---|---|
ArrayDeque() |
Empty deque with a small default capacity. |
ArrayDeque(int numElements) |
Initial capacity hint; the deque still grows as needed. |
ArrayDeque(Collection<? extends E> c) |
Elements in the collection's iteration order. |
All Deque and Queue methods are available. In addition, clone() makes a shallow copy.
Throws: NullPointerException for any null element; NoSuchElementException from throwing remove and examine methods on an empty deque.
Usage notes
- Complexity:
addFirst,addLast,pollFirst,pollLastand the peeks areO(1)amortized.containsandremove(Object)areO(n). There is no indexed access. - No nulls:
nullis used internally as the "empty" signal, which is whypoll()can return it safely. - Faster than
StackandLinkedListin practice, because the data sits in one contiguous array. - Capacity: the constructor argument is only a hint. Pre-sizing avoids a few array copies in hot code.
- Iterator is fail-fast on a best-effort basis: structural changes during iteration usually cause
ConcurrentModificationException. - Not thread-safe. Use
ConcurrentLinkedDequeorLinkedBlockingDequewhen several threads share a deque. - Declare as
DequeorQueueto keep the code independent from the implementation.
Related
- Deque, Queue, LinkedList, PriorityQueue
- Lessons: Queues and deques, Choosing a collection