Abstract Data Types………..
When designing Data Structures and Algorithms it is desirable to avoid makingdecisions based on the accident of how you first sketch out a piece of code. Alldesign should be motivated by the explicit needs of the application. The idea ofan Abstract Data Type (ADT) is to support this (the idea is generally consideredgood for program maintainablity as well, but that is no great concern for thisparticular course). The specification of an ADT is a list of the operations thatmay be performed on it, together with the identities that they satisfy. This specificationdoes not show how to implement anything in terms of any simpler datatypes. The user of an ADT is expected to view this specification as the completedescription of how the data type and its associated functions will behave — noother way of interrogating or modifying data is available, and the response to anycircumstances not covered explicitly in the specification is deemed undefined.
To help make this clearer, here is a specification for an Abstract Data Type called STACK:
make empty stack(): manufactures an empty stack.
is empty stack(s): s is a stack. Returns TRUE if and only if it is empty.
push(x, s): x is an integer, s is a stack. Returns a non-empty stack which canbe used with top and pop. is empty stack(push(x, s))=FALSE.
top(s): s is a non-empty stack; returns an integer. top(push(x, s))= x.
pop(s): s is a non-empty stack; returns a stack. pop(push(x, s))=s.