Stack

Ein Stack ist eine dynamische Datenstruktur, die auf dem "Last In First Out"-Prinzip (LIFO) basiert.

Erklärung

Du kannst dir einen Stack auch als einen Tellerstapel an einem Buffet vorstellen:

In einem Stack gilt das "Last In First Out"-Prinzip. Also wird das Element, das als Letztes hinzugefügt wird, als Erstes bearbeitet.

Stacks werden zum Beispiel verwendet, um Rücksprungadressen oder Funktionsaufrufe zu speichern.

Operationen am Beispiel

Ein Stack hat vier wichtige Operationen, die auf dieser Datenstruktur ausgeführt werden können:

• Push: Einfügen eines Objektes an das Ende.
• Pop: Entfernen des zuletzt eingefügten Objekts.
• Peek: Anzeigen des ersten Objekts, ohne es zu entfernen.
• Empty: Überprüfen, ob der Stack leer ist.

Push

Schau dir das wieder am Beispiel eines Tellerstapels an:

Ein neuer Teller wird oben auf den Stapel gestellt.

Pop

Der oberste Teller wird vom Stapel genommen.

Peek

Der oberste Teller wird betrachtet, aber nicht vom Stapel genommen.

Empty

Die empty-Operation hilft dir dabei, zu überprüfen, ob ein Stapel leer ist.

Operationen an der Datenstruktur

Ein Stack kann als ein Array implementiert werden. Dabei werden die Werte startend bei Index = 0 gespeichert. Zusätzlich wird eine Variable top benötigt, die den Index des zuletzt eingefügten Objekts angibt. Diese wird mit -1 initialisiert. Diese Implementation ist bei vielen Programmiersprachen zum Glück schon vorimplementiert, was dir viel Zeit sparen kann!

Schau dir nun wieder die Operationen an, die auf einem Stack angewendet werden können.

Push

Um ein neues Element auf den Stack zu legen, wird die Variable top um eins erhöht. Dann wird in diese Stelle das neue Element eingefügt.

Pop

Um das zuletzt hinzugefügte Element im Stack zu löschen, wird top um eins verringert.

Peek

Um das letzte Element in dem Stack auszugeben, ohne ihn zu löschen, wird einfach nur top ausgegeben.

Empty

Ein Stack ist leer, wenn top den Wert -1 hat.

Beispiel

Push

Füge die 3 an folgenden Stack an:

Dabei wird zuerst top um eins erhöht. Danach wird an diesem Index die 3 angefügt.

Pop

Um das letzte Element aus dem Stack zu löschen, wird top um eins verringert:

Peek

Wenn du nur wissen möchtest, welche Zahl ganz oben liegt, wird einfach nur top ausgegeben:

In diesem Beispiel wird also 6 ausgegeben.

Empty

Wenn du überprüfen möchtest, ob folgender Stack leer ist, musst du nur checken, ob top den Wert -1 hat.

Da top den Wert 6 hat, ist dieser Stack nicht leer.