Deque Interface

A deque (pronounced "deck") is a double-ended queue: a collection that supports adding, removing, and examining elements at both ends. The java.util.Deque interface extends Queue, so a deque can act as an ordinary FIFO queue, as a LIFO stack, or as something in between. Its main implementation, ArrayDeque, is the recommended choice for both queues and stacks in modern Java.

The Deque Concept

 addFirst / offerFirst / push                addLast / offerLast / offer
            │                                          │
            ▼                                          ▼
  head ─► [  A  |  B  |  C  |  D  ] ◄─ tail
            │                                          │
            ▼                                          ▼
 removeFirst / pollFirst / pop / poll      removeLast / pollLast

Where a plain queue restricts you to "add at the tail, remove at the head," a deque lets you work at either end. This one structure covers several needs:

Creating a Deque

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> d = new ArrayDeque<>();
d.offerFirst("B");      // [B]
d.offerFirst("A");      // [A, B]
d.offerLast("C");       // [A, B, C]

System.out.println(d.peekFirst());   // A
System.out.println(d.peekLast());    // C

ArrayDeque stores elements in a resizable circular array: the head and tail are indexes that wrap around the end of the array. Adding or removing at either end only moves an index, so these operations run in constant time without shifting any elements.

LinkedList also implements Deque and works the same way, but uses more memory per element. Prefer ArrayDeque unless you need a List and a Deque in one object or need to store null.

Methods at Both Ends

Like Queue, each operation has a version that throws an exception and one that returns a special value:

ArrayDeque is unbounded, so add and offer always succeed. The throwing and non-throwing forms matter for removal and examination: removeFirst() on an empty deque throws NoSuchElementException, while pollFirst() returns null.

ArrayDeque does not allow null elements, precisely because null is the "empty" signal of poll and peek.

Using a Deque as a Queue

The Queue methods map to deque methods as follows:

Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll());   // first

Using a Deque as a Stack

A stack adds and removes at the same end. Deque provides the classic stack method names, all operating on the head:

Deque<String> stack = new ArrayDeque<>();
stack.push("page1");
stack.push("page2");
stack.push("page3");

System.out.println(stack.pop());    // page3: last in, first out
System.out.println(stack.peek());   // page2
System.out.println(stack);          // [page2, page1]  (top of the stack first)

The Java documentation recommends Deque over the older java.util.Stack class for stacks. Stack extends Vector, synchronizes every method (adding overhead for single-threaded code), and exposes index-based methods that let code reach into the middle of the "stack." The next lesson covers Stack and this comparison in detail.

Note that peek() on a deque examines the head. That is the top for stack use and the front for queue use, which is consistent as long as you use one style per deque.

Iterating in Both Directions

Deque<Integer> d = new ArrayDeque<>(List.of(1, 2, 3, 4));

for (int x : d) {
    System.out.print(x + " ");                // 1 2 3 4  (head to tail)
}

Iterator<Integer> back = d.descendingIterator();
while (back.hasNext()) {
    System.out.print(back.next() + " ");      // 4 3 2 1  (tail to head)
}

Since Java 21, Deque is a SequencedCollection, and d.reversed() returns a reverse-ordered view that can be used directly in a for-each loop.

Other useful methods include removeFirstOccurrence(o) and removeLastOccurrence(o), which search from the respective end, along with size(), contains(), and clear().

Performance

ArrayDeque has no get(index) method. If you need indexed access as well as fast operations at both ends, consider whether the problem really needs both; usually one access pattern dominates.

Common Deque Patterns

Bounded history (keep the last N items)

Deque<String> recent = new ArrayDeque<>();
int limit = 3;
for (String file : List.of("a.txt", "b.txt", "c.txt", "d.txt")) {
    recent.offerFirst(file);              // newest at the front
    if (recent.size() > limit) {
        recent.pollLast();                // drop the oldest
    }
}
System.out.println(recent);               // [d.txt, c.txt, b.txt]

Checking palindromes

Compare characters taken from both ends:

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

isPalindrome("Malayalam");   // true
isPalindrome("Java");        // false

The elements are Character objects, so they are compared with equals, not ==.

Undo and redo

Two stacks, one for undo and one for redo, implement undo/redo in editors: each edit is pushed onto the undo stack; undoing pops from it and pushes onto the redo stack, and any new edit clears the redo stack.

Practical Example: Peak Traffic in a Sliding Window

A monitoring dashboard shows, for each minute, the highest request count over the last three minutes. Recomputing the maximum of every window from scratch would take O(n × k) time for n readings and windows of size k. A deque solves it in O(n) by keeping only the indexes that could still become a window's maximum.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class PeakTraffic {
    static int[] slidingMax(int[] values, int window) {
        int[] result = new int[values.length - window + 1];
        Deque<Integer> idx = new ArrayDeque<>();      // indexes; their values decrease from front to back

        for (int i = 0; i < values.length; i++) {
            if (!idx.isEmpty() && idx.peekFirst() <= i - window) {
                idx.pollFirst();                       // front index has left the window
            }
            while (!idx.isEmpty() && values[idx.peekLast()] <= values[i]) {
                idx.pollLast();                        // smaller values can never be the max again
            }
            idx.offerLast(i);
            if (i >= window - 1) {
                result[i - window + 1] = values[idx.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] requestsPerMinute = {120, 340, 210, 180, 560, 90, 300, 410, 150};
        System.out.println("Traffic:          " + Arrays.toString(requestsPerMinute));
        System.out.println("3-minute peaks:   " + Arrays.toString(slidingMax(requestsPerMinute, 3)));
    }
}

Output:

Traffic:          [120, 340, 210, 180, 560, 90, 300, 410, 150]
3-minute peaks:   [340, 340, 560, 560, 560, 410, 410]

The deque uses both ends, which is why a deque is required here:

• At the front, it removes an index once it slides out of the current window. The front always holds the index of the current window's maximum.
• At the back, before adding a new reading, it removes every index whose value is less than or equal to the new one. Those older, smaller readings can never be a maximum again while the newer, larger reading is in the window.

As a result, values in the deque always decrease from front to back. Each index is added once and removed at most once, so the whole computation is linear in the number of readings. The same technique is used for moving maximums and minimums in stock charts, rate limiting, and sensor monitoring.