Deque vs. Queue - Feature ImageDeque vs. Queue - Feature Image
HappyCoders Glasses

Java Queue vs. Deque

Sven Woltmann
Sven Woltmann
7. Juni 2022

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:

Queue vs. Deque: Queue-Datenstruktur
Queue-Datenstruktur

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:

Queue vs. Deque: Deque-Datenstruktur
Deque-Datenstruktur

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:

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.