Stapelspeicher

Im Supermarkt sind Getränkekisten gestapelt. Man kann immer nur eine Kiste von oben herunternehmen. Um zu einer Kiste ganz unten zu gelangen, muss man zuerst einzeln die Kisten von oben her herunterheben. Diejenige Kiste, die als letzte auf den Stapel gestellt wurde, muss wieder als erste heruntergenommen werden. Das bedeutet LIFO: Last in, first out. Auf Englisch wird der Stapelspeicher als stack bezeichnet.

Darstellung der Funktion eines Stapelspeichers

init: Leere den Stapel
push: Gib (Objekt) auf den Stapel
pop: Nimm das oberste Objekt vom Stapel
top / peek: Welches Objekt liegt oben am Stapel?
isEmpty: Gibt es Objekte am Stapel?

Stapelspeicher werden im Computer sehr häufig verwendet:

• Syntaxprüfungen: Sind mathematische Ausdrücke korrekt aufgebaut?
• Parser: Ist ein XML-Dokument oder ein HTMl-Dokument korrekt?
• Compiler: Kann ein Programm in ein für den Computer ausführbares Format umgewandelt werden?
• Mikroprozessoren verwenden neben Registern (einzelnen Variablen) vor allem den Stapelspeicher, um Befehle und Daten abzulegen.
• Bei Rekursionen muss der aktuelle Zustand ("Wo befinde ich mich gerade im Programm?", "Welche Werte sind gerade in den Variablen gespeichert?") zwischengespeichert werden.

Der Stapelspeicher in Scratch

Ein Stapelspeicher kann in Scratch sehr einfach mit Hilfe einer Liste umgesetzt werden:

Definiere Leere den Stapel
lösche alles aus [Stapel v]

Definiere Lege (Objekt) auf den Stapel PUSH
füge (Objekt) zu [Stapel v] hinzu

Definiere Nimm das oberste Objekt vom Stapel POP
setze [Stapel_Ergebnis v] auf (Element (Länge von [Stapel v]) von [Stapel v])
lösche (Länge von [Stapel v]) aus [Stapel v]

Definiere Welches Objekt liegt oben am Stapel?
setze [Stapel_Ergebnis v] auf (Element (Länge von [Stapel v]) von [Stapel v])

Definiere Gibt es Objekte am Stapel?
setze [Stapel_Ergebnis v] auf <(Länge von [Stapel v]) > [0]>

Beispiele

Stapelspeicher

Gomoku - Five in a Row