.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