Java Deque Interface | W3Docs Learn Java

Deque<E> — ausgesprochen „Deck", kurz für double-ended queue (doppelseitige Warteschlange) — ist Queue<E> mit einem zweiten Ende. Während eine Queue das Entfernen nur am Kopf erlaubt, erlaubt eine Deque das Einfügen, Entfernen und Untersuchen an beiden Enden — am Kopf und am Ende. Diese eine zusätzliche Fähigkeit reicht aus, um Deque zum Vertrag hinter zwei völlig unterschiedlichen Abstraktionen zu machen: Es ist eine Warteschlange, es ist ein Stack, und das JDK empfiehlt es standardmäßig für beide.

Zwei Enden × drei Operationen × zwei Fehlerstile

Das Interface wirkt auf den ersten Blick einschüchternd, weil jede Operation in zwölf Varianten erscheint — Kopf vs. Ende, Einfügen vs. Entfernen vs. Untersuchen, Ausnahme vs. Sonderwert. Es ist aber lediglich das Queue-3×2-Raster auf zwei Enden ausgedehnt:

Operation	Erstes Element (Kopf) — wirft	Erstes Element (Kopf) — Sonderwert	Letztes Element (Ende) — wirft	Letztes Element (Ende) — Sonderwert
Einfügen	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Entfernen	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Untersuchen	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

Die Spalte „wirft" ist diejenige, die man aufruft, wenn eine leere oder volle Deque an dieser Stelle ein Fehler wäre. Die Spalte „Sonderwert" ist diejenige, die man aufruft, wenn eine leere Deque ein erwarteter Zustand ist und man darauf in einer Schleifenbedingung prüfen möchte.

Die Queue-Zuordnung

Deque erweitert Queue, sodass eine Deque auch eine Queue ist. Die geerbten Methoden sind Aliase für die kopfseitigen Varianten:

`Queue`-Methode	`Deque`-Äquivalent
`add(e)` / `offer(e)`	`addLast(e)` / `offerLast(e)`
`remove()` / `poll()`	`removeFirst()` / `pollFirst()`
`element()` / `peek()`	`getFirst()` / `peekFirst()`

Am Ende einfügen, am Kopf entfernen — das ist die FIFO-Disziplin, die eine Queue bereits bietet, nur mit den endseitig expliziten Namen geschrieben.

Die Stack-Zuordnung

Deque definiert außerdem drei „Stack"-Methoden, die alle am Kopf wirken:

Stack-Methode	Deque-Äquivalent
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

Obenauf schieben, oben abnehmen — LIFO-Disziplin, dasselbe Kopfende, entgegengesetztes Ende im Vergleich zur Queue-Zuordnung. Deshalb hat das Stack-Kapitel auf dieses hier verwiesen: Der moderne Weg, in Java einen Stack zu schreiben, ist Deque<E> stack = new ArrayDeque<>(); und dann push / pop / peek aufzurufen.

Die Regel: null ist nicht erlaubt

Wie bei Queue reserviert der Deque-Vertrag null als „leeres"-Sentinel für pollFirst, pollLast, peekFirst, peekLast. Daher lehnen alle universellen Deque-Implementierungen im JDK null-Elemente beim Einfügen mit einer NullPointerException ab. Die einzige Ausnahme ist LinkedList, die aus historischen Gründen null erlaubt — und alle damit verbundenen Mehrdeutigkeiten erbt. Das sollte man vermeiden.

Iteration und Rückwärtsiteration

Eine Deque besitzt per Konvention zwei Iteratoren:

iterator() läuft von Kopf zu Ende — in der Reihenfolge, in der man wiederholt pollFirst aufrufen würde.
descendingIterator() läuft von Ende zu Kopf — in der Reihenfolge, in der man wiederholt pollLast aufrufen würde.

Beide sind typischerweise fail-fast: Das Verändern der Deque von außerhalb des Iterators während der Iteration wirft eine ConcurrentModificationException. Verwende Iterator.remove() oder removeIf, wenn du während des Durchlaufens mutieren musst.

Eine Implementierung wählen

Im single-threaded Code gibt es im Wesentlichen zwei Möglichkeiten:

ArrayDeque — die Standardwahl. Zirkuläres Array, O(1) an beiden Enden, keine Knotenallokation pro Element, cache-freundlich. Lehnt null ab. Implementiert Deque und Queue.
LinkedList — doppelt verkettete Knoten. Implementiert auch List, sodass jedes Element einen Knoten mit prev/next-Zeigern erhält. An beiden Enden langsamer als ArrayDeque und speicherintensiver. Nur wählen, wenn man tatsächlich Deque- und List-Semantik am selben Objekt benötigt.

Für nebenläufigen Code (später im Nebenläufigkeitsteil des Buches behandelt):

ConcurrentLinkedDeque — sperrfrei, unbegrenzt.
LinkedBlockingDeque — optional begrenzt, blockierend — die Variante, die man zum Aufbau einer Work-Stealing-Queue oder eines Producer/Consumer mit Gegendruck an beiden Enden verwenden würde.

Ein durchgearbeitetes Beispiel: Queue, Stack und Palindromprüfung in einer Deque

Das folgende Programm verwendet eine ArrayDeque als FIFO-Warteschlange, eine weitere als LIFO-Stack und eine dritte, um zu prüfen, ob ein Satz ein Palindrom ist, indem beide Enden befüttert und verglichen werden. Der Punkt ist, dass dasselbe Interface, sogar dieselbe Klasse, alle drei Rollen übernimmt.

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;
  }
}

Was dieser Durchlauf zeigt:

Dieselbe Klasse füllt sowohl Queue- als auch Stack-Rollen aus, ohne eine einzige Methode umzubenennen — außer an welchem Ende man angreift.
Die „Sonderwert"-Methoden liefern bei leerem Zustand still null zurück; die „wirft"-Methoden lösen NoSuchElementException aus. Man wählt nach dem Kriterium, ob Leerheit erwartet oder ein Fehler ist.
Die Palindromprüfung verwendet beide Enden in derselben Schleife — pollFirst und pollLast zusammen. Das ist das Zugriffsmuster, das nur eine Deque günstig ermöglicht.

Was kommt als Nächstes

Das Deque-Kapitel schließt die warteschlangenseitige Betrachtung des Frameworks ab. Die andere große Abstraktion in Collection ist diejenige, die Duplikate ablehnt: Ein Set ist eine Collection mit eingebautem Eindeutigkeitsvertrag. Das schauen wir uns als Nächstes an.

Übungen

Übung

Du möchtest einen LIFO-Stack in modernem Java-Code. Welche Zeile entspricht der JDK-Empfehlung?

`Deque<String> stack = new ArrayDeque<>();` dann `push` / `pop` / `peek` aufrufen`Stack<String> stack = new Stack<>();` — die dedizierte Klasse signalisiert die Absicht am klarsten`Queue<String> stack = new LinkedList<>();` und `add(0, ...)` zum Pushen aufrufen`List<String> stack = new ArrayList<>();` und `add` / `remove(size()-1)` verwenden — O(1) am Ende