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:

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:

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:

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:

• Unterschiede zwischen Deque und Stack
• Unterschiede zwischen Queue und Deque
• Unterschiede zwischen Stack und Queue

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.