Wir nutzen Cookies, um das allgemeine Benutzerelebnis zu verbessern. Mit der Nutzung unseres Wikis stimmst du der Nutzung von Cookies zu.

Stapelspeicher

Darstellung der Funktion eines Stapelspeichers

Ein Stapel- oder Kellerspeicher (englisch Stack) ist eine Datenstruktur, welche Elemente der Reihenfolge ihrer Speicherung nach aufnimmt und in umgekehrter Reihenfolge wieder ausgibt (Last In – First Out|Last-In-First-Out-Prinzip (LIFO)). Ein Stapelspeicher kann in Scratch mit Hilfe von Listen implementiert werden.

Ein Stapel kann eine theoretisch beliebige, in der Praxis jedoch begrenzte Menge von Objekten aufnehmen. Elemente können nur oben auf den Stapel gelegt und auch nur von dort wieder gelesen werden (aus StapelspeicherWikipedia.jpg, Wikipedia.org).

Typischerweise wird ein Stapelspeicher mit folgenden Operationen angesprochen:

push (auch „einkellern“)
legt das Objekt oben auf den Stapel.
pop („auskellern“)
liefert das oberste Objekt und entfernt es vom Stapel

In manchen Umsetzungen gibt es auch noch den Befehl

peek („nachsehen“)
liefert das oberste Objekt, ohne es zu entfernen

Anwendung

Ein Stapelspeicher eignet sich gut zum Speichern von Daten in Unterroutinen, speziell wenn eine Unterroutine mehrfach von sich selbst aufgerufen werden kann (das ist bei der Implementierung von rekursiven Algorithmen oft der Fall).

Stapelspeicherstrukturen werden daher von den meisten Mikroprozessoren hardwaremäßig unterstützt. Da der Speicher in der Realität begrenzt ist, kann es zum Speicherüberlauf (Stack Overflow) kommen, wenn zuviele Elemente auf den Stack geschoben werden.

Stapelspeicher in Scratch

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

Definiere push (element)
füge (element) zu [Stapel v] hinzu

setze [a v] auf (3)
push (a)
ändere [a v] um (10)
push (a)
ändere [a v] um (10) //a ist jetzt 23
setze [a v] auf (Element (letztes v) von [Stapel v]) // dieser Befehl entspricht "peek"
lösche (letztes v) aus [Stapel v] //zusammen mit dem vorigen Befehl entspricht dies "pop", a ist jetzt 13
setze [a v] auf (Element (letztes v) von [Stapel v]) // a ist jetzt wieder 3
lösche (letztes v) aus [Stapel v] //zusammen mit dem vorigen Befehl entspricht dies "pop"

Mit Hilfe eines "hacked Blocks" kann der Code etwas schöner gestaltet werden:

Definiere push (element)
füge (element) zu [Stapel v] hinzu

Definiere pop (varname)
setze (varname) auf (Element (letztes v) von [Stapel v]) //um diesen Block einzugeben ist das JSON File zu editieren
lösche (letztes v) aus [Stapel v]

setze [a v] auf (3)
push (a)
ändere [a v] um (10)
push (a)
ändere [a v] um (10) //a ist jetzt 23
pop [a] //a ist jetzt 13
pop [a] //a ist jetzt wieder 3 und der Stapelspeicher ist leer

Damit das "push" and "pop" möglichst schnell erfolgt, empfiehlt es sich bei den benutzerdefinierten Blöcken die Option "ohne Bildschirmaktualisierung laufen lassen" einzuschalten.

Beispiele

Beispiele zur Verwendung eines Stapelspeichers in Scratch findet sich auf der Seite Rekursion.

In folgenden Projekten wird ein Stapelspeicher wie oben beschrieben eingesetzt:

112059659_144x108.png

Stapelspeicher

103822876_144x108.png

Gomoku - Five in a Row



Code zum Einbinden ins Forum:
[wiki=de:Stapelspeicher]Stapelspeicher[/wiki]