Skip to content
Tutorials Center
My learning

Topics

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.

Java
Deque<String> stack = new ArrayDeque<>();
Queue<String> queue = new ArrayDeque<>(64);

Try it

Java Stack, queue and sliding window

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.

Java Restrictions and conversions

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

Java
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, pollLast and the peeks are O(1) amortized. contains and remove(Object) are O(n). There is no indexed access.
  • No nulls: null is used internally as the "empty" signal, which is why poll() can return it safely.
  • Faster than Stack and LinkedList in 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 ConcurrentLinkedDeque or LinkedBlockingDeque when several threads share a deque.
  • Declare as Deque or Queue to keep the code independent from the implementation.