Java Deque: Methoden, Implementierungen, Beispiel

Nachdem Java in Version 5 das Queue-Interface bekommen hatte, kamen in Java 6 das Interface java.util.Deque und mit ArrayDeque und LinkedBlockingDeque die ersten Deque-Implementierungen hinzu. LinkedList, die es schon seit Java 1.2 gibt, implementiert seit Java 6 ebenfalls Deque; ConcurrentLinkedDeque folgte in Java 7.

Die Implementierungen unterscheiden sich in diversen Eigenschaften (wie bounded/unbounded, blocking/non-blocking, threadsicher/nicht threadsicher). In diesem Artikel vergleiche ich sie und zeige dir, wann du welche einsetzen solltest.

Java-Deque-Klassenhierarchie

Hier siehst du zunächst einen Überblick über die Deque-Interfaces und -Klassen in Form eines UML-Klassendiagramms. Farbig hervorgehoben sind die Deque-Interfaces und -Klassen; grau umrandet stehen links daneben die Queue-Interfaces und -Klassen:

Queue und BlockingQueue stelle ich in den Artikeln Java Queue und BlockingQueue vor.

Seit Java 21 erweitert Deque außerdem das Interface SequencedCollection, das die Methode reversed() hinzufügt. Was das für ein Deque bedeutet, erfährst du im Artikel Queue vs. Deque.

Das BlockingDeque-Interface werde ich im nächsten Teil des Tutorials vorstellen; danach folgen die konkreten Deque-Klassen ArrayDeque, LinkedList, ConcurrentLinkedDeque und LinkedBlockingDeque.

Du kannst jederzeit über die Navigation zu dieser Serie zu den entsprechenden Teilen springen.

Java-Deque-Methoden

Das Deque-Interface erbt von Queue und ergänzt zwölf Methoden zum Einfügen, Entnehmen und Betrachten von Elementen an beiden Enden des Deques – am Kopf (Head) und am Ende (Tail) – sowie drei Stack-Methoden. Dazu kommen removeFirstOccurrence(), removeLastOccurrence(), descendingIterator() und seit Java 21 reversed().

Aus Konsistenzgründen haben die Operationen, die Deque bereits von Queue erbt, Gegenstücke mit neuem Namen – beispielsweise entspricht Queue.add() der Methode Deque.addLast() und Queue.remove() der Methode Deque.removeFirst().

Die drei Stack-Methoden sind Alternativen zu Deque-Methoden, z. B. Deque.push() zu Deque.addFirst(). Diese Methoden hätten in ein eigenes Stack-Interface gehört.

Warum du für einen Stack Deque verwenden solltest und nicht die alte Klasse java.util.Stack, erfährst du im Artikel Java Deque vs. Stack.

All diese Queue- und Stack-Methoden habe ich im Folgenden explizit mit aufgeführt – und zwar jeweils bei den äquivalenten Deque-Methoden.

Am Ende dieses Kapitels findest du eine zusammenfassende Tabelle.

Methoden zum Einfügen in das Deque

Zum Einstieg ein grafischer Überblick aller Enqueue-Methoden:

Deque.addFirst() + addLast()

Diese Methoden fügen ein Element am Kopf bzw. am Ende des Deques ein. Sie haben keinen Rückgabewert. Wenn ein größenbeschränktes (bounded) Deque voll ist, werfen diese Methoden eine IllegalStateException.

Die vom Queue-Interface geerbte Methode Queue.add() entspricht Deque.addLast().

Die Deque.push()-Methode ist das Stack-Äquivalent zu Deque.addFirst().

Deque.offerFirst() + offerLast()

Auch offerFirst() und offerLast() fügen Elemente in das Deque ein, geben aber im Erfolgsfall true zurück. Wenn ein bounded Deque voll ist, geben diese Methoden false zurück, anstatt eine IllegalStateException zu werfen.

Die vom Queue-Interface geerbte Methode Queue.offer() entspricht Deque.offerLast().

Methoden zum Entnehmen aus dem Deque

Auch für die Dequeue-Methoden zunächst ein grafischer Überblick:

Deque.removeFirst() + removeLast()

Die Methoden removeFirst() und removeLast() entnehmen das Element vom Kopf bzw. Ende des Deques. Wenn das Deque leer ist, werfen sie eine NoSuchElementException.

Die vom Queue-Interface geerbte Methode Queue.remove() entspricht Deque.removeFirst().

Deque.pop() ist das Stack-Äquivalent zu Deque.removeFirst().

Deque.pollFirst() + pollLast()

pollFirst() und pollLast() entnehmen ebenfalls das Element vom Kopf bzw. Ende des Deques. Im Gegensatz zu removeFirst() und removeLast() werfen diese Methoden bei einem leeren Deque keine Exception, sondern geben null zurück.

Die vom Queue-Interface geerbte Methode Queue.poll() entspricht Deque.pollFirst().

Methoden zum Betrachten des Kopf- bzw. Endelements

Und zum Abschluss ein grafischer Überblick der Peek-Methoden:

Deque.getFirst() + getLast()

Die getFirst()- und getLast()-Methoden geben das Element vom Kopf bzw. Ende des Deques zurück, ohne es aus dem Deque zu entfernen. Wenn das Deque leer ist, werfen diese Methoden eine NoSuchElementException.

Die vom Queue-Interface geerbte Methode Queue.element() entspricht Deque.getFirst().

Deque.peekFirst() + peekLast()

Auch peekFirst() und peekLast() geben das Element vom Kopf bzw. Ende des Deques zurück, ohne es aus dem Deque zu entfernen. Bei einem leeren Deque werfen diese Methoden allerdings keine Exception, sondern geben null zurück.

Die vom Queue-Interface geerbte Methode Queue.peek() entspricht Deque.peekFirst(). peek() ist ebenfalls das Stack-Äquivalent zu peekFirst().

Weitere Deque-Methoden

Neben den Methoden für Kopf und Ende definiert das Deque-Interface diese vier Methoden:

• removeFirstOccurrence(Object o) entfernt das erste Vorkommen des übergebenen Elements – auch aus der Mitte des Deques – und gibt true zurück, wenn es eines gab.
• removeLastOccurrence(Object o) entfernt entsprechend das letzte Vorkommen.
• descendingIterator() liefert einen Iterator, der die Elemente vom Ende zum Kopf durchläuft.
• reversed() liefert seit Java 21 eine umgekehrte Sicht auf das Deque. Änderungen an der Sicht wirken auf das Deque selbst. getFirst() auf der Sicht liefert das letzte Element des Deques.

Deque-Methoden – Zusammenfassung

Die folgende Tabelle zeigt noch einmal alle zwölf Deque-Methoden, die drei Stack-Methoden und die äquivalenten Queue-Methoden, gruppiert nach Operation, Kopf oder Ende und Art der Fehlerbehandlung:

Operation	Kopf: Exception	Kopf: Rückgabewert	Ende: Exception	Ende: Rückgabewert
Element einfügen (enqueue)	addFirst(E e) push(E e)²	offerFirst(E e)	addLast(E e) add(E e)¹	offerLast(E e) offer(E e)¹
Element entnehmen (dequeue)	removeFirst() remove()¹ pop()²	pollFirst() poll()¹	removeLast()	pollLast()
Element ansehen (examine)	getFirst() element()¹	peekFirst() peek()¹ ²	getLast()	peekLast()

¹ Diese Methoden erbt Deque vom Queue-Interface; in einem Deque entsprechen sie der Deque-Methode in derselben Zelle.

² Diese Stack-Methoden sind zusätzlich im Deque-Interface definiert. Das JDK enthält leider kein Stack-Interface.

Wie erzeugt man ein Deque?

Das Interface java.util.Deque kann nicht direkt instanziiert werden.

Du musst also eine konkrete Deque-Implementierung auswählen, z. B. ein ArrayDeque:

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

Das JDK bietet vier Deque-Implementierungen an. Sie unterscheiden sich in Threadsicherheit, Blockierverhalten und Kapazität – der nächste Abschnitt vergleicht sie.

Deque-Implementierungen in Java: Welche einsetzen?

In der Tabelle ist der Name des Deques jeweils mit dem Teil der Serie verlinkt, in dem dieses Deque mit seinen spezifischen Eigenschaften vorgestellt wird.

Erläuterungen zu den Begriffen blocking, non-blocking, fairness policy, bounded und unbounded findest du im Artikel über das BlockingQueue-Interface.

Klasse	Thread- sicher?	Blocking/ Non-blocking	Fairness Policy	Bounded/ Unbounded	Iterator-Typ
ArrayDeque	Nein	Non-blocking	—	Unbounded	Fail-fast¹
LinkedList	Nein	Non-blocking	—	Unbounded	Fail-fast¹
ConcurrentLinkedDeque	Ja (optimistisches Locking durch Compare-and-set)	Non-blocking	—	Unbounded	Weakly consistent²
LinkedBlockingDeque	Ja (pessimistisches Locking mit einem Lock)	Blocking	Nicht verfügbar	Bounded³	Weakly consistent²

¹ Fail-fast: Wird das Deque nach dem Erzeugen des Iterators verändert – außer über dessen eigene remove()-Methode –, wirft der Iterator in der Regel eine ConcurrentModificationException. Garantiert ist das nicht. Verlass dich deshalb nicht darauf; der Mechanismus soll nur Programmierfehler aufdecken.

² Weakly consistent: Alle Elemente, die zum Zeitpunkt der Erzeugung des Iterators im Deque liegen, werden vom Iterator genau einmal durchlaufen. Änderungen, die danach erfolgen, können – müssen aber nicht – durch den Iterator berücksichtigt werden. Eine ConcurrentModificationException wirft ein solcher Iterator nie.

³ Übergibst du dem Konstruktor keine Kapazität, liegt die Grenze bei Integer.MAX_VALUE Elementen.

Anhand dieser Eigenschaften kannst du für deinen speziellen Einsatzzweck das richtige Deque auswählen. Meine Empfehlungen lauten:

• ArrayDeque für single-threaded Anwendungen
• ConcurrentLinkedDeque als threadsicheres, nicht blockierendes und unbounded Deque
• LinkedBlockingDeque als threadsicheres, blockierendes Deque – mit Kapazität bounded, ohne Kapazität praktisch unbounded

Hier meine Empfehlung noch einmal als Entscheidungsbaum:

Wahrscheinlich fällt dir auf, dass hier die LinkedList fehlt. Das liegt daran, dass ich grundsätzlich davon abrate, LinkedList als Deque einzusetzen.

Beispiel: Wie benutzt man ein Deque?

Das folgende Java-Code-Beispiel fügt Elemente an beiden Enden eines Deques ein und entnimmt sie danach abwechselnd vom Kopf und vom Ende.

Du findest den Code auch in der Klasse JavaDequeDemo im GitHub-Repository des Tutorials.

public class JavaDequeDemo {
  static void main() {
    // 1.
    Deque<Integer> deque = new ArrayDeque<>();

    // 2.
    for (int i = 20; i <= 22; i++) {
      deque.offerFirst(i);
      System.out.println("deque.offerFirst(" + i + ") --> deque = " + deque);
    }

    for (int i = 23; i <= 25; i++) {
      deque.offerLast(i);
      System.out.println("deque.offerLast(" + i + ")  --> deque = " + deque);
    }

    for (int i = 26; i <= 27; i++) {
      deque.offerFirst(i);
      System.out.println("deque.offerFirst(" + i + ") --> deque = " + deque);
    }

    // 3.
    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
    System.out.println();

    // 4.
    while (!deque.isEmpty()) {
      System.out.println("deque.pollFirst() = " + deque.pollFirst()
          + " --> deque = " + deque);
      System.out.println("deque.pollLast()  = " + deque.pollLast()
          + " --> deque = " + deque);
    }

    // 5.
    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
  }
}

Das Programm macht das Folgende (die Nummern verweisen auf die Quellcode-Kommentare):

1. Es erstellt ein ArrayDeque. Jede andere Deque-Implementierung würde in diesem Beispiel dieselbe Ausgabe liefern.
2. Es schreibt mit offerFirst() und offerLast() einige Werte in das Deque.
3. Es gibt mit isEmpty(), peekFirst() und peekLast() den Zustand des Deques aus.
4. Es entnimmt abwechselnd vom Kopf und vom Ende des Deques Elemente und gibt diese aus – so lange, bis das Deque leer ist.
5. Schließlich gibt es noch einmal den Zustand des Deques aus.

Das Programm gibt das Folgende aus:

deque.offerFirst(20) --> deque = [20]
deque.offerFirst(21) --> deque = [21, 20]
deque.offerFirst(22) --> deque = [22, 21, 20]
deque.offerLast(23)  --> deque = [22, 21, 20, 23]
deque.offerLast(24)  --> deque = [22, 21, 20, 23, 24]
deque.offerLast(25)  --> deque = [22, 21, 20, 23, 24, 25]
deque.offerFirst(26) --> deque = [26, 22, 21, 20, 23, 24, 25]
deque.offerFirst(27) --> deque = [27, 26, 22, 21, 20, 23, 24, 25]

deque.isEmpty()   = false
deque.peekFirst() = 27
deque.peekLast()  = 25

deque.pollFirst() = 27 --> deque = [26, 22, 21, 20, 23, 24, 25]
deque.pollLast()  = 25 --> deque = [26, 22, 21, 20, 23, 24]
deque.pollFirst() = 26 --> deque = [22, 21, 20, 23, 24]
deque.pollLast()  = 24 --> deque = [22, 21, 20, 23]
deque.pollFirst() = 22 --> deque = [21, 20, 23]
deque.pollLast()  = 23 --> deque = [21, 20]
deque.pollFirst() = 21 --> deque = [20]
deque.pollLast()  = 20 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null

An der Ausgabe siehst du: offerFirst() stellt jedes neue Element vor die bisherigen. Deshalb steht die 27 vorne, obwohl sie als letztes Element eingefügt wurde.

Zusammenfassung und Ausblick

In diesem Artikel hast du das Deque-Interface und seine Methoden kennengelernt, die vier Deque-Implementierungen des JDK und wann du welche einsetzen solltest. An einem Beispiel habe ich die Funktionsweise des Java-Deques gezeigt.

Im nächsten Teil des Tutorials lernst du das BlockingDeque-Interface kennen.