Stack vs. Queue: Unterschied der Datenstrukturen (und in Java)

In diesem Artikel erfährst du:

• Was sind die Unterschiede zwischen den Datenstrukturen Stack und Queue?
• Was bedeuten LIFO-Prinzip und FIFO-Prinzip?
• Wann setzt du einen Stack ein, wann eine Queue?
• Wie unterscheiden sich die Java-Klasse Stack und das Java-Interface 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 Element, 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.

Wann Stack, wann Queue?

Die Wahl ergibt sich aus der Reihenfolge, in der die Elemente verarbeitet werden sollen:

• Ein Stack passt, wenn das zuletzt hinzugefügte Element als erstes verarbeitet werden soll: die Zurück-Historie eines Browser-Tabs, der Call Stack mit den Rücksprungadressen von Methodenaufrufen oder die Verarbeitung verschachtelter Strukturen wie XML- und JSON-Dokumente in Parsern.
• Eine Queue passt, wenn die Elemente in Ankunftsreihenfolge abgearbeitet werden sollen: die Druckerwarteschlange oder HTTP-Requests, die ein Webserver zwischenspeichert, während alle Threads seines Threadpools belegt sind.

Ausführlichere Beispiele findest du in den beiden oben verlinkten Hauptartikeln.

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.

Methoden

Die Operationen aus der Terminologie-Tabelle heißen in Java so:

Operation	Stack	Queue (wirft Exception)	Queue (liefert Sonderwert)
Einfügen	push()	add()	offer()
Entnehmen	pop()	remove()	poll()
Ansehen	peek()	element()	peek()

Queue bietet jede Operation in zwei Varianten an: Die eine wirft bei leerer Queue (beim Einfügen: bei voller Queue) eine Exception, die andere liefert stattdessen null bzw. false zurück. Stack kennt nur eine Variante – pop() und peek() werfen bei leerem Stack eine EmptyStackException.

Thread-Sicherheit

Alle Stack-Operationen laufen über synchronized-Methoden (die eigenen oder die der Oberklasse Vector) – 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)

Stack oder Deque?

Die JDK-Entwickler:innen empfehlen, die Klasse Stack nicht mehr zu verwenden und stattdessen Implementierungen des Deque-Interfaces einzusetzen, das ebenfalls die Stack-Methoden push(), pop() und peek() definiert.

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)

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 das Collection-Interface implementiert und Deque es erweitert, haben beide z. B. die Methoden remove(), removeIf(), removeAll() und retainAll(), mit denen Elemente aus der Mitte der Datenstruktur entnommen werden können. Das sind keine bloß deklarierten Methoden – sie funktionieren bei Stack wie bei allen Deque-Implementierungen des JDK.

Stack hat zudem eine insertElementAt()-Methode, mit der Elemente in der Mitte des Stacks eingefügt werden können. Seit Java 21 kommt über das SequencedCollection-Interface noch addFirst() hinzu – die Methode fügt bei Stack am unteren Ende ein, also genau dort, wo ein Stack per Definition nicht erreichbar ist. Deque hat das Gegenstück: Wird eine ArrayDeque als Stack verwendet, liegt der Top am Anfang, und addLast() fügt unten ein.

Der Abschnitt „Stack-Interface“ und der Artikel „Queue mit einem Array implementieren“ zeigen, wie ein Stack- bzw. Queue-Interface eigentlich aussehen sollte.

Zusammenfassung

Die wichtigsten Unterschiede zwischen Stack und Queue auf einen Blick:

• Ein Stack arbeitet nach dem LIFO-Prinzip, eine Queue nach dem FIFO-Prinzip.
• In Java ist Stack eine konkrete Klasse, Queue ein Interface mit mehreren Implementierungen, aus denen du je nach Anwendungsfall wählst.
• Stack ist immer synchronisiert; bei Queue entscheidest du über die Implementierung, ob und wie synchronisiert wird.
• Beide verletzen das Interface-Segregation-Prinzip; als Stack solltest du daher eine Deque-Implementierung wie ArrayDeque verwenden.

Wie sich die Interfaces Queue und Deque unterscheiden, erfährst du im Artikel „Java Queue vs. Deque“.