Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java ArrayDeque Queue: Use It for FIFO Queues

Learn how to use Java ArrayDeque as a FIFO queue, including performance advantages, API behavior, and when it is a better choice than LinkedList.

~5 min readJava
#ArrayDeque#Queue#Deque#Java Collections
Diagram of ArrayDeque serving as a FIFO queue with elements entering at one end and leaving at the other.

If you need a FIFO queue in Java and typically reach for LinkedList, you may be missing a more efficient option. The ArrayDeque class, introduced in Java 6, implements a resizable-array-based double-ended queue and can serve as a Queue implementation. In many queue-like workloads, it provides better performance and lower memory overhead than LinkedList.

This article focuses on when to use ArrayDeque as your queue and how to do it correctly. We'll examine the API, behavior, performance characteristics, and common pitfalls.

Queue Operations with ArrayDeque

ArrayDeque implements the Deque interface, which extends Queue. This means you can use it wherever a Queue is expected. The two primary operations are offer() for adding elements and poll() for retrieving and removing the head of the queue.

Here is a minimal example that creates a queue backed by ArrayDeque and processes a few tasks in FIFO order:

java
import java.util.ArrayDeque; import java.util.Queue; Queue<String> taskQueue = new ArrayDeque<>(); taskQueue.offer("compile"); taskQueue.offer("test"); taskQueue.offer("package"); String nextTask = taskQueue.poll(); // returns "compile" and removes it

In this example, offer() adds elements to the tail, and poll() retrieves and removes the head. If the queue is empty, poll() returns null, which is critical to handle in production code.

Unlike LinkedList, ArrayDeque does not allow null elements. Attempting to add a null will throw a NullPointerException. This constraint enables a more efficient internal representation. If you need to store null values, use a different collection, such as LinkedList.

Why ArrayDeque Is Often a Better Queue Choice

Many developers reach for LinkedList when they need a queue because it implements List and Deque. However, ArrayDeque has several advantages:

  • Better memory locality: The elements are stored in a contiguous array, which improves cache performance during iteration.
  • No node objects: LinkedList creates a separate node object for each element, adding overhead. ArrayDeque stores elements directly in its internal array.
  • Faster traversal: Accessing elements in an array is generally faster than following pointers between nodes.
  • No random access overhead: LinkedList offers O(n) access by index, but a queue should not need indexed access anyway.

For a single-threaded FIFO queue, ArrayDeque is almost always the better choice. The Oracle documentation explicitly notes that ArrayDeque is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue.

Resizing Behavior and Capacity

ArrayDeque uses an internal circular array. When the array becomes full, it doubles its capacity. This resizing operation is O(n), but it happens infrequently enough that the amortized cost remains O(1) per operation.

You can pre-size the ArrayDeque if you know the expected number of elements. This avoids unnecessary resizing and can save memory. Use the constructor that accepts an initial capacity:

java
Queue<String> queue = new ArrayDeque<>(1000);

The initial capacity must be a positive integer. The implementation may round it up to a power of two for internal alignment.

Choosing a very large capacity to avoid resizing can waste memory if the queue never fills. A good practice is to pick a capacity that closely matches the expected workload.

Performance: Time and Memory Considerations

Both ArrayDeque and LinkedList offer amortized O(1) time for offer() and poll(), but their constants and memory use differ.

  • ArrayDeque: Uses a dynamic array. Accessing an element at a specific index is O(1). Adding or removing at the ends is amortized O(1). There is no per-element object overhead beyond the array slot.
  • LinkedList: Each element is a separate object containing the value and references to the previous and next elements. Adding or removing at the ends is O(1), but each node consumes more memory.

Memory usage is a concrete difference. For example, a LinkedList with 10,000 Integer objects allocates 10,000 node objects plus the Integer objects. An ArrayDeque allocates the backing array plus the Integer objects. Some array slots may be wasted due to resizing, but that overhead is usually much less than the per-node overhead.

Actual performance depends on the JVM and workload; the important point is that the two implementations have different structural costs.

Concurrency: ArrayDeque Is Not Thread-Safe

ArrayDeque is not synchronized. If you need a thread-safe queue, use one of these instead:

  • ConcurrentLinkedQueue: A lock-free, thread-safe queue designed for high-concurrency scenarios.
  • LinkedBlockingQueue: A blocking queue commonly used with the producer-consumer pattern.
  • ArrayBlockingQueue: A bounded, blocking queue backed by an array.

Do not use ArrayDeque from multiple threads without external synchronization. Wrapping it with Collections.synchronizedQueue() synchronizes individual method calls, but compound operations such as check-then-act still require explicit locking, and iteration also needs synchronization.

If you do use ArrayDeque across threads, synchronize on the queue object itself. For example:

java
Queue<String> queue = Collections.synchronizedQueue(new ArrayDeque<>()); // Still need to synchronize for compound actions synchronized (queue) { if (queue.peek() != null) { queue.poll(); } }

For most concurrent cases, a dedicated concurrent queue is simpler and safer.

Iteration and Bulk Operations

ArrayDeque supports iteration in both directions. When using it as a queue, you can iterate over pending tasks without removing them:

java
for (String task : queue) { System.out.println("Processing: " + task); }

Do not call structural modification methods such as remove() or poll() directly while iterating with an enhanced for-loop. If you need to remove selected elements during iteration, use Iterator.remove():

java
import java.util.Iterator; Iterator<String> iterator = queue.iterator(); while (iterator.hasNext()) { String task = iterator.next(); if (task.startsWith("skip:")) { iterator.remove(); } }

Because Queue extends Collection, the enhanced for-loop is available. ArrayDeque's iterator implements Iterator.remove(), so removing through the iterator is supported.

Common Mistakes and Edge Cases

A common mistake is using add() instead of offer(). Both add elements, but add() throws an exception when a bounded queue is full. ArrayDeque is unbounded, so add() will not throw an IllegalStateException for capacity reasons. Still, offer() is a good habit for queue code because it returns a boolean and communicates the possibility of insertion failure.

Another edge case is calling peek() and then poll() in concurrent code. peek() returns the head without removing it, while poll() removes it. If other threads can modify the queue, the value you saw with peek() may no longer be at the head by the time poll() runs. In single-threaded code, remember that both methods return null for an empty queue, so check the result of poll() if you depend on it.

Also remember that ArrayDeque does not allow null. If you need to represent "no value" in a queue, use a sentinel object or a different collection.

When to Choose ArrayDeque vs. LinkedList or ConcurrentLinkedQueue

Use ArrayDeque when:

  • You need a single-threaded FIFO queue.
  • You need fast, predictable queue operations.
  • You don't need to store null elements.
  • You want to minimize memory overhead.

Use LinkedList when:

  • You need to store null elements.
  • You need a List and a Deque simultaneously.
  • You need to insert or remove elements in the middle (though that is rarely a queue use case).

Use ConcurrentLinkedQueue when:

  • You need thread-safe queue operations without a hard bound.
  • You are using a producer-consumer pattern and don't need blocking.

For blocking queues, use LinkedBlockingQueue or ArrayBlockingQueue. The choice depends on whether you need bounded capacity and whether you need fairness guarantees.

The bottom line is that for a typical FIFO queue in a single-threaded Java application, ArrayDeque is the best starting point. It combines low overhead, high throughput, and a clean API.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.