Stack, Queue, Deque in Java

Früher oder später müssen sich Java-Entwickler mit den Datenstrukturen Queue, Deque und Stack auseinandersetzen. In den Stack-, Queue- und Deque-Tutorials findest du Antworten auf die folgenden Fragen:

Wie funktionieren die Datenstrukturen Stack, Queue und Deque?
Wie unterscheiden sie sich?
Wie unterscheiden sich die Java-Interfaces bzw. Klassen Stack, Queue und Deque?
Welche Queue-, Deque- und Stack-Implementierungen gibt es im JDK?
Und welche der zahlreichen Implementierungen sind für welche Einsatzzwecke geeignet?
Wie kann man Queues, Deques und Stacks selbst implementieren?

Alle Code-Beispiele findest du im "Java Collections Guide" GitHub-Repository.

Datenstrukturen: Was sind Stacks, Queues und Deques?

Ein Stack (auf deutsch: "Stapelspeicher", "Kellerspeicher" oder kurz "Stapel", "Keller") ist eine Liste von Elementen, bei der die Elemente auf derselben Seite (in Darstellungen klassischerweise oben) eingefügt ("gestapelt") und wieder entnommen werden:

Stack vs. Queue vs. Deque: Stack-Datenstruktur — Stack-Datenstruktur

Weitere Details findest du im Hauptartikel über die Stack-Datenstruktur.

Eine Queue (auf deutsch: "Warteschlange") ist eine Liste von Elementen, bei der die Elemente auf einer Seite eingefügt und in derselben Reihenfolge auf der anderen Seite wieder entnommen werden:

Stack vs. Queue vs. Deque: Queue-Datenstruktur — Queue-Datenstruktur

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

Ein Deque (Double-ended queue, ausgesprochen "Deck" – eine deutsche Übersetzung gibt es nicht) ist eine Liste von Elementen, bei der die Elemente sowohl auf der einen als auch auf der anderen Seite eingefügt und entnommen werden können:

Stack vs. Queue vs. Deque: Deque-Datenstruktur — Deque-Datenstruktur

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

Wie unterscheiden sich Stack, Queue und Deque?

Die Unterschiede zwischen den jeweiligen Datenstrukturen sind in folgenden Artikeln erklärt:

Welche Java-Implementierungen gibt es, und welche sollte man einsetzen?

Die Einsatzempfehlungen basieren auf den Charakteristika der JDK-Queue- und Deque-Implementierungen, die in den verlinkten Artikeln näher beschrieben sind.

Folgendes sind meine Empfehlungen für allgemeine Einsatzzwecke:

Verwende ArrayDeque für single-threaded Anwendungen.
ConcurrentLinkedQueue und ConcurrentLinkedDeque als threadsichere, nicht blockierende und unbounded Queues/Deques.
ArrayBlockingQueue als threadsichere, blockierende, bounded Queue, sofern du wenig Contention zwischen Producer- und Consumer-Threads erwartest.
LinkedBlockingQueue als threadsichere, blockierende, bounded Queues, wenn du eher hohe Contention zwischen Producer- und Consumer-Threads erwartest (am besten testen, welche Implementierung für deinen Use Case performanter ist).
LinkedBlockingDeque als threadsicheres, blockierendes, bounded Deque.
... oder die optimierten Queues von JCTools.

Die folgenden Queues sind für spezielle Einsatzwecke vorgesehen:

PriorityQueue und PriorityBlockingQueue, um die Elemente sortiert nach Priorität zu entnehmen.
DelayQueue, um Elemente nach einer vorgegebenen Wartezeit zu entnehmen.
SynchronousQueue, um Elemente synchron von einem Producer an einen Consumer zu übergeben.
LinkedTransferQueue, um einen Producer-Threads solange zu blockieren, bis das Element an einen Consumer-Thread transferiert wurde.

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.