Datenstrukturen: Stack / Stapelspeicher

Der Stapelspeicher

Der Stack (deutsch: Stapelspeicher oder auch Kellerspeicher genannt) ist eine Datenstruktur, die einer einfach verketteten Liste ähnlich ist. Sie folgt nach dem LIFO-Prinzip (Last-In-First-Out). Das zuletzt eingefügte Objekt ist das Objekt was zuerst herausgenommen wird. Genauso wie eine Liste kann der Stack dynamisch erweitert werden.

Im Gegensatz zu einer Liste gibt es keine Möglichkeit ein Objekt irgendwo zwischen zwei weiteren Objekten einzufügen, oder zu entfernen.
Ein Stack beherscht nur die Funktionen: am Ende einfügen (push), vom Ende entfernen (pop) und letztes Objekt finden (peek). Gegebenenfalls kann man Stacks noch Kopieren.

Abbildung: Ein Stack

Ein Stack ist quasi eine einfach verkettete Liste mit Einschränkungen in der Funktionalität. Das hört sich erstmal nach einer überflüssigen Datenstruktur an, dennoch gibt es Anwendungsfälle wo Stacks häufig eingesetzt werden.

Anwendungsbeispiel

• Ein Stack kann eingesetzt werden, um eine Syntax auf Korrektheit zu überprüfen
  Beispiel : 3 * ( 5 + 7 ) - 1 oder abstrakter: zahl operator klammer zahl operator zahl klammer operator zahl.
  Hier könnte man ein Muster überprüfen, ob die Berechnung laut einer vorgegebenen Regel definiert ist. Wird ein Element gefunden was gegen die Regel verstößt, so gilt die Syntax als nicht gültig.
• Stacks verwalten Funktionsaufrufe bei Programmiersprachen
• Stacks werden für Unterbrechungsroutienen (Interrupts) benutzt

Quelle
cdn.programiz.com/sites/tutorial2program/files/stack.jpg
http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci235/lecture_notes/chapter_06.pdf