ADT Stapel = Stack

In den Anwendungen tritt recht häufig die Situation auf, daß eine von vorneherein nicht begrenzte Zahl von Datenelementen so aufbewahrt werden muß, daß jeweils das zuletzt verwendete Datenelement direkt zugreifbar ist, während die anderen in umgekehrter Reihenfolge der Eintragung beim Abruf wieder erscheinen. Dieses Last-In-First-Out -Verhalten (LIFO) ist uns bereits bei der Formularmaschine zur Abarbeitung von Syntaxdiagrammen begegnet, und es ist generell typisch für Probleme, die bei der Analyse und Verarbeitung von kontextfreien Sprachen (insbesondere Programmiersprachen) auftreten, oder die sich (bei hinreichend tiefer theoretischer Einsicht) über solche Sprachen beschreiben lassen.

Eine Datenstruktur, die sich so verhält, nennt man einen Stapel, auch Keller oder Stack, und sie ist leicht algebraisch zu modellieren:

ADT Stacks(T) IS
SORTS:
stack, T, boolean
OPERATIONS:
newstack: stack
push: T stack stack
top: stack T
pop: stack stack
isempty: stack boolean
RULES:
isempty(newstack) = true
isempty(push(x, l)) = false
top(push(x, l)) = x
pop(push(x, l)) = l
END Stacks.
Dies stimmt bis auf die Bezeichnung der Funktionen push, pop und top mit den bereits besprochenen Listen überein, jedoch arbeiten wir hier nicht funktional mit Stack-Werten, sondern der Objekt-Aspekt steht im Vordergrund. Die dafür angegebenen Realisierungen können wir mit den notwendigen Änderungen direkt übernehmen.

Benötigt man nur einen einzigen Stapel, so kann man ihn auch in einem Array fester Länge ablegen, muß aber jetzt die aktuelle Höhe des Stapels mitführen (dies geschieht automatisch) und darauf achten, daß der Stapel nicht überläuft. Die Realisierung ist eine naheliegende Übungsaufgabe.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36