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) ISDies 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.
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.
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.