Java Deque Interface

Deque<E> — pronounced "deck," short for double-ended queue — is Queue<E> with a second end. Where a Queue only lets you remove from the head, a Deque lets you insert, remove, and examine at both the head and the tail. That single extra capability is enough to make Deque the contract behind two completely different abstractions: it's a queue, it's a stack, and the JDK recommends it as the default for both.

Two ends × three operations × two error styles

The interface looks intimidating at first because every operation appears in twelve shapes — head vs tail, insert vs remove vs examine, throws vs returns-special-value. But it's just the Queue 3×2 grid stretched across two ends:

Operation	First (head) — throws	First (head) — special value	Last (tail) — throws	Last (tail) — special value
Insert	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Remove	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Examine	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

The "throws" column is the one you call when an empty/full deque at that point would be a bug. The "special value" column is the one you call when emptiness is an expected state and you want to test for it in a loop condition.

The queue mapping

Deque extends Queue, so a Deque is a Queue. The inherited methods are aliases for the head-from-tail variants:

`Queue` method	`Deque` equivalent
`add(e)` / `offer(e)`	`addLast(e)` / `offerLast(e)`
`remove()` / `poll()`	`removeFirst()` / `pollFirst()`
`element()` / `peek()`	`getFirst()` / `peekFirst()`

Insert at the tail, remove from the head — that's the FIFO discipline a Queue already gives you, just spelled with the end-explicit names.

The stack mapping

Deque also defines three "stack" methods that all act on the head:

Stack method	Deque equivalent
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

Push on, pop off — LIFO discipline, same head, opposite end of the insert/remove from the queue mapping. This is why the Stack chapter pointed you here: the modern way to write a stack in Java is Deque<E> stack = new ArrayDeque<>(); and call push / pop / peek.

The rule: null is not allowed

Like Queue, the Deque contract reserves null as the "empty" sentinel for pollFirst, pollLast, peekFirst, peekLast. So every general-purpose Deque in the JDK rejects null elements with NullPointerException on insert. The single exception is LinkedList, which permits null for historical reasons — and inherits all the ambiguity that comes with it. Don't do that.

Iteration and reverse iteration

A Deque has two iterators by convention:

iterator() walks head to tail — the order you'd pollFirst repeatedly.
descendingIterator() walks tail to head — the order you'd pollLast repeatedly.

Both are typically fail-fast: mutating the deque from outside the iterator while iterating throws ConcurrentModificationException. Use Iterator.remove() or removeIf if you need to mutate during a walk.

Picking an implementation

In single-threaded code there are essentially two choices:

ArrayDeque — the default. Circular array, O(1) at both ends, no per-element node allocation, cache-friendly. Rejects null. Implements Deque and Queue.
LinkedList — doubly-linked nodes. Also implements List, so each element gets a node with prev/next pointers. Slower at both ends than ArrayDeque and uses more memory. Pick it only if you actually need Deque and List semantics on the same object.

For concurrent code (covered later in the concurrency part of the book):

ConcurrentLinkedDeque — lock-free, unbounded.
LinkedBlockingDeque — optionally bounded, blocking — the version you'd use to build a work-stealing queue or a producer/consumer with back-pressure at either end.

A worked example: queue, stack, and palindrome check in one deque

The program below uses one ArrayDeque as a FIFO queue, another as a LIFO stack, and a third to check whether a sentence is a palindrome by feeding both ends and comparing. The point is that the same interface, even the same class, plays all three roles.

java— editable, runs on the server

import java.util.*;

public class DequeShowcase {
  public static void main(String[] args) {
    // --- FIFO via Deque ---
    Deque<String> queue = new ArrayDeque<>();
    queue.offerLast("task-1");
    queue.offerLast("task-2");
    queue.offerLast("task-3");
    System.out.println("FIFO drain: " + queue.pollFirst() + ", "
        + queue.pollFirst() + ", " + queue.pollFirst());

// --- LIFO via Deque ---
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1); stack.push(2); stack.push(3);
    System.out.println("LIFO drain: " + stack.pop() + ", "
        + stack.pop() + ", " + stack.pop());

// --- Empty: returns special value vs throws ---
    Deque<String> empty = new ArrayDeque<>();
    System.out.println("pollFirst on empty: " + empty.pollFirst());
    System.out.println("peekLast  on empty: " + empty.peekLast());
    try { empty.removeFirst(); }
    catch (NoSuchElementException e) {
      System.out.println("removeFirst threw " + e.getClass().getSimpleName());
    }

// --- Iteration: forward and reverse ---
    Deque<Integer> d = new ArrayDeque<>(List.of(10, 20, 30, 40));
    System.out.print("forward: ");
    d.iterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();
    System.out.print("reverse: ");
    d.descendingIterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();

// --- Palindrome check: pollFirst vs pollLast until they meet ---
    System.out.println("\npalindrome? 'racecar' -> " + isPalindrome("racecar"));
    System.out.println("palindrome? 'hello'   -> " + isPalindrome("hello"));
  }

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

What this run shows:

The same class fills both queue and stack roles without renaming a single method beyond which end you address.
The "returns special value" methods quietly produce null for empty; the "throws" methods raise NoSuchElementException. Choose by whether emptiness is expected or a bug.
The palindrome check uses both ends in the same loop — pollFirst and pollLast together. That's the access pattern only a Deque gives you cheaply.

What's next

The Deque chapter closes the queue-side of the framework. The other big abstraction in Collection is the one that rejects duplicates: a Set is a Collection with the uniqueness contract baked in. We pick that up next.

Practice

You want a LIFO stack in modern Java code. Which line matches the JDK recommendation?

`Deque stack = new ArrayDeque<>();` then call `push` / `pop` / `peek`
`Stack stack = new Stack<>();` — the dedicated class is the clearest way to signal intent
`Queue stack = new LinkedList<>();` and call `add(0, ...)` to push
`List stack = new ArrayList<>();` and use `add` / `remove(size()-1)` — O(1) at the end