多态性。多态性是指在一般类型中定义的数据或行为被特殊类型继承后，具有不同的数据类型或呈现出不同的行为。例如，“苹果”是“水果”的子类，它可以有“水果”的一般“吃”法，但其本身还可以有别的多种“吃法”。

注：“抽象”的意义在于数据类型的数学特性，其数学特性和具体的计算机或语言无关。

在编程语言（或库）和教科书中，常见的几个抽象数据类型如下：

关联数组用字符串代替数字来索引数组中的元素。可以认为索引字符串是用来寻找元素的关键字。在Perl中,利用在数组名前加前缀百分号(%)来定义一个关联数组。被赋值的值列表由索引字符串对和元素值组成。索引字符串后跟随元素值，元素值后面跟下个索引字符串和元素值，以此类推。

定义如下：

ADT complex{

数据对象：D={real, image | real∈实数, image∈实数}

数据关系：R={}

基本操作：

}ADT Complex

容器类是容纳、包含一组对象或对象集的对象。与一个盒子中放置一套书和一个书包中放入一些铅笔相似的方式，容器类包含一组对象或一个对象集。容器类作为通用对象收集器( generic holder)。C++语言的容器类中可以包含混合的对象。即容器类可以包含组不同类型的对象或一组相同类型的对象。

当容器类包含不同类型的对象时，称为异类容器类( heterogenous container)当容器类包含相同类型的对象时，称为同类容器类(homogenous container)。容器类的名称源于它的功能，如果我们使用容器类来存储对象或从容器类中检索对象，我们可以由此知道应该对存储在容器类中的对象或与容器类相关联的对象作哪些操作输入一些数据到计算机或输出一些数据到与计算机连接的设备是最通常的操作，除此之外，设计程序时最常进行的操作包括:查询、排序、添加、检索、存储数据。

实际上，命令计算机执行这些数据控制操作被认为计算机程序设计定义固有的内容。C++语言的容器类用于帮助创建这些基本的操作对数据的排序、查询、添加、删除、存储以及其他的一些操作通常需要预先定义特定的数据类型和数据结构。在非面向对象的程序设计语言中，例如C语言、Fortran语言、Pascal语言和Cobol语言，计算机程序分为数据类型、数据结构以及按照这些数据结构完成的操作和算法。

双端队列是一种插入和删除工作在两端都可进行的线性表。可以把双端队列看成是底元素连在一起的两个栈。它们与两个栈共享存储空间不同的是，两个栈的栈顶指针是两边延伸的。

由于双端队列允许在两端进行插入删除工作，因此需要建立两个指针，分别指向双端队列中两端的元素。允许在一端进行插入和删除，另一端只允许插入的双端队列称为输出受限双端队列;允许在一端进行插入和删除，而另一端只允许删除的双端队列称为输入受限双端队列。

列表是一个特别灵活的结构，因为它可以根据要求而增长和收缩而且其中任何位置都可被访问，可以插入和删去元素。几个列表可以连接在一起以形成更大的列表，也可以把一个列表分开成若干个子列表。在诸如信息查寻，程序设计翻译及模拟等应用中都会使用列表，在一些存储管理技术中也广泛地使用列表处理。从数学上说，列表就是一个给定类型的零个或多个元素的序列。

即多重映像容器，与一般映像map不同的是，多重映像multimap中允许出现相同的键值。多重映像容器中，没重载下标运算符“[ ]”本容器的成员函数成员函数与一般映像map相类似。

优先队列( Priority Queue)是一种抽象数据类型( Abstract Data Type)，可以把它看成种容器，里面有一些元素，这些元素称为队列的结点(Node)。优先队列的结点至少要包含一种性质：有序性，也就是说任意两个结点可以比较大小。为了具体起见，我们假设这些结点中都包含一个键值(Key)，结点的大小通过比较它们的键值而定。优先队列并不是按照入队的顺序简单地执行先进先出( First in first out )，而是按照一定的优先级(键值的大小)调用。优先队列最早出现在操作系统中，实现对任务或进程的调度。

优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等类型的题目中都有着广泛的应用。优先队列有三种基本操作：插入结点( Insert )、取最小结点( Get Min )和删除最小结点( Delete min )。优先队列有着多种具体实现方法，不同实现方法的三种基本操作的时间复杂度也有很大的区别。比如，采用一维数组或线性链表实现，插入结点的时间复杂度只需要O(1)，但取最小结点和删除最小结点的时间复杂度为O(n)；采用二叉排序树实现，三种基本操作的时间复杂度都为O(log2n)，但二又排序树可能退化成线性表。

队列( Queue)是只允许在一端进行插入操作，而在另外一端进行删除操作的线性表。只允许插入的一端称为队尾rea，只允许删除的一端称为队头front)°。事实上，在队列中，这两种操作已经不再称为“插入”和“删除”，而是称为“入队”和“出队”。

队列是一种先进先出( First-In First-Out，FIFO)的结构，具有很强的顺序特征。队列会记录下零散无序的数据进入队列的顺序，并且在出队的时候保持这个顺序，以方便程序算对其进行利用。

队列中不允许对除了队头和队尾之外的其他元素进行任何形式的操作。这种限制使得队列虽然名义上是一种线性表，但是它已经几乎丧失了线性表的所有特点，无法对其进行线性表的大部分操作。

队列就像一个管道一样，将位于管道中间的数据保护起来，只留下管道的两端可供程序员进行操作。

STACK，栈是一种特殊的表，这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。

堆栈的行为特征：假设一个栈S中的元素为an，an-1，,,, ,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a，a2，,,, ，an-1，an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出表，简称LIFO表。

ADT String

数据元素集合:

字符的一个有限序列。

基本操作：

树的抽象数据类型的定义如下:

ADT Tree {

(1)数据对象D：一个集合，该集合中的所有元素具有相同的特性。

(2)数据关系R：若D为空或D中仅含有一个数据元素，则R={ ∅ }，否则R={ H }，H关系如下：

a.在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。

b.除root以外，D中其余结点存在m(m≥0)个不相交的划分，每个划分都是一棵树，是根的子树。

(3)树的基本操作。

} ADT Tree

抽象数据类型是一个数学模型以及定义在其上的一组操作组成，因此，抽象数据类型一般通过数据对象、数据关系以及基本操作来定义，即抽象数据类型三要素是(D，R，P)。

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

} ADT抽象数据类型名

其中基本操作的定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

实现于程序时，抽象数据类型只显现出其接口，并将实现加以隐藏。用户只需关心它的接口，而不是如何实现。未来更可以改变实现的方式。（其支持信息隐藏原理，或保护程序免受变化的冲击。）

抽象数据类型的强处在于对用户隐藏了实现细节，仅公开其接口。这表示抽象数据类型可以用各种方法来实现，只要遵循其接口，就不会影响到用户。

在抽象数据类型和数据结构之间，有一个实现上的微妙差别。例如，列表的抽象数据类型可以数组为基础、或者使用链表来实现。列表即是一种具良好运算（加入元素、移除元素等等）定义的抽象数据类型。链表是以指针为基础的数据结构，且可用来创建一个列表。链表常用于列表的抽象数据类型。

同样地，二叉树搜索法的抽象数据结构可以几个方式实现：二叉树、AVL树、红黑树、数组等等。且无须关心其实现，二叉树搜索法总是有相同的运算（插入、移除、查找等等）。

从实现中分离出接口，并不表示用户不该知道实现的方法，而是用户不能依赖于实现细节。例如，一个抽象数据类型可以用脚本语言创建，或其它可以被反编译的语言（如C语言）。即使用户可发现实现的方法，只要所有客户端程序遵循该接口，且改变实现方式时不会产生影响，那就仍是抽象数据类型。

在面向对象的用语中，抽象数据类型相当于类别；抽象数据类型的实体就相当于对象。某些语言包含了用于宣告抽象数据类型的构造函数。例如，C++ 和 Java 为此提供了类的构造函数。

抽象数据结构即根据所要运算的数据以及其计算复杂性所定义的抽象存储区，而不关心具体的数据结构的实现。

就实现高效率的算法而言，对数据结构的选择相当重要。抽象数据结构的选择，决定了高效率的算法的设计，和估计其计算复杂性。

这个概念与编程语言理论中所使用的抽象数据类型非常接近，大致上抽象数据结构和抽象数据类型的名称，和具体的数据结构的名称一致。

一部分抽象数据类型在程序设计中相当普遍且实用，所以在某些编程语言中，成为原生类型、或加进标准库中。例如，Perl 的数组可以用列表或双端队列之类的抽象数据类型来实现，散列表也可以用 Map 或 Table 来做。C++ 标准库和 Java 库也提供了列表、堆栈、队列、Map、优先权队列和字符串。