Deques

Both ends

A stack works at one end. A queue adds at one end and removes at the other. A deque — short for double-ended queue, pronounced “deck” — does everything at both ends.

That makes it a superset. Any stack or queue can be built from a deque by simply choosing which methods you call. This is why the two previous lessons both used ArrayDeque.

Deque methods

Six operations in two families: the throwing kind and the returning kind. Choose one family per program.

Using one

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

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

deque.addLast("middle");
deque.addFirst("start");
deque.addLast("end");

System.out.println(deque);              // [start, middle, end]
System.out.println(deque.peekFirst());  // start
System.out.println(deque.peekLast());   // end

deque.removeFirst();
deque.removeLast();
System.out.println(deque);              // [middle]

Adding at the front costs the same as adding at the back — both instant. That is the thing an ArrayList cannot do, where inserting at index 0 shifts every element.

As a stack, as a queue

// stack: add and remove at the same end
Deque<Integer> stack = new ArrayDeque<>();
stack.addFirst(1);
stack.addFirst(2);
System.out.println(stack.removeFirst());   // 2 — last in, first out

// queue: add at one end, remove at the other
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(1);
queue.addLast(2);
System.out.println(queue.removeFirst());   // 1 — first in, first out

Same class, same object type, different method pairing.

Which implementation

ArrayDeque stores elements in an array used as a circular buffer. Instead of shifting elements when the front is removed, it moves an internal index and wraps around at the end. That is how both ends stay instant while keeping array-like memory layout.

It rejects null, which is deliberate: the poll and peek methods use null to mean “empty”, so allowing null elements would make that signal ambiguous.

Where deques show up

A sliding window. Keeping the maximum of the last K values needs removal from both ends — new values push in at the back, stale ones drop off the front.

// indices of candidates for the maximum in each window of width k
Deque<Integer> window = new ArrayDeque<>();

for (int i = 0; i < values.length; i++) {
    // drop indices that have fallen out of the window
    while (!window.isEmpty() && window.peekFirst() <= i - k) {
        window.removeFirst();
    }
    // drop values smaller than the incoming one — they can never be the max
    while (!window.isEmpty() && values[window.peekLast()] <= values[i]) {
        window.removeLast();
    }
    window.addLast(i);

    if (i >= k - 1) {
        System.out.println("window max: " + values[window.peekFirst()]);
    }
}

Both ends are used for different purposes: the front discards expired entries, the back discards values that are now irrelevant. No other structure does this cleanly.

Undo and redo. Two deques, moving items between them.

Browser history. Back and forward, from either end.

A bounded buffer of recent readings. Add at the back, and drop from the front once you exceed the limit.

Deque<Double> recent = new ArrayDeque<>();

void record(double reading) {
    recent.addLast(reading);
    if (recent.size() > 50) {
        recent.removeFirst();      // discard the oldest
    }
}

That last pattern is genuinely common in robot code, where you want a rolling average of the last N sensor values without letting the buffer grow forever.

Next

Related