Stack vs. Queue

In diesem Artikel erfährst du:

• Was sind die Unterschiede zwischen den Datenstrukturen Stack und Queue?
• Was bedeuten LIFO-Prinzip und FIFO-Prinzip?
• Wie unterscheiden sich die Java-Interfaces bzw. Klassen Stack und Queue?

Beginnen wir mit den Datenstrukturen.

Unterschied zwischen Stack und Queue

Ein Stack ist eine lineare Datenstruktur, bei der die Elemente nach dem LIFO-Prinzip ("last-in-first-out") eingefügt und entnommen werden. Das bedeutet, dass dasjenige Elemente, das als letztes auf den Stack gelegt wurde, als erstes wieder entnommen wird – und dass das Element, das zuerst auf den Stack gelegt wurde, als letztes wieder entnommen wird.

Eine Queue ist eine lineare Datenstruktur, bei der die Elemente nach dem FIFO-Prinzip ("first-in-first-out") eingefügt und entnommen werden. Elemente, die als erstes in die Queue eingefügt wurden, werden auch als erstes wieder entnommen. Elemente, die als letztes in die Queue eingefügt wurden, werden zuletzt entnommen.

Weitere Details, wie Anwendungsgebiete und Betrachtungen der Zeitkomplexität, findest du im Hauptartikel über die Stack-Datenstruktur und im Hauptartikel über die Queue-Datenstruktur.

Stack und Queue – Terminologie

Die Einfüge- und Entnahmeoperation sowie die Seiten der Datenstrukturen werden bei Stacks und Queues unterschiedlich bezeichnet:

Operation	Stack	Queue
Einfügen	Push (top)	Enqueue (back / tail)
Entnehmen	Pop (top)	Dequeue (front / head)

Die untere Seite des Stacks wird als "bottom" bezeichnet und ist über die Operationen nicht erreichbar.

Unterschied zwischen Java Stack und Queue

Dieser Abschnitt beschreibt die Unterschiede zwischen der Java-Klasse java.util.Stack und dem Interface java.util.Queue hinsichtlich verschiedener Aspekte.

Klasse vs. Interface

Stack ist eine Klasse (→ alle Details über die Stack-Klasse), also eine konkrete Implementierung des Stack-Datentyps im JDK.

Queue hingegen ist ein Interface (→ alle Details über das Queue-Interface). Das JDK stellt mehrere Queue-Implementierungen mit verschiedenen Charakteristika zur Verfügung. Entsprechend deines Anwendungsgebiets kannst du eine geeignete Queue-Implementierung auswählen.

Thread-Sicherheit

Alle Stack-Methoden sind synchronized – Stack ist also threadsicher.

Wenn wir jedoch keine Threadsicherheit benötigen, ist die Synchronisation überflüssig.

Und wenn wir Threadsicherheit benötigen, wäre die Verwendung von pessimistischen Locks, wie synchronized sie verwendet, nur bei einer hohen Anzahl an Zugriffskonflikten ("high thread contention") sinnvoll. Bei moderaten Zugriffskonflikten wäre optimistisches Locking besser geeignet.

Für das Queue-Interface bietet das JDK mehrere Implementierungen:

• nicht threadsichere Implementierungen (z. B. ArrayDeque¹)
• threadsichere Implementierungen mit pessimistischem Locking (z. B. LinkedBlockingQueue)
• threadsichere Implementierungen mit optimistischem Locking (z. B. ConcurrentLinkedQueue)

Tatsächlich empfehlen die JDK-Entwickler die Klasse Stack nicht mehr zu verwenden und stattdessen Implementierungen des Deque-Interfaces, welches ebenfalls die Stack-Methoden push() und pop() definiert, einzusetzen.

Auch für das Deque-Interface bietet das JDK zahlreiche Implementierungen:

• nicht threadsichere Implementierungen (z. B. ArrayDeque¹)
• threadsichere Implementierungen mit pessimistischem Locking (z. B. LinkedBlockingDeque)
• threadsichere Implementierungen mit optimistischem Locking (z. B. ConcurrentLinkedDeque)

¹ Das Java-Deque-Interface erbt von Queue, daher kann ArrayDeque sowohl als Deque als auch als Queue eingesetzt werden.

Verletzung des Interface-Segregation-Prinzips

Sowohl die Stack-Klasse als auch das Deque-Interface definieren Methoden, die die jeweilige Datenstruktur eigentlich nicht anbieten sollte. Damit verletzen beide das Interface-Segregation-Prinzip.

Da Stack und Deque letztendlich das Collection-Interface implementieren, haben sie z. B. die Methoden remove(), removeIf(), removeAll() und ratainAll(), mit denen Elemente aus der Mitte der Datenstruktur entnommen werden können.

Stack hat zudem eine insertElementAt()-Methode, mit der Elemente in der Mitte des Stacks eingefügt werden können.

Die Artikel "Stack in Java implementieren" und "Queue mit einem Array implementieren" zeigen, wie ein Stack- bzw. Queue-Interface eigentlich aussehen sollte.

Zusammenfassung

Dieser Artikel hat die Unterschiede zwischen den Datenstrukturen Stack und Queue und den entsprechenden Java-Interfaces bzw. Klassen erläutert.

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.