Java Queue vs. Deque

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?

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

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 Deque-spezifische Methoden zum Einfügen und Entnehmen von Elementen von spezifischen Seiten des Deques. Eine Übersicht über diese Methoden findest du im oben verlinkten Artikel zum Deque-Interface.

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?

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

Iteration

Queue, und damit auch Deque, erweitern Collection und implementieren 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);
}Code-Sprache: Java (java)

Beide Datenstrukturen durchläuft der Iterator vom Anfang (Kopf) zum Ende, wie die Ausgabe des kleinen Beispiels zeigt:

Queue: 
A
B
C

Deque: 
A
B
C
Code-Sprache: Klartext (plaintext)

Deque hat zusätzlich eine descendingIterator()-Methode, mit der die Elemente in entgegengesetzter Richtung – also vom Ende zum Anfang – durchlaufen werden können:

for (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {
  String s = iterator.next();
  System.out.println(s);
}
Code-Sprache: Java (java)

Zusammenfassung

In diesem Artikel hast du die Unterschiede zwischen den Datenstrukturen Deque und Queue und den entsprechenden Java-Interfaces kennengelernt.

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.