NIST

abstract data type

(definition)

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.

  1. new() returns a stack
  2. popOff(push(v, S)) = S
  3. top(push(v, S)) = v
where S is a stack and v is a value. (The usual pop operation is a combination of top, to return the top value, and popOff, to remove the top value.) Contrast this with the axiomatic semantics definition of a set, a dictionary, or a queue.

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.

  1. isEmpty(new()) = true
  2. isEmpty(push(v, S)) = false

After Nell Dale <ndale@cs.utexas.edu> May 2001.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 10 February 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "abstract data type", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/abstractDataType.html