Deque

Deque Fundamentals

A deque (double-ended queue) allows insertion and removal from both ends.

Core Operations

Operation	Description	Time
addFirst	Add to front	O(1)
addLast	Add to rear	O(1)
removeFirst	Remove from front	O(1)
removeLast	Remove from rear	O(1)
peekFirst	View front	O(1)
peekLast	View rear	O(1)

Deque as Stack or Queue

// Deque as Stack
deque.push(1);      // or addFirst
deque.pop();        // or removeFirst
deque.peek();       // peekFirst

// Deque as Queue
deque.offer(1);     // or addLast
deque.poll();       // or removeFirst
deque.peek();       // peekFirst

ArrayDeque Implementation

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

deque.addFirst(1);   // [1]
deque.addLast(2);    // [1, 2]
deque.addFirst(0);   // [0, 1, 2]

int front = deque.removeFirst();  // 0
int back = deque.removeLast();    // 2

When to Use Deque

1. Sliding window maximum
2. Implementing both stack and queue
3. Palindrome checking
4. BFS with bidirectional traversal
5. Rolling hash computations

Deque Applications

1. Sliding Window Maximum (LeetCode 239)

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        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;
}
// Time: O(n), Space: O(k)

2. Palindrome Check

public boolean isPalindrome(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            deque.addLast(Character.toLowerCase(c));
        }
    }
    while (deque.size() > 1) {
        if (deque.pollFirst() != deque.pollLast()) {
            return false;
        }
    }
    return true;
}

3. Moving Average (LeetCode 346)

class MovingAverage {
    Deque<Integer> deque;
    int size;
    double sum;
    
    public MovingAverage(int size) {
        this.deque = new ArrayDeque<>();
        this.size = size;
        this.sum = 0;
    }
    
    public double next(int val) {
        deque.offerLast(val);
        sum += val;
        if (deque.size() > size) {
            sum -= deque.pollFirst();
        }
        return sum / deque.size();
    }
}

Deque vs Stack vs Queue

Feature	Stack	Queue	Deque
Add	Push (top)	Offer (rear)	Both ends
Remove	Pop (top)	Poll (front)	Both ends
Use	DFS, undo	BFS	Sliding window