Dieses Tutorial erklärt den abstrakten Datentyp „Stack“ (deutsch: „Stapelspeicher“, „Kellerspeicher“ oder kurz „Stapel“, „Keller“):
- Wie funktioniert ein Stack?
- Was sind die Anwendungsgebiete für Stacks?
- Wie verwendet man die Java-Klasse „Stack“?
- Wie implementiert man einen eigenen Stack in Java?
Die ersten beiden Fragen beantwortet dieser Artikel, die beiden anderen die verlinkten Folgeteile.
Was ist ein Stack?
Ein Stack ist eine Sammlung von Elementen, bei der die Elemente nur auf einer Seite (in grafischen Darstellungen klassischerweise oben) eingefügt und wieder entnommen werden können.
Am besten stellt man sich einen Stack wie einen Tellerstapel vor:
Neue Teller können nur oben auf den Stapel gelegt werden, und Teller können auch nur von oben wieder entnommen werden.
Der zuletzt hinzugefügte Teller wird also als Erstes wieder entnommen – man spricht vom Last-in-First-out-Prinzip (LIFO).
LIFO-Prinzip beim Stack
Die folgende Grafik zeigt einen Stack mit fünf Strings, oben liegt „cherry“. Legst du „grape“ auf den Stack (Push), musst du „grape“ auch als Erstes wieder entnehmen (Pop):
Stack-Operationen: Push, Pop und Peek
Eine Stack-Datenstruktur bietet in der Regel die folgenden Operationen an:
- Push: legt ein Element oben auf den Stack
- Pop: entnimmt das oberste Element
- Peek oder Top: liefert das oberste Element, ohne es zu entnehmen
- Eine Prüfung, ob der Stack leer ist
Anwendungsgebiete für Stacks
Du kannst dir z. B. die Webseiten-Historie innerhalb eines Browser-Tabs als Stack vorstellen: Jedes Mal, wenn du einen Link anklickst, wird die vorherige URL auf einen Stack gelegt. Beim Betätigen des Zurück-Buttons wird die oberste URL des Stacks entnommen und wieder angezeigt.
In ähnlicher Weise legt bei der Ausführung eines Computerprogramms jeder Methodenaufruf einen Stack Frame mit Rücksprungadresse und lokalen Variablen auf den sogenannten Call Stack (deutsch: „Aufrufstapel“). Ist die Methode beendet, wird ihr Stack Frame wieder entnommen, und das Programm springt an die Aufrufposition zurück. Der StackOverflowError, den eine zu tiefe Rekursion auslöst, ist dir vielleicht schon mal begegnet.
In der JVM enthält jeder Stack Frame sogar einen zweiten Stack, den Operand Stack: Ein Bytecode-Befehl wie iadd nimmt zwei Werte von diesem Stack und legt ihre Summe wieder darauf.
Compiler und Parser verwenden ebenfalls Stacks, z. B. um zu prüfen, ob in einem JSON- oder XML-Dokument jede geöffnete Klammer und jedes geöffnete Tag wieder geschlossen wird, oder um mathematische Ausdrücke auszuwerten.
Zeitkomplexität der Stack-Operationen
Eine Einführung in das Thema Zeitkomplexität findest du im Artikel „O-Notation und Zeitkomplexität – anschaulich erklärt“.
In der Regel wird ein Stack mit einem Array oder einer verketteten Liste implementiert. Bei der verketteten Liste ist der Aufwand für das Einfügen und Entnehmen eines Elements konstant und hängt nicht von der Anzahl der im Stack vorhandenen Elemente ab.
Beim Array gilt das für das Entnehmen und, solange das Array eine feste Größe hat, auch für das Einfügen. Wächst das Array mit, ist das Einfügen amortisiert konstant: Ist es voll, kostet ein push() einmalig O(n) für das Umkopieren in ein größeres Array; auf alle Aufrufe verteilt bleibt der Aufwand konstant.
Die Zeitkomplexität lautet somit: O(1) – beim Einfügen in ein wachsendes Array amortisiert.
Stacks können auch mit Queues implementiert werden – das aber eher zu Übungszwecken: In der Implementierung dieses Tutorials muss push() alle vorhandenen Elemente umschichten und kostet O(n).
Stacks in Java
Die Klasse java.util.Stack gibt es seit Java 1.0. Wie du sie verwendest, zeigt der nächste Teil: Java Stack: Klasse, Methoden, Alternativen, Implementierung.
Ich empfehle dir allerdings, statt Stack ein Deque wie ArrayDeque zu verwenden – so steht es auch in der Dokumentation der Stack-Klasse selbst. Warum, liest du in „Java Deque vs. Stack: Warum Deque die bessere Wahl ist“.
Wenn dir dieser Artikel gefallen hat, freue ich mich über eine Bewertung auf meinem ProvenExpert-Profil.
