Deque

Deque Fundamentals

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

Core Operations

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