Java Deque and ArrayDeque Explained — With Real-World Use Cases
Most Java developers reach for ArrayList or LinkedList without thinking twice. But the moment you need a stack, a queue, or anything where you add or remove from both ends, you're using the wrong tool — and paying for it in performance and readability. Deque (pronounced 'deck') is Java's purpose-built answer to this exact problem, and it's been quietly sitting in the standard library since Java 6.
The classic pain point looks like this: you want a stack, so you use java.util.Stack. It works — but Stack extends Vector, which is synchronized, which means every single push and pop acquires a lock even when you're on a single thread. That's unnecessary overhead, and the Java docs themselves tell you to prefer Deque over Stack. ArrayDeque solves this: no synchronization overhead, no legacy baggage, and faster iteration because the data lives in a contiguous array rather than scattered heap nodes.
By the end of this article you'll understand what Deque actually is (not just what it does), why ArrayDeque is the go-to implementation for most use cases, how to use it as both a stack and a queue in the same codebase, and exactly what traps to avoid. You'll also have a concrete mental model you can pull out in interviews.
What Deque Actually Is — and Why It Replaces Both Stack and Queue
The Deque interface extends Queue and adds mirror-image methods for the front of the collection. Where a plain Queue only lets you offer() at the tail and poll() from the head, a Deque lets you do both operations at both ends. This single property makes it flexible enough to act as a stack (LIFO) or a queue (FIFO) depending on which pair of methods you call.
This isn't just an academic curiosity. Real problems need it. Browser history is a deque — new pages push to the front, the back button pops from the front, and you can cap the history size by dropping from the tail. A sliding-window maximum algorithm in competitive programming uses a deque to efficiently track the largest element in a moving window. An undo/redo system uses it to maintain two stacks in one structure.
The Deque interface gives you three styles of every operation: one that throws an exception on failure (addFirst, removeFirst), one that returns a special value (offerFirst, pollFirst), and one that blocks — but only in the BlockingDeque sub-interface. For ArrayDeque, stick to the offer/poll family so your code stays null-and-exception-safe.
The key mental shift: stop thinking of it as 'a fancy list' and start thinking of it as 'a double-ended conveyor belt with defined entry and exit points at each end.'
import java.util.ArrayDeque; import java.util.Deque; public class DequeAsStackAndQueue { public static void main(String[] args) { // ── Using ArrayDeque as a STACK (LIFO) ────────────────────────── // Think: a stack of pancakes — last one placed is first one eaten. Deque<String> browserHistory = new ArrayDeque<>(); browserHistory.push("google.com"); // pushes to the FRONT (head) browserHistory.push("github.com"); // pushes to the FRONT, google moves back browserHistory.push("thecodeforge.io"); // now this is at the top System.out.println("=== Browser History (Stack) ==="); System.out.println("Current page : " + browserHistory.peek()); // look without removing System.out.println("Going back : " + browserHistory.pop()); // removes from front System.out.println("Now on : " + browserHistory.peek()); // ── Using ArrayDeque as a QUEUE (FIFO) ────────────────────────── // Think: a printer queue — first document sent is first printed. Deque<String> printQueue = new ArrayDeque<>(); printQueue.offerLast("invoice.pdf"); // add to the TAIL printQueue.offerLast("report.docx"); // add to the TAIL printQueue.offerLast("photo.png"); // add to the TAIL System.out.println("\n=== Print Queue (FIFO) ==="); // pollFirst() removes from the HEAD — first in, first out while (!printQueue.isEmpty()) { System.out.println("Printing: " + printQueue.pollFirst()); } // ── Using BOTH ends simultaneously ─────────────────────────────── // A sliding window of the last 3 user actions Deque<String> recentActions = new ArrayDeque<>(); String[] actions = {"login", "view-dashboard", "edit-profile", "upload-photo", "logout"}; int windowSize = 3; System.out.println("\n=== Last " + windowSize + " Actions ==="); for (String action : actions) { recentActions.offerLast(action); // new action enters at the tail if (recentActions.size() > windowSize) { recentActions.pollFirst(); // oldest action drops from the head } } System.out.println("Recent actions: " + recentActions); } }
Current page : thecodeforge.io
Going back : thecodeforge.io
Now on : github.com
=== Print Queue (FIFO) ===
Printing: invoice.pdf
Printing: report.docx
Printing: photo.png
=== Last 3 Actions ===
Recent actions: [edit-profile, upload-photo, logout]
Why ArrayDeque Beats Stack, LinkedList, and Even ArrayList for This Job
ArrayDeque is backed by a circular array — a plain Object[] where head and tail are just integer pointers that wrap around. When you push to the front, the head pointer moves left (mod capacity). When you offer to the back, the tail pointer moves right. No object allocation per element, no pointer chasing, no garbage to collect. This gives O(1) amortized time for addFirst, addLast, removeFirst, and removeLast.
Compare that to LinkedList: every node is a separate heap object with two reference fields. That's 24–32 bytes of overhead per element on a modern JVM, scattered across memory, which destroys CPU cache locality. LinkedList is theoretically O(1) for head/tail operations too, but the constant factor is much higher and GC pressure is real.
Stack is even worse for new code. It inherits from Vector, which wraps every method in synchronized — meaning you pay for thread safety you don't need on a single thread. The Java 11 docs literally say: 'A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.'
ArrayDeque does have one catch: it doesn't allow null elements. This is actually a feature — null is used as a sentinel value internally for certain checks, and if you store nulls, poll() returning null becomes ambiguous (empty queue, or null element?). If you genuinely need to store nulls, LinkedList is the fallback.
import java.util.ArrayDeque; import java.util.Deque; import java.util.LinkedList; import java.util.Stack; public class ArrayDequeInternals { // A simple benchmark to make the performance difference tangible. // Not a rigorous JMH benchmark, but good enough to see the shape. static final int OPERATIONS = 1_000_000; public static void main(String[] args) { // ── ArrayDeque timing ──────────────────────────────────────────── Deque<Integer> arrayDeque = new ArrayDeque<>(OPERATIONS); // pre-size to avoid resizing long start = System.nanoTime(); for (int i = 0; i < OPERATIONS; i++) { arrayDeque.push(i); // addFirst under the hood } for (int i = 0; i < OPERATIONS; i++) { arrayDeque.pop(); // removeFirst under the hood } long arrayDequeMs = (System.nanoTime() - start) / 1_000_000; // ── LinkedList timing ──────────────────────────────────────────── Deque<Integer> linkedList = new LinkedList<>(); start = System.nanoTime(); for (int i = 0; i < OPERATIONS; i++) { linkedList.push(i); } for (int i = 0; i < OPERATIONS; i++) { linkedList.pop(); } long linkedListMs = (System.nanoTime() - start) / 1_000_000; // ── Legacy Stack timing ────────────────────────────────────────── Stack<Integer> legacyStack = new Stack<>(); start = System.nanoTime(); for (int i = 0; i < OPERATIONS; i++) { legacyStack.push(i); } for (int i = 0; i < OPERATIONS; i++) { legacyStack.pop(); } long stackMs = (System.nanoTime() - start) / 1_000_000; System.out.println("=== 1,000,000 push + pop operations ==="); System.out.printf("ArrayDeque : %d ms%n", arrayDequeMs); System.out.printf("LinkedList : %d ms%n", linkedListMs); System.out.printf("Stack : %d ms%n", stackMs); // ── Null safety demonstration ──────────────────────────────────── System.out.println("\n=== Null element behaviour ==="); try { Deque<String> noNulls = new ArrayDeque<>(); noNulls.offerLast(null); // ArrayDeque rejects null } catch (NullPointerException e) { // ArrayDeque throws NPE rather than silently storing null System.out.println("ArrayDeque: null rejected — " + e.getClass().getSimpleName()); } Deque<String> nullsOk = new LinkedList<>(); nullsOk.offerLast(null); // LinkedList accepts null System.out.println("LinkedList : null accepted, poll() returns: " + nullsOk.pollFirst()); // Ambiguous! Is null because the queue had a null element, or because it's empty? System.out.println("LinkedList : poll() on empty returns: " + nullsOk.pollFirst()); // Both print null — you can't tell the difference. } }
ArrayDeque : 18 ms
LinkedList : 74 ms
Stack : 91 ms
=== Null element behaviour ===
ArrayDeque: null rejected — NullPointerException
LinkedList : null accepted, poll() returns: null
LinkedList : poll() on empty returns: null
Real-World Pattern: Undo/Redo with Two Deques
The undo/redo pattern is one of the clearest real-world demonstrations of why Deque exists. Most developers reach for two Stacks — but since ArrayDeque replaces Stack, you end up with two ArrayDeques. The elegance here is in the data flow: every action pushes to the undo deque. An undo pops from the undo deque and pushes to the redo deque. A redo pops from the redo deque and pushes back to the undo deque. Any brand-new action clears the redo deque, because you've forked off the history.
This pattern appears everywhere: text editors, Photoshop, database transaction rollback, Git (roughly), and any wizard-style form with a Back button.
The example below models a simple text editor command history. Notice how the deques' push/pop semantics make the intent obvious at the call site — you're not juggling indices or size checks. The code reads almost like a specification of the algorithm.
import java.util.ArrayDeque; import java.util.Deque; // Simulates a minimal text editor with undo/redo support. public class UndoRedoEditor { private final Deque<String> undoStack = new ArrayDeque<>(); // commands we can undo private final Deque<String> redoStack = new ArrayDeque<>(); // commands we can redo private final StringBuilder document = new StringBuilder(); // Performs a new edit and records it for potential undo public void performEdit(String command, String text) { String snapshot = document.toString(); // save state BEFORE the change applyEdit(command, text); undoStack.push(snapshot); // push old state so undo can restore it redoStack.clear(); // branching — future redo history is now invalid System.out.println("[EDIT] command='" + command + "' text='" + text + "' | doc now: '" + document + "'"); } // Undoes the last edit public void undo() { if (undoStack.isEmpty()) { System.out.println("[UNDO] nothing to undo"); return; } redoStack.push(document.toString()); // save current state so redo can restore it String previousState = undoStack.pop(); // restore the state before last edit document.setLength(0); document.append(previousState); System.out.println("[UNDO] doc now: '" + document + "'"); } // Redoes the last undone edit public void redo() { if (redoStack.isEmpty()) { System.out.println("[REDO] nothing to redo"); return; } undoStack.push(document.toString()); // save current so we can undo the redo String redoState = redoStack.pop(); document.setLength(0); document.append(redoState); System.out.println("[REDO] doc now: '" + document + "'"); } private void applyEdit(String command, String text) { switch (command) { case "append" -> document.append(text); case "delete" -> { int len = Math.min(text.length(), document.length()); document.delete(document.length() - len, document.length()); } default -> throw new IllegalArgumentException("Unknown command: " + command); } } public static void main(String[] args) { UndoRedoEditor editor = new UndoRedoEditor(); editor.performEdit("append", "Hello"); editor.performEdit("append", ", World"); editor.performEdit("append", "!"); System.out.println(); editor.undo(); // removes '!' editor.undo(); // removes ', World' System.out.println(); editor.redo(); // restores ', World' System.out.println(); // Performing a new edit here clears redo history editor.performEdit("append", " from Java"); editor.redo(); // nothing to redo — new branch forked the history } }
[EDIT] command='append' text=', World' | doc now: 'Hello, World'
[EDIT] command='append' text='!' | doc now: 'Hello, World!'
[UNDO] doc now: 'Hello, World'
[UNDO] doc now: 'Hello'
[REDO] doc now: 'Hello, World'
[EDIT] command='append' text=' from Java' | doc now: 'Hello, World from Java'
[REDO] nothing to redo
Every Deque Method You'll Actually Use — and Which to Avoid
ArrayDeque has a lot of methods and the naming is genuinely confusing at first, because the same logical operation has three names depending on the error-handling style you want. Let's demystify this once and for all.
The pattern is: each end (First/Last) has three method styles — throwing, returning-null/false, and the legacy push/pop/peek aliases (which always operate on the head). The throwing variants (addFirst, removeFirst) raise NoSuchElementException on an empty deque. The safe variants (offerFirst, pollFirst, peekFirst) return null or false without throwing. Use the safe variants by default unless an empty deque is a programming error you genuinely want to crash on.
The push(), pop(), and peek() methods are Stack compatibility aliases. push(e) is addFirst(e). pop() is removeFirst(). peek() is peekFirst(). They're fine to use, but mixing them with offerLast() in the same class can confuse readers about which end you're operating on. A clean codebase picks a convention and sticks to it: either always use push/pop (stack style) or always use offerFirst/offerLast/pollFirst/pollLast (explicit style).
import java.util.ArrayDeque; import java.util.Deque; import java.util.NoSuchElementException; public class DequeMethodReference { public static void main(String[] args) { Deque<String> taskQueue = new ArrayDeque<>(); // ── Adding elements ────────────────────────────────────────────── taskQueue.offerFirst("low-priority-task"); // safe add to HEAD taskQueue.offerLast("normal-task"); // safe add to TAIL taskQueue.offerFirst("urgent-task"); // jumps to the front // taskQueue is now: [urgent-task, low-priority-task, normal-task] System.out.println("Queue: " + taskQueue); // ── Peeking (non-destructive) ──────────────────────────────────── System.out.println("Next up (head): " + taskQueue.peekFirst()); // does NOT remove System.out.println("Last in (tail): " + taskQueue.peekLast()); // does NOT remove System.out.println("Still intact : " + taskQueue); // unchanged // ── Removing elements ──────────────────────────────────────────── String nextTask = taskQueue.pollFirst(); // safe remove from HEAD, returns null if empty System.out.println("Processing: " + nextTask); System.out.println("Remaining : " + taskQueue); // ── Throwing vs safe variants ──────────────────────────────────── Deque<String> emptyDeque = new ArrayDeque<>(); // Safe — returns null, no exception String safeResult = emptyDeque.pollFirst(); System.out.println("\npollFirst on empty: " + safeResult); // null // Throwing — raises NoSuchElementException try { emptyDeque.removeFirst(); // throws because the deque is empty } catch (NoSuchElementException e) { System.out.println("removeFirst on empty: " + e.getClass().getSimpleName()); } // ── Stack aliases (push/pop operate on the HEAD) ───────────────── Deque<Integer> callStack = new ArrayDeque<>(); callStack.push(1); // same as addFirst(1) callStack.push(2); // same as addFirst(2) callStack.push(3); // same as addFirst(3) System.out.println("\nCall stack top: " + callStack.peek()); // 3 — same as peekFirst() System.out.println("Popped : " + callStack.pop()); // 3 — same as removeFirst() System.out.println("New top : " + callStack.peek()); // 2 // ── Size checks ────────────────────────────────────────────────── System.out.println("\nSize : " + callStack.size()); System.out.println("Empty? : " + callStack.isEmpty()); System.out.println("Contains 1? : " + callStack.contains(1)); // O(n) linear scan } }
Next up (head): urgent-task
Last in (tail): normal-task
Still intact : [urgent-task, low-priority-task, normal-task]
Processing: urgent-task
Remaining : [low-priority-task, normal-task]
pollFirst on empty: null
removeFirst on empty: NoSuchElementException
Call stack top: 3
Popped : 3
New top : 2
Size : 2
Empty? : false
Contains 1? : true
| Feature / Aspect | ArrayDeque | LinkedList (as Deque) | Stack (legacy) |
|---|---|---|---|
| Underlying structure | Circular resizable array | Doubly-linked nodes | Resizable array (via Vector) |
| Memory per element | ~4-8 bytes (reference only) | ~32-40 bytes (node + 2 refs) | ~4-8 bytes (reference only) |
| addFirst / addLast | O(1) amortized | O(1) true | O(1) amortized (tail only) |
| removeFirst / removeLast | O(1) amortized | O(1) true | O(1) top only, O(n) bottom |
| Random access (get by index) | Not supported | O(n) | O(1) via inherited Vector |
| Thread-safe? | No | No | Yes (synchronized — costly) |
| Allows null elements? | No — throws NPE | Yes | Yes |
| Iteration order | Head to tail (FIFO) | Head to tail (FIFO) | Bottom to top (LIFO) |
| Recommended for stack? | Yes — preferred | Acceptable | No — legacy, avoid |
| Recommended for queue? | Yes — preferred | Acceptable | No — wrong structure |
| Java version introduced | Java 6 | Java 1.2 | Java 1.0 |
🎯 Key Takeaways
- ArrayDeque is the right default for both stacks and queues in single-threaded Java — it outperforms Stack (no synchronization) and LinkedList (better cache locality) in almost every benchmark.
- Deque's method table is systematic, not arbitrary: each end (First/Last) has a throwing variant and a safe variant. Learn the pattern once and you know all 8 methods.
- ArrayDeque does not allow null elements by design — null is ambiguous as a return value from pollFirst() because it could mean 'empty' or 'stored null'. This is a feature, not a limitation.
- The undo/redo pattern is the canonical real-world demonstration of Deque: two ArrayDeques acting as stacks, with the branching rule (new action clears redo) being the detail that proves you've actually used it.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Using Stack instead of ArrayDeque for LIFO operations — Symptom: Unnecessarily slower code and mixing synchronized methods with single-threaded logic; the Java docs explicitly deprecate this usage pattern — Fix: Replace new Stack<>() with new ArrayDeque<>() and use push()/pop()/peek(); no other code changes needed.
- ✕Mistake 2: Storing null elements in ArrayDeque — Symptom: NullPointerException thrown at offerLast(null) or addFirst(null), which is confusing if you're used to ArrayList accepting nulls — Fix: If your data can genuinely be null, use Optional
as your element type (e.g., Deque - ✕Mistake 3: Mixing push/pop (head-only) with offerLast/pollLast (tail) in the same class — Symptom: Logic bugs where elements are removed from the wrong end; e.g., push() adds to head but pollLast() removes from tail, so what looks like a stack behaves like a queue — Fix: Pick one convention per Deque instance. Document it with a comment at the declaration site, e.g., // used as STACK — always push/pop from head only.
Interview Questions on This Topic
- QWhy does the Java documentation recommend using ArrayDeque over Stack for LIFO operations, and what is the specific cost of using Stack in a single-threaded application?
- QExplain the difference between the throwing methods (addFirst, removeFirst) and the safe methods (offerFirst, pollFirst) in the Deque interface. When would you choose one over the other?
- QArrayDeque is backed by a circular array. What does 'circular' mean in this context, and why does it allow O(1) addFirst without shifting every element — something a regular array can't do?
Frequently Asked Questions
Is ArrayDeque thread-safe in Java?
No, ArrayDeque is not thread-safe. If multiple threads access it concurrently, you must synchronize externally (e.g., Collections.synchronizedDeque()) or use a thread-safe alternative like LinkedBlockingDeque from java.util.concurrent. For single-threaded code, ArrayDeque is the preferred choice precisely because it avoids synchronization overhead.
What is the difference between Deque and Queue in Java?
Queue is a one-ended interface — you add at the tail and remove from the head (FIFO only). Deque extends Queue and adds mirror methods for the head, so you can add and remove from either end. Every Deque is a Queue, but not every Queue is a Deque. Use Queue when FIFO semantics are all you need; use Deque when you need stack behaviour, double-ended access, or both.
Why does ArrayDeque say it's faster than LinkedList if both are O(1) for head/tail operations?
Big-O notation hides constant factors. LinkedList's O(1) operations still allocate a new Node object per element, which means GC pressure and scattered heap memory that destroys CPU cache performance. ArrayDeque stores references in a contiguous array, so traversal and sequential access are cache-friendly. In practice, ArrayDeque is 3–5x faster for push/pop workloads because of this memory layout difference.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.