Definition: A set of data values and associated operations that are precisely specified independent of any particular implementation.
Also known as ADT.
Specialization (... is a kind of me.)
dictionary, stack, queue, priority queue, set, bag.
See also data structure.
Note: Since the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language, we may reason about effects of the operations, relations to other abstract data types, whether a program implements the data type, etc.
One of the simplest abstract data types is the stack. The operations new(), push(v, S), top(S), and popOff(S) may be defined with axiomatic semantics as following.
From these axioms, one may define equality between stacks, define a pop function which returns the top value in a non-empty stack, etc. For instance, the predicate isEmpty(S) may be added and defined with the following additional axioms.
After Nell Dale <email@example.com> May 2001.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 10 February 2005.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "abstract data type", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 10 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/abstractDataType.html