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