抽象数据类型

在计算机科学中，抽象数据类型（ADT）是一种数据类型的数学模型。一个抽象数据类型是由它的行为（语义）定义的，从用户的角度来看，数据，特别是在可能的值，对这种类型的数据的可能操作，以及这些操作的行为。

这种数学模型与数据结构形成对比，后者是数据的具体表示，是实现者而不是用户的观点。从形式上看，ADT可以被定义为一类对象，其逻辑行为由一组值和一组操作定义；这类似于数学中的代数结构。

行为的含义因作者而异，行为的两种主要形式规范是公理（代数）规范和抽象模型；它们分别对应于抽象机器的公理语义和操作语义。

一些作者还包括计算复杂性（成本），包括时间（用于计算操作）和空间（用于表示数值）。在实践中，许多常见的数据类型都不是ADT，因为抽象并不完美，用户必须注意到由于表示方法而导致的算术溢出等问题。

例如，整数通常被存储为固定宽度的值（32位或64位二进制数），因此，如果超过最 大值，会出现整数溢出。ADT是计算机科学中的一个理论概念，用于算法、数据结构和软件系统的设计和分析，并不对应于计算机语言的具体特征--主流计算机语言并不直接支持正式规定的ADT。

然而，各种语言特征与ADT的某些方面相对应，并且容易与ADT本身相混淆；这些特征包括抽象类型、不透明数据类型、协议和契约设计。ADTs是由BarbaraLiskov和StephenN.Zilles在1974年首次提出的，作为CLU语言开发的一部分。

例如，整数是一个ADT，定义为...-2、-1、0、1、2、...等值，以及加、减、乘、除等运算，还有大于、小于等，其行为符合熟悉的数学原理（注意整数除法），与整数如何被计算机表示无关。明确地说，行为包括遵守各种公理（加法的关联性和互换性等），以及操作的前提条件（不能除以0）。

通常情况下，整数在数据结构中被表示为二进制数，最常见的是二的补码，但也可能是二进制编码的十进制或一的补码，但对于大多数目的来说，用户可以使用抽象而不是具体选择的表示方法，并且可以简单地使用数据，好像该类型是真正抽象的。一个ADT不仅包括操作，还包括一个值域，以及对定义操作的约束。

一个接口通常只指操作，也许还有对操作的一些约束，如前条件和后条件；但不包括其他约束，如操作之间的关系。例如，一个抽象的堆栈，它是一个后进先出的结构，可以由三个操作来定义：push，在堆栈中插入一个数据项；pop，从堆栈中删除一个数据项；peek或top，访问堆栈顶部的一个数据项，而不删除。

一个抽象的队列，是一个先进先出的结构，也会有三个操作：enqueue，向队列中插入一个数据项；dequeue，从队列中移除第 一个数据项；以及front，访问并提供队列中的第 一个数据项。

如果这些是全部的定义，那么就没有办法区分这两种数据类型和它们非常不同的预期排序行为。

因此，引入了一个约束条件，对于堆栈来说，每个pop总是返回（和删除）最近推送的尚未被pop的项目，而对于队列来说（相反），指定pop操作最近推送的最少的项目。

在分析算法的效率时，我们也可以规定，无论有多少数据项被推入堆栈，所有的操作都需要相同的时间，并且堆栈对每个元素使用的存储量是恒定的。然而，时间界限并不总是被认为是ADT定义的一部分。

抽象数据类型是纯粹的理论实体，（除其他外）用于简化抽象算法的描述，对数据结构进行分类和评估，并正式描述编程语言的类型系统。然而，一个ADT可以通过特定的数据类型或数据结构，以多种方式和多种编程语言来实现。