Queue vs. Deque in Java: Was ist der Unterschied?

In diesem Artikel erfährst du:

• Was sind die Unterschiede zwischen den Datenstrukturen Deque und Queue?
• Wie unterscheiden sich die Java-Interfaces Queue und Deque?
• Was hat sich seit Java 21 durch SequencedCollection geändert?

Beginnen wir mit den Datenstrukturen...

Unterschied zwischen Queue und Deque

Eine Queue ist eine Datenstruktur, die nach dem FIFO-Prinzip arbeitet: Elemente, die als erstes in die Queue gelegt werden, werden auch als erstes wieder entnommen. Elemente werden am Ende der Queue eingefügt und am Anfang (auch „Kopf“ genannt) wieder entnommen:

Alles über Queues erfährst du im Hauptartikel über die Queue-Datenstruktur.

Deque (ausgesprochen „Deck“) steht für „Double-ended Queue“, also eine Queue mit zwei Seiten. Beim Deque können Elemente auf beiden Seiten eingefügt und wieder entnommen werden:

Ein Deque ist eine Erweiterung der Queue und kann auch als solche benutzt werden. Es ist aber nicht auf FIFO-Funktionalität beschränkt. Es kann auch als LIFO-Datenstruktur – also als Stack – verwendet werden, indem man Elemente auf nur einer Seite einfügt und wieder entnimmt.

Details findest du im Hauptartikel über die Deque-Datenstruktur.

Unterschied zwischen Java Deque und Queue

Dieser Abschnitt beschreibt die Unterschiede zwischen den Java-Interfaces java.util.Queue und java.util.Deque.

Deque erweitert Queue und SequencedCollection

Deque (→ alle Details über das Deque-Interface) wurde in Java 6 als Erweiterung der in Java 5 eingeführten Queue (→ alle Details über das Queue-Interface) bereitgestellt.

Deque erweitert Queue um Methoden, die Elemente gezielt am Anfang oder am Ende einfügen und entnehmen. Eine Übersicht über diese Methoden findest du im oben verlinkten Artikel zum Deque-Interface.

Seit Java 21 erweitert Deque außerdem das Interface SequencedCollection. Dieses sichert eine festgelegte Reihenfolge der Elemente zu und definiert einheitliche Methoden für den Zugriff auf beide Enden – getFirst(), getLast(), addFirst(), addLast(), removeFirst() und removeLast(). Diese Methoden hatte Deque schon seit Java 6 – JEP 431 hat sie von dort in das neue Interface gezogen, daher ihre Namen. Neu hinzugekommen ist reversed(), das eine umgekehrte Sicht auf die Elemente liefert.

Queue erweitert SequencedCollection nicht: Eine Queue legt nur fest, welches Element am Kopf steht, nicht die Reihenfolge aller Elemente. Bei einer PriorityQueue etwa ist der Kopf das Element mit der höchsten Priorität; die übrigen Elemente haben keine festgelegte Reihenfolge – und damit gibt es auch kein „letztes“ Element, das getLast() liefern könnte.

Die folgende Grafik zeigt die Vererbungsbeziehungen der vier Interfaces, jeweils mit der Java-Version, in der sie eingeführt wurden, und den wichtigsten Methoden:

Implementierungen und Performance

Beide Interfaces bieten zahlreiche Implementierungen mit unterschiedlichen Eigenschaften. Welche du einsetzen solltest, erfährst du hier:

• Welche Queue-Implementierung sollte man einsetzen?
• Welche Deque-Implementierung sollte man einsetzen?

Die Performance hängt von der Implementierung ab, nicht vom Interface. Für single-threaded Anwendungen empfehle ich als Queue wie als Deque ArrayDeque; die passende Implementierung für den Zugriff aus mehreren Threads findest du in den beiden verlinkten Artikeln.

Da Deque von Queue erbt, kann jede Deque-Implementierung auch als Queue eingesetzt werden.

Iteration

Queue – und damit auch Deque – erweitert Collection und implementiert damit das Iterable-Interface. Wir können also innerhalb einer for-Schleife über beide Datenstrukturen iterieren:

Queue<String> queue = new ConcurrentLinkedQueue<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");

System.out.println("Queue:");
for (String s : queue) {
  System.out.println(s);
}

Deque<String> deque = new ArrayDeque<>();
deque.offerLast("A");
deque.offerLast("B");
deque.offerLast("C");

System.out.println("\nDeque:");
for (String s : deque) {
  System.out.println(s);
}

Ein Deque durchläuft der Iterator garantiert vom Anfang (Kopf) zum Ende. Für eine Queue gilt das nur bei FIFO-Implementierungen wie ConcurrentLinkedQueue oder LinkedList; der Iterator einer PriorityQueue hingegen liefert die Elemente in keiner bestimmten Reihenfolge. Die Ausgabe des Beispiels:

Queue:
A
B
C

Deque:
A
B
C

Seit Java 21 liefert deque.reversed() eine umgekehrte Sicht auf das Deque, über die du direkt iterieren kannst:

for (String s : deque.reversed()) {
  System.out.println(s);
}

Die Ausgabe:

C
B
A

In älteren Java-Versionen übernimmt das die Methode descendingIterator():

for (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {
  String s = iterator.next();
  System.out.println(s);
}

Zusammenfassung

Die folgende Tabelle stellt die Unterschiede zwischen Queue und Deque gegenüber – in den ersten drei Zeilen die Datenstrukturen, in den übrigen die Java-Interfaces:

	Queue	Deque
Prinzip	FIFO	FIFO und LIFO
Einfügen	nur am Ende	an beiden Enden
Entnehmen	nur am Kopf	an beiden Enden
Java-Interface seit	Java 5	Java 6
Erweitert	Collection	Queue und seit Java 21 SequencedCollection
Iterationsreihenfolge	abhängig von der Implementierung	garantiert vom Kopf zum Ende, umgekehrt per reversed()
Typische Implementierungen	LinkedList, PriorityQueue, ConcurrentLinkedQueue, ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue	ArrayDeque, LinkedList, ConcurrentLinkedDeque, LinkedBlockingDeque

Brauchst du nur FIFO, reicht das Queue-Interface. Sobald du an beiden Enden arbeitest oder rückwärts iterieren willst, greifst du zu Deque.