(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.

- new() returns a stack
- popOff(push(v, S)) = S
- top(push(v, S)) = v

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.

- isEmpty(new()) = true
- 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