Stack Datenstruktur

In diesem Tutorial lernst du alles über 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?

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.

Da dadurch der zuletzt hinzugefügte Teller als erstes wieder entnommen wird, spricht man vom Last-in-First-out-Prinzip (LIFO).

LIFO-Prinzip beim Stack

Beim abstrakten Datentyp "Stack" könnte das dann in etwa wie folgt aussehen:

Die Grafik zeigt einen Stack, der einige Strings enthält. Als nächstes Element wird "grape" auf den Stack gelegt. Danach würden wir "grape" auch als erstes wieder entnehmen müssen.

Eine Stack-Datenstruktur bietet in der Regel die folgenden Operationen an:

"Push": Hinzufügen eines Elements auf den Stack
"Pop": Entnehmen eines Elements von der Oberseite des Stacks
"Peek" oder "Top": Betrachten des obersten Elements des Stapels, 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: Jedesmal, 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 werden bei der Ausführung eines Computerprogramms die Rücksprungsadressen beim Aufruf von Methoden auf den sogennanten Call Stack gelegt (deutsch: "Aufrufstapel"), so dass nach Ausführung der Methode an die Aufrufposition zurückgesprungen werden kann. Der durch eine zu tiefe Verschachtelung verursachte StackOverflowError ist dir vielleicht schon mal begegnet.

Auch Compiler und Parser verwenden Stacks, z. B. bei der Verarbeitung von XML- und JSON-Dokumenten oder der Evaluierung von mathematischen Ausdrücken.

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 beiden Varianten ist der Aufwand für das Einfügen oder Entnehmen eines Elements konstant und hängt nicht von der Anzahl der im Stack vorhandenen Elemente ab.

Die Zeitkomplexität lautet somit: O(1).

Stacks können auch mit Queues implementiert werden – das aber eher zu Schulungszwecken. Die Zeitkomplexität ist dann höher. Mehr dazu liest du im entsprechenden Teil des Tutorials.

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.