.Title Stack as an Abstract Data Type
. Values
A stack is an object that stores zero or more items.
Symbolize the set of stacks by the word Stack and the set of
items by the word Item.
Item::Sets=`Set of items`.
Stack::Sets=`Set of stacks`.
. Operations
The operations are expressed as functions as follows:
new: Stack, --`new returns a new empty stack`
pop: Stack <>->Stack, --`pop(S) returns S with out its head`
push: Stack >< Item->Stack, --`push(S,i) returns S with i on top`
top: Stack <>->Item, --`top(S) is a copy of the top of S`
empty: Stack ->Boolean. --`empty(S) is true iff S is empty`
The '<>->' arrow indicates that top and empty are partial functions.
Pop(S) and top(S) are not defined when empty(S) is true.
Note: these are mathematical functions and so simpler to reason about than
computer instruction/procedures.
.Example
Here is the result of pushing three integers (1,2,3 respectively) onto a new and
empty stack:
push(push(push(new, 1), 2), 3).
. Axioms
We require the following properties:
empty(new) is true.
empty(push(S,i)) is always false.
pop(push(s,i))=s.
top(push(x,i)=i.
Notice that this implies an important property of a stack,
|- data in a stack stays there until it is popped out.
Also
|- the data is stored and retrieved Last_In_First_Out(LIFO)
pop(push(push(y,a),b))=push(y,a)
. Relation to stacks in Sebesta Page 577.
Sebesta Math
Operations Functions
empty(S) empty(S)
top(S) top(S)
create(S) Afterwards S'=new.
push(S,E) Afterwards S'=push(S,E).
pop(S) Afterwards S'=pop(S).
destroy(S) Implicit. A value returned by a function is used and then destroyed.
. Implementations
There are many ways of implementing the physical data structure that
hold the items in a stack. Different languages will implement the
functions as functions, procedures, messages, and predicates.
In some languages 'new' has to be given a different name because
'new' is a reserved name in those languages (C++, Ada,...).
.See This directory