Java Deque and ArrayDeque — Double-Ended Queues

Deque (pronounced “deck”) stands for double-ended queue — a linear structure that supports adding and removing elements at both ends in O(1) time. ArrayDeque is its fastest general-purpose implementation.

---

The Deque Interface

        ← offerFirst()              offerLast() →
        ← pollFirst()               pollLast() →
        ← peekFirst()               peekLast() →

     ┌───┬───┬───┬───┬───┐
     │ A │ B │ C │ D │ E │
     └───┴───┴───┴───┴───┘
     head                tail

Methods — Two Families

Operation	Throws Exception	Returns null/false
Insert first	addFirst(e)	offerFirst(e)
Insert last	addLast(e)	offerLast(e)
Remove first	removeFirst()	pollFirst()
Remove last	removeLast()	pollLast()
Examine first	getFirst()	peekFirst()
Examine last	getLast()	peekLast()

Stack Methods (Aliases)

Stack	Deque Equivalent
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

Queue Methods (Aliases)

Queue	Deque Equivalent
offer(e)	offerLast(e)
poll()	pollFirst()
peek()	peekFirst()

---

ArrayDeque Internals

ArrayDeque uses a circular (ring) buffer — a resizable array where head and tail wrap around:

Initial state (capacity 8):
  Index:  0   1   2   3   4   5   6   7
        ┌───┬───┬───┬───┬───┬───┬───┬───┐
        │   │   │ A │ B │ C │ D │   │   │
        └───┴───┴───┴───┴───┴───┴───┴───┘
                  ↑               ↑
                 head            tail

After offerFirst("Z"):
  Index:  0   1   2   3   4   5   6   7
        ┌───┬───┬───┬───┬───┬───┬───┬───┐
        │   │ Z │ A │ B │ C │ D │   │   │
        └───┴───┴───┴───┴───┴───┴───┴───┘
              ↑                   ↑
             head                tail

After offerLast("E"):
  Index:  0   1   2   3   4   5   6   7
        ┌───┬───┬───┬───┬───┬───┬───┬───┐
        │   │ Z │ A │ B │ C │ D │ E │   │
        └───┴───┴───┴───┴───┴───┴───┴───┘
              ↑                       ↑
             head                    tail

Wrap-around — head moves to index 7:
  Index:  0   1   2   3   4   5   6   7
        ┌───┬───┬───┬───┬───┬───┬───┬───┐
        │ D │ E │   │   │   │ A │ B │ C │
        └───┴───┴───┴───┴───┴───┴───┴───┘
                              ↑       ↑
                             head    (wraps to 0)

When the array is full, it doubles in size and copies elements into a contiguous block.

---

Big-O Complexity

Operation	Time
offerFirst(e) / offerLast(e)	O(1) amortized
pollFirst() / pollLast()	O(1)
peekFirst() / peekLast()	O(1)
contains(Object)	O(n)
remove(Object)	O(n)
size()	O(1)

---

ArrayDeque vs LinkedList

Factor	ArrayDeque	LinkedList
Backing structure	Circular array	Doubly-linked nodes
Memory per element	~8 bytes	~40 bytes
Cache locality	✅ Excellent	❌ Poor
Null elements	❌ Not allowed	✅ Allowed
Implements List	❌	✅
Throughput	Faster	Slower

Always prefer ArrayDeque for stack/queue usage — unless you need null elements or the List interface.

---

Using ArrayDeque as a Stack

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

// Navigate to pages
history.push("home");
history.push("products");
history.push("product/42");

// Go back
String current = history.pop();     // "product/42"
String previous = history.peek();   // "products"

---

Using ArrayDeque as a Queue

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

printQueue.offer("Document1.pdf");
printQueue.offer("Report.docx");
printQueue.offer("Photo.jpg");

while (!printQueue.isEmpty()) {
    String job = printQueue.poll();
    System.out.println("Printing: " + job);
}

---

Sliding Window Pattern

// Find max in every window of size k
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();  // stores indices
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside the window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove smaller elements from back
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

---

Important Restrictions

1. No null elements — ArrayDeque uses null internally as a sentinel.
2. Not thread-safe — use ConcurrentLinkedDeque for concurrency.
3. No random access — ArrayDeque does not implement List, so no get(index).
4. No capacity limit — grows as needed (unlike ArrayBlockingQueue).

---

Key Takeaways

1. Deque = double-ended queue; supports O(1) operations at both ends.
2. ArrayDeque is the best implementation — circular array, cache-friendly, low memory.
3. Use push()/pop() for stack, offer()/poll() for queue.
4. Always prefer ArrayDeque over LinkedList for Deque operations.
5. Does not allow null elements and does not implement List.

---

What’s Next?

Next: PriorityQueue — min-heap ordering, custom comparators, and top-K problems.