Deque operations

A deque (pronounced “deck”) supports insertion and removal at both ends. At the front, addFirst / offerFirst insert, removeFirst / pollFirst remove and getFirst / peekFirst examine. As with Queue, the first name in each pair throws an exception on failure and the second returns a special value.

Deque.push(x) is simply addFirst(x) and pop() is removeFirst(), which is how an ArrayDeque works as a stack.

The rear mirrors the front: addLast / offerLast, removeLast / pollLast, getLast / peekLast. The plain Queue methods add, offer and peek are the same as the *Last variants for insertion and the *First variants for removal, so a deque used as a queue enqueues at the last end and dequeues at the first end.

1static void demo() {
2    Deque<Integer> d = new ArrayDeque<>();
3    d.addLast(1); d.addLast(2);          // used as a queue: 1, 2
4    d.addFirst(9);                       // 9, 1, 2
5    int a = d.pollFirst();               // 9 leaves from the front
6    int b = d.pollLast();                // 2 leaves from the rear
7    System.out.println(a + " " + b + " " + d);
8}

A deque is the most general of the three structures. Using only addLast and pollFirst it is a queue; using only addFirst and pollFirst it is a stack; using all four it is something neither can be. Every end operation is O(1) in a circular-array or linked implementation.

In the animation each operation is one token: F5 is addFirst(5), L5 is addLast(5), f is pollFirst() and l is pollLast(). Try “Used as a stack” and “Used as a queue”: the same structure, two different orders of removal.

1Deque<Integer> d = new ArrayDeque<>();
2d.addFirst(x);                 // F x: x becomes the new front
3d.addLast(x);                  // L x: x becomes the new back
4Integer a = d.pollFirst();     // f: remove the front, null when empty
5Integer b = d.pollLast();      // l: remove the back, null when empty

The sliding window maximum is the classic deque algorithm. The deque stores *indices* of window elements in decreasing order of their values. A new element first pops every smaller value from the back (they can never be a maximum again, because the new value is larger and will stay in the window longer), then joins the back. The front is the current maximum; it is removed from the front when its index leaves the window.

Each index enters and leaves the deque at most once, so the whole scan is O(n) even though a window may be large. Step through the “Classic” preset and watch the values being discarded from the back.

1static int[] windowMax(int[] a, int k) {
2    int[] out = new int[a.length - k + 1];
3    Deque<Integer> dq = new ArrayDeque<>();                 // indices, values decreasing
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();       // left the window
6        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();       // dominated by a[i]
7        dq.addLast(i);
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
9    }
10    return out;
11}

1public static int[] maxSlidingWindow(int[] arr, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();        // indices; values decrease front to back
3    int[] out = new int[arr.length - k + 1];
4    for (int i = 0; i < arr.length; i++) {
5        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();   // fell out of the window
6        while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) dq.pollLast();
7        dq.offerLast(i);
8        if (i >= k - 1) out[i - k + 1] = arr[dq.peekFirst()];
9    }
10    return out;
11}

A palindrome reads the same from both ends, so a deque fits naturally: keep only letters and digits, then repeatedly compare the front and the back and drop both. If every pair matches the text is a palindrome; one mismatch ends the search.

Compare the two characters with equals, not ==: d.pollFirst() returns a Character object, and == on boxed values compares references. The animation skips punctuation, as in “A man, a plan, a canal: Panama”.

1static boolean isPalindrome(String s) {
2    Deque<Character> d = new ArrayDeque<>();
3    for (char c : s.toCharArray()) if (Character.isLetterOrDigit(c)) d.addLast(Character.toLowerCase(c));
4    while (d.size() > 1) {
5        if (!d.pollFirst().equals(d.pollLast())) return false;   // compare the two ends, then drop both
6    }
7    return true;
8}

1static boolean isPalindrome(String s) {
2    Deque<Character> d = new ArrayDeque<>();
3    for (char c : s.toCharArray()) if (Character.isLetterOrDigit(c)) d.addLast(Character.toLowerCase(c));
4    while (d.size() > 1) {
5        if (!d.pollFirst().equals(d.pollLast())) return false;   // compare the two ends, then drop both
6    }
7    return true;
8}