Abstract Data Types (ADTs)

ABSTRACT DATA TYPE

An abstract data type (ADT) is a  mathematical model for a certain class of  data structures that have similar behavior; or for certain  data types of one or more  programming languages that have similar  semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly  cost) of those operations.

For example, an abstract  stack could be defined by three operations: push, that inserts some data item onto the structure, pop, that extracts an item from it (with the constraint that each pop always returns the most recently pushed item that has not been popped yet), and peek, that allows data on top of the structure to be examined without removal. When  analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.

Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the  type systems of programming languages. However, an ADT may be  implemented by specific  data types or  data structures, in many ways and in many programming languages; or described in a  formal specification language. ADTs are often implemented as  modules: the module's  interface declares procedures that correspond to the ADT operations, sometimes with  comments that describe the constraints. This  information hiding strategy allows the implementation of the module to be changed without disturbing the  client programs.