Queue, Deque, and ArrayDeque

Master Java's queue abstractions for FIFO processing, double-ended operations, and stack replacement. Learn why ArrayDeque outperforms both LinkedList and Stack, and when to use each queue variant.

📋 At a Glance

🎯 What You'll Learn

After completing this article, you will be able to:

1. Understand Queue and Deque interfaces and their operation pairs
2. Master ArrayDeque's circular buffer implementation
3. Replace deprecated Stack with ArrayDeque
4. Choose between ArrayDeque and LinkedList for queue operations
5. Implement BFS, undo/redo, and other classic patterns

---

Production Story: The Stack Overflow That Wasn't

The Incident

JAVA(18 lines)
Code
Loading syntax highlighter...

The Problem with Stack

JAVA(14 lines)
Code
Loading syntax highlighter...

The ArrayDeque Solution

JAVA(18 lines)
Code
Loading syntax highlighter...

Performance Comparison

JAVA(15 lines)
Code
Loading syntax highlighter...

Lessons Learned

1. Never use Stack class - it's a legacy class from Java 1.0
2. ArrayDeque is the modern replacement for both Stack and Queue
3. Synchronization has cost - don't pay for it when you don't need it
4. Check for legacy classes - Vector, Stack, Hashtable are outdated

---

Mental Model: The Double-Ended Line

TEXT(42 lines)
Code
Loading syntax highlighter...
Show all 42 lines

---

Deep Dive: Queue Interface

Queue Method Pairs

JAVA(11 lines)
Code
Loading syntax highlighter...

When to Use Which

JAVA(20 lines)
Code
Loading syntax highlighter...

---

Deep Dive: Deque Interface

Double-Ended Operations

JAVA(28 lines)
Code
Loading syntax highlighter...

Deque as Stack vs Queue

JAVA(13 lines)
Code
Loading syntax highlighter...

---

Deep Dive: ArrayDeque Internals

Circular Buffer Implementation

JAVA(20 lines)
Code
Loading syntax highlighter...

Visual: Circular Buffer

TEXT(33 lines)
Code
Loading syntax highlighter...

Resize Strategy

JAVA(17 lines)
Code
Loading syntax highlighter...

Why No Nulls?

JAVA(6 lines)
Code
Loading syntax highlighter...

---

Deep Dive: ArrayDeque vs LinkedList

Performance Comparison

*Amortized O(1) for ArrayDeque (occasional resize)

When to Use Which

JAVA(15 lines)
Code
Loading syntax highlighter...

BFS Example: ArrayDeque vs LinkedList

JAVA(24 lines)
Code
Loading syntax highlighter...

---

Deep Dive: Common Patterns

Pattern 1: Sliding Window

JAVA(22 lines)
Code
Loading syntax highlighter...

Pattern 2: Undo/Redo Stack

JAVA(27 lines)
Code
Loading syntax highlighter...

Pattern 3: Monotonic Deque (Sliding Window Maximum)

JAVA(24 lines)
Code
Loading syntax highlighter...

Pattern 4: Level-Order Tree Traversal

JAVA(22 lines)
Code
Loading syntax highlighter...

---

⚠️ Common Mistakes

Mistake 1: Using Stack Instead of ArrayDeque

JAVA(9 lines)
Code
Loading syntax highlighter...

Mistake 2: Adding Null to ArrayDeque

JAVA(11 lines)
Code
Loading syntax highlighter...

Mistake 3: Confusing add/offer Behavior

JAVA(12 lines)
Code
Loading syntax highlighter...

Mistake 4: Wrong Direction for Stack Operations

JAVA(12 lines)
Code
Loading syntax highlighter...

Mistake 5: Modifying During Iteration

JAVA(19 lines)
Code
Loading syntax highlighter...

---

🐛 Debug This

Challenge 1: The Disappearing Elements

JAVA(9 lines)
Code
Loading syntax highlighter...

Output:

TEXT(2 lines)
Code
Loading syntax highlighter...

• offer adds to tail: [1, 2, 3]
• push adds to head: [0, 1, 2, 3]
• poll (= pollFirst) removes from head: returns 0, deque is [1, 2, 3]
• pollLast removes from tail: returns 3, deque is [1, 2]

Challenge 2: The Iterator Direction

JAVA(15 lines)
Code
Loading syntax highlighter...

Output:

TEXT(2 lines)
Code
Loading syntax highlighter...

• addLast("A"): [A]
• addFirst("B"): [B, A]
• addLast("C"): [B, A, C]
• iterator(): head to tail → B A C
• descendingIterator(): tail to head → C A B

Challenge 3: The Queue vs Stack

JAVA(14 lines)
Code
Loading syntax highlighter...

• offer(1): [1]
• offer(2): [1, 2]
• push(3): [3, 1, 2]
• push(4): [4, 3, 1, 2]
• poll removes from head: 4, 3, 1, 2

---

💻 Exercises

Exercise 1: Browser History

Implement browser back/forward using two stacks:

JAVA(6 lines)
Code
Loading syntax highlighter...

JAVA(33 lines)
Code
Loading syntax highlighter...

Exercise 2: Valid Parentheses

Check if brackets are balanced:

JAVA(6 lines)
Code
Loading syntax highlighter...

JAVA(15 lines)
Code
Loading syntax highlighter...

Exercise 3: Recent Counter

Count requests in last 3000ms:

JAVA(8 lines)
Code
Loading syntax highlighter...

JAVA(11 lines)
Code
Loading syntax highlighter...

Exercise 4: Implement Queue Using Stacks

Implement FIFO queue using only stack operations:

JAVA(6 lines)
Code
Loading syntax highlighter...

JAVA(31 lines)
Code
Loading syntax highlighter...

Exercise 5: Circular Buffer

Implement a fixed-size circular buffer:

JAVA(7 lines)
Code
Loading syntax highlighter...

JAVA(40 lines)
Code
Loading syntax highlighter...
Show all 40 lines

---

🎤 Senior-Level Interview Questions

Question 1: Stack vs ArrayDeque

1. No synchronization overhead: Stack extends Vector, all methods synchronized
2. Better performance: ArrayDeque is ~3-5x faster for push/pop
3. Consistent API: Stack extends Vector, mixing stack and list semantics
4. Modern design: ArrayDeque designed for Deque interface

JAVA(8 lines)
Code
Loading syntax highlighter...

Question 2: ArrayDeque Null Restriction

1. Ambiguity with poll(): poll() returns null for empty queue - can't distinguish stored null
2. Efficient empty slot detection: Uses null to identify unused array slots
3. Design decision: Cleaner API, prevents NPE bugs

JAVA(4 lines)
Code
Loading syntax highlighter...

Question 3: Circular Buffer Benefits

Simple array approach:

JAVA(2 lines)
Code
Loading syntax highlighter...

Circular buffer approach:

JAVA(5 lines)
Code
Loading syntax highlighter...

Benefits:

• O(1) add/remove at both ends
• No shifting required
• Minimal memory overhead
• Excellent cache locality

Question 4: Queue vs Deque Interface

JAVA(14 lines)
Code
Loading syntax highlighter...

Question 5: BFS Queue Choice

1. Cache locality: ArrayDeque stores elements contiguously
2. Memory efficiency: ~8 bytes/element vs ~40 bytes for LinkedList nodes
3. No allocation per element: LinkedList creates node object for each add
4. Faster operations: No pointer traversal

JAVA(4 lines)
Code
Loading syntax highlighter...

Question 6: offer() vs add()

JAVA(14 lines)
Code
Loading syntax highlighter...

---

📝 Summary & Key Takeaways

Queue Interface

• Two operation styles: throwing (add/remove/element) vs special-value (offer/poll/peek)
• Use offer/poll for normal empty/full handling
• Use add/remove when empty/full is a bug

Deque Interface

• Double-ended: addFirst/addLast, pollFirst/pollLast
• Stack: push/pop/peek (all operate on head)
• Queue: offer/poll (tail to head)

ArrayDeque

• Circular buffer - O(1) operations at both ends
• No null elements allowed
• Better than Stack and usually better than LinkedList
• Use for stack, queue, or deque operations

Best Practices

• Never use Stack class - use ArrayDeque
• Prefer ArrayDeque over LinkedList for queues
• Use most restrictive interface type (Queue vs Deque)
• Consider bounded queues for backpressure

---

🏁 Conclusion

ArrayDeque is the Swiss Army knife of Java's queue implementations. Understanding its circular buffer design explains why it outperforms alternatives and why it prohibits nulls. Whether you need a stack, queue, or double-ended queue, ArrayDeque should be your default choice.

Key takeaways:

1. Never use Stack - ArrayDeque is faster and cleaner
2. ArrayDeque's circular buffer enables O(1) operations at both ends
3. No nulls allowed - uses null for empty slot detection
4. Prefer ArrayDeque over LinkedList for pure queue/stack usage
5. Interface choice matters - Queue restricts API, Deque exposes all operations

In the next article, we'll explore PriorityQueue and heap-based data structures - essential for scheduling, top-K problems, and priority-based processing.

---

📅 Review Schedule

To solidify your understanding, review this material:

• Tomorrow: Implement Exercise 4 (Queue using Stacks) from memory
• In 3 days: Explain ArrayDeque circular buffer to a colleague
• In 1 week: Review Stack class deprecation reasons
• In 2 weeks: Practice sliding window problems using Deque

---