Deque-Interface in Java

Nachdem Java in Version 5 das Queue-Interface bekommen hat, kamen in Java 6 das Interface java.util.Deque und die ersten Deque-Implementierungen hinzu.¹

Die Implementierungen unterscheiden sich in diversen Eigenschaften (wie bounded/unbounded, blocking/non-blocking, threadsicher/nicht threadsicher). Auf diese Eigenschaften werde ich im Verlauf dieses Tutorials eingehen.

¹ Das stimmt nicht ganz: LinkedList, eine der Deque-Implementierungen, gibt es bereits seit Java 1.2.

Java Deque-Klassenhierarchie

Hier siehst du zunächst einen Überblick über die Deque-Interfaces und -Klassen in Form eines UML-Klassendiagramms:

Der kompletten linke Teil des Diagramms wird im Queue-Tutorial behandelt.

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 am rechten Rand zu den entsprechenden Teilen der Serie springen.

Java Deque-Methoden

Das Deque-Interface erbt von Queue und definiert 15 (!) zusätzliche Methoden zum Einfügen, Entnehmen und Betrachten von Elementen auf beiden Seiten des Deques (12 Deque-Methoden und 3 Stack-Methoden).

Aus Konsistenzgründen wurden die Operationen, die Deque bereits von Queue erbt, mit neuem Namen neu implementiert – beispielsweise Queue.add() als Deque.addLast() und Queue.remove() als Deque.removeFirst().

Das Deque-Interface definiert zusätzlich drei Stack-Methoden als Alternativen zu den Deque-Methoden, z. B. Deque.push() als Alternative zu Deque.addFirst(). Diese Methoden hätten eigentlich in ein Stack-Interface gehört.

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. Bei Erfolg geben die Methoden true zurück. Wenn ein größenbeschränktes (bounded) Deque voll ist, werfen diese Methoden eine IllegalStateException.

Die vom Queue-Interface geerbte Methode Queue.add() wird zu Deque.addLast() weitergeleitet.

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 und geben 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() wird zu Deque.offerLast() weitergeleitet.

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() wird zu Deque.removeFirst() weitergeleitet.

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 Methode bei einem leeren Deque keine Exception, sondern geben null zurück.

Die vom Queue-Interface geerbte Methode Queue.poll() wird zu Deque.pollFirst() weitergeleitet.

Methoden zum Betrachten des Head- bzw. Tail-Elements

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() wird zu Deque.getFirst() weitergeleitet.

Deque.peekFirst() + peekLast()

Auch peekFirst() und peekLast() geben das Kopf- bzw. Tail-Element 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() wird zu Deque.peekFirst() weitergeleitet. peek() ist ebenfalls das Stack-Äquivalent zu peekFirst().

Deque-Methoden – Zusammenfassung

Die folgende Tabelle zeigt noch einmal alle zwölf Deque-Methoden, die drei Stack-Methoden und die weitergeleiteten Queue-Methoden gruppiert nach Operation, Seite des Deques und Art der Fehlerbehandlung:

¹ Diese Methoden sind im Queue-Interface implementiert und rufen die entsprechenden Deque-Methoden auf.

² 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 instatiiert werden. Ein Interface beschreibt lediglich, welche Methoden eine Klasse implementieren muss, die dieses Interface implementiert.

Es muss also eine konkreten Deque-Implementierungen ausgewählt werden, z. B. ein ArrayDeque:

Deque<Integer> deque = new ArrayDeque<>();Code-Sprache: Java (java)

Die konkreten, vom JDK angebotenen Deque-Klassen werden in den folgenden Teilen des Tutorials – mit Erklärung ihrer Eigenschaften – vorgestellt:

• Java ArrayDeque (mit Beispielen)
• Java LinkedList (mit Beispielen)
• Java ConcurrentLinkedDeque (mit Beispielen)
• Java LinkedBlockingDeque (mit Beispielen)

Welche Implementierung du wann einsetzen solltest erfährst du im Teil "Deque-Implementierungen – Wann welche einsetzen?"

Beispiel: Wie benutzt man ein Deque?

Das folgende Java-Code-Beispiel erzeugt genau das Deque, das ich am Anfang des Artikels grafisch dargestellt habe. Danach werden die Elemente wieder entnommen.

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

public class JavaDequeDemo {
  public static void main(String[] args) {
    // 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());
  }
}
Code-Sprache: Java (java)

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

1. Es erstellt ein Deque. Welches du benutzt, ist für dieses Beispiel unwichtig, da die spezifischen Deque-Eigenschaften für dieses Beispiel irrelevant sind.
2. Es schreibt mit offerFirst() und offerLast() einige Werte in das Deque.
3. Wir geben mit isEmpty(), peekFirst() und peekLast() den Zustand des Deques aus.
4. Wir entnehmen abwechselnd vom Kopf und vom Ende des Deques Elemente und geben diese aus – solange, bis das Deque leer ist.
5. Abschließend schauen wir uns noch einmal den Zustand des Deques an.

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
Code-Sprache: Klartext (plaintext)

Die Funktionsweise des Deques lässt sich anhand der Ausgabe gut nachvollziehen.

Zusammenfassung und Ausblick

In diesem Artikel hast du das Deque-Interface und seine Methoden kennengelernt. An einem Beispiel habe ich die Funktionsweise des Java-Deques gezeigt.

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

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.