What is Deque?

🟢 Junior Level

Deque (Double-Ended Queue) — queue where you can add and remove elements from both ends.

Analogy: Deck of cards — you can take card from top or bottom, put on top or bottom.

Simple analogy: Two-sided queue at amusement park — can enter and exit from both ends.

Deque = Stack + Queue:

Deque<String> deque = new ArrayDeque<>();

// As stack (LIFO):
deque.push("A");     // Push on top
deque.pop();         // Pop from top

// As queue (FIFO):
deque.offer("A");    // To end
deque.poll();        // From front

// From both ends:
deque.addFirst("A"); // To front
deque.addLast("B");  // To end
deque.removeFirst(); // Remove front
deque.removeLast();  // Remove end

🟡 Middle Level

ArrayDeque: best implementation

// Circular Buffer
Deque<String> deque = new ArrayDeque<>();

// Operations: O(1) amortized
deque.addFirst("A");   // O(1)
deque.addLast("B");    // O(1)
deque.removeFirst();   // O(1)
deque.removeLast();    // O(1)
deque.peekFirst();     // O(1)
deque.peekLast();      // O(1)

Why ArrayDeque better than LinkedList

	ArrayDeque	LinkedList
Memory	Array (little)	Node objects (much)
Cache locality	Excellent	Terrible
Allocations	On resize	On every insertion
GC pressure	Low	High
Speed	Per JMH benchmarks: ArrayDeque 3-10x faster than LinkedList on iteration, 2-5x faster on insertion/removal.

Deque as Stack

// ❌ Don't use Stack
Stack<String> stack = new Stack<>();

// ✅ Use Deque
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();
stack.peek();

Java 21: SequencedCollection

// Java 21 not available everywhere. For Java 11/17 use deque.peekFirst() instead of getFirst() and deque.peekLast() instead of getLast().

// Deque now SequencedCollection
deque.getFirst();    // New method!
deque.getLast();     // New method!
deque.reversed();    // Reverse order (view)

// Guaranteed iteration order
for (String s : deque) { ... }  // From first to last
for (String s : deque.reversed()) { ... }  // Opposite

🔴 Senior Level

Circular Buffer

Array: [A][B][C][ ][ ][ ][ ][ ]
        ↑head         ↑tail

addLast(D):
[A][B][C][D][ ][ ][ ][ ]
        ↑head      ↑tail

removeFirst():
[ ][B][C][D][ ][ ][ ][ ]
   ↑head      ↑tail

tail reached end → wraps around:
[ ][B][C][D][E][F][ ][ ]
   ↑head               ↑tail

Index: (tail + 1) & (length - 1)  // Bitwise AND!

Bitmasks instead of division

// Normal cyclic index:
index = (index + 1) % capacity;  // Division — slow!

// ArrayDeque (capacity = power of 2):
index = (index + 1) & (elements.length - 1);  // AND — fast!

// Example: capacity = 8 (1000 in binary)
// (7 + 1) & 7 = 8 & 7 = 0  ← Wrapped!

// Why power of 2?
// 8 = 1000, 7 = 0111
// x & 7 = x % 8  (for x < 16)
// → One CPU instruction instead of division!

Trade-off: power of 2 means array can only be 50-75% full before resize (to distinguish “full” from “empty”). This wastes some memory, but division savings worth it.

Why ArrayDeque forbids null?

deque.offer(null);  // → NullPointerException!

// Why?
// poll() and peek() return null for empty deque
// If null is valid element → can't distinguish!

// This is architectural decision, not a bug!

Concurrency

// ArrayDeque NOT thread-safe!

// Lock-free Deque:
Deque<String> deque = new ConcurrentLinkedDeque<>();

// Blocking Deque (Work Stealing):
BlockingDeque<String> deque = new LinkedBlockingDeque<>();
// → Threads can "steal" tasks from tail
// → ForkJoinPool uses this!

// **Work Stealing** — load balancing algorithm: when thread finishes its task queue, it "steals" tasks from tail of another thread's queue. This prevents one thread being overloaded while another idle. Used in ForkJoinPool.

Production Experience

Real case: LinkedList → ArrayDeque

Message queue: LinkedList
GC every 2 seconds (Node allocations)
Solution: ArrayDeque
Result: GC once per minute, +50% throughput

Best Practices

ArrayDeque — for stacks and queues
Forbids null — architectural limitation
Power of 2 → bitmasks instead of division
Java 21 → getFirst(), getLast(), reversed()
ConcurrentLinkedDeque — lock-free
LinkedBlockingDeque — Work Stealing
DO NOT use Stack or LinkedList

Summary for Senior

Deque = double-ended queue (LIFO + FIFO)
ArrayDeque = circular buffer, capacity = 2^n
Bitmasks → (index + 1) & (length - 1)
null forbidden → unambiguous poll/peek
Cache locality » LinkedList
SequencedCollection (Java 21) → getFirst/reversed
Work Stealing → LinkedBlockingDeque
NEVER use Stack

🎯 Interview Cheat Sheet

Must know:

Deque (Double-Ended Queue) = double-ended queue, supports LIFO + FIFO
ArrayDeque — best implementation: circular buffer, O(1) amortized for all operations on both ends
ArrayDeque better than LinkedList: 3-10x faster on iteration, 2-5x on insertion/removal, less GC pressure
Circular buffer: capacity = power of 2 → bitmasks instead of division ((index + 1) & (length - 1))
ArrayDeque forbids null — architectural decision (poll/peek return null for empty deque)
Java 21: SequencedCollection → getFirst(), getLast(), reversed() for Deque
Concurrency: ConcurrentLinkedDeque (lock-free), LinkedBlockingDeque (Work Stealing, ForkJoinPool)
ArrayDeque replaces Stack: push/pop/peek — same methods, without synchronized overhead and LSP violation

Common follow-up questions:

Why ArrayDeque uses capacity = power of 2? — For bitmasks: (index + 1) & (length - 1) instead of slow division %
Why ArrayDeque forbids null? — poll()/peek() return null for empty deque, null element would create ambiguity
What is Work Stealing? — Threads “steal” tasks from tail of other queues, load balancing in ForkJoinPool
How Deque differs from Queue? — Deque supports operations on both ends, Queue — only one end (FIFO)

Red flags (NOT to say):

❌ “LinkedList — good Deque implementation” — ArrayDeque always better (cache locality, less memory)
❌ “ArrayDeque can be used as Map key” — Deque has no hashCode/equals contract for keys
❌ “Deque can contain null” — ArrayDeque forbids null, this is architectural decision
❌ “Use Stack as stack” — ArrayDeque replaces Stack without synchronized overhead and LSP violation

Related topics:

[[What is Queue and what implementations exist]]
[[What is Stack]]
[[What is the difference between ArrayList and LinkedList]]
[[What are the main Collection Framework interfaces]]
[[What is Vector and how does it differ from ArrayList]]