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.