2.2　抽象数据类型

通常来说，抽象是一个概念，用来定义复杂系统中常见的核心功能。利用这个概念来创建通用的数据结构，就产生了抽象数据类型（ADT）。通过隐藏实现层上的细节，给用户提供一个通用的、与实现无关的数据结构，抽象数据类型将使得算法的代码更加简洁和清晰。抽象数据类型可以使用任何编程语言进行实现，如C++、Java和Scala。在此，我们使用Python实现抽象数据类型，先从向量（vector）开始。

2.2.1　向量

向量是一种存储数据的单维结构，这是Python中最流行的数据结构之一。在Python中创建向量有以下两种方法：

• 使用Python列表：创建向量的最简单方法是使用Python的列表，如下所示：

这段代码创建了一个有四个元素的列表。

• 使用numpy数组：另一种流行的创建向量的方法是使用NumPy的array函数，如下所示：

注意，在这段代码中我们使用np.array创建了名为myVector的向量。

2.2.2　栈

栈是一种用于存储一维列表的线性数据结构。它可以通过后进先出（LIFO）或先进后出（FILO）的方式存储各项元素。栈所定义的特征是元素的添加和删除方式，新来的元素会被添加在栈的一端，如果要删除一个元素，也只能从该端进行。

以下是与栈有关的操作：

• isEmpty：如果栈为空，则返回true。
• push：添加一个新的元素。
• pop：返回最近添加的元素，并将其从栈中删除。

图2-4展示了如何使用push和pop操作分别在栈中添加和删除数据。

图2-4的上半部分展示了如何使用push操作向栈中添加元素，在步骤1.1、步骤1.2和步骤1.3中，分别使用了三次push操作向栈中添加了三个元素。图2-4的下半部分展示了从栈中取出所存储的值，在步骤2.2和步骤2.3中，pop操作以LIFO方式从栈中取出了两个元素。

下面我们在Python中创建一个名为Stack的类，并在这里定义所有与栈相关的操作。这个类的代码如下：

要将四个元素压入栈中，可以使用如图2-5所示的代码。

注意，图2-5的代码创建了一个有四个数据元素的栈。

栈的时间复杂度

我们看看栈的时间复杂度（使用大O记号）：

需要注意的是，上表中提到的四种操作，其性能都不取决于栈的规模。

实例

在很多用例中，栈都被当作数据结构来使用。例如，当用户想在Web浏览器中浏览所有历史记录时，这是一种LIFO数据访问模式，可以使用栈来存储历史记录。另一个例子是当用户想在文字处理软件中进行Undo操作时，也可以使用栈来存储历史记录。

2.2.3　队列

同栈一样，队列也用一维结构来存储n个元素，元素是以先进先出的形式进行添加和删除的。队列的一端称为队尾（rear），另一端称为队首（front）。当元素从队首被移出时，这种操作称为出队（dequeue）。当在队尾添加元素时，这种操作称为入队（enqueue）。

图2-6的上半部分展示了入队操作。步骤1.1、步骤1.2、步骤1.3为队列添加了三个元素，最后得到的队列如步骤1.4所示。此时，Yellow为队尾，Red为队首。

图2-6的下半部分展示了出队操作。步骤2.2、步骤2.3和步骤2.4从队列的队首逐一移出队列中的元素。

图2-6所展示的队列可以使用如下代码来实现：

我们在图2-7的帮助下，理解图2-6所展示的元素的入队和出队操作。

在图2-7中，前一部分的代码（[2]～[6]）先创建一个队列，然后将四个元素分别加入队列。

2.2.4　栈和队列背后的基本思想

我们通过类比来讨论栈和队列背后的基本思想。假设有一个桌子，用来存放从邮政服务收到的邮件，例如来自加拿大的邮件。我们将邮件堆叠起来，直到空闲时逐一打开并查看邮件。有两种可能的方法可以完成这个工作：

• 把信件叠成一堆，每当我们收到新的信，就把它放在邮件堆的最上面。当我们要读信时，就从最上面的那封信开始读，这里的信件堆就是我们所说的栈。需要注意的是，最新到达的信件总会在最上面，并且会优先被处理。从信件列表顶部取信称为pop操作，每当新的信件到达时，将其放在列表顶部的操作称为push操作。如果我们最终有一个相当大的信件堆，并且不断有大量的信件到达，则可能永远没有机会处理在信件堆的底端的非常重要的信件。
• 把信件叠成一堆，但要先处理最早的信件：每次要阅读信件时，都要先处理最早到达的那封信，这就是我们所说的队列。将一封信件添加到信件堆中称为入队操作，从信件堆中移除信件称为出队操作。

2.2.5　树

在算法的背景中，树是非常有用的数据结构之一，因为它具有层次化的数据存储能力。在设计算法时，我们使用树来表示需要存储或处理的数据元素之间的层次关系。

我们深入了解一下这个有趣且相当重要的数据结构。

每棵树都有有限个节点，起始数据元素对应的节点称为根节点（root），所有节点通过链接关系组织在一起，链接也称为分支（branch）。

术语

我们来看看与树这种数据结构相关的一些术语：

树的类型

树有不同的类型，下面分别进行解释：

• 二叉树：如果一棵树的度是2，那么这棵树称为二叉树。例如，图2-8所展示的树就是一棵二叉树，因为它的度是2。

图2-8所展示的是一棵有4层和8个节点的树。

• 满树：满树是指所有非叶节点的度都相同的树，这个值就是树的度。图2-9展示了前面讨论的树的类型。

请注意，最左边的二叉树不是满树，因为节点C的度是1，其他节点的度都是2。中间的树和右边的树都是满树。

• 完美树：完美树是一种特殊类型的满树，其中所有的叶节点都位于同一层。例如，图2-9中右侧的二叉树就是一棵完美的满树，因为所有的叶节点都在同一层，即第2层。
• 有序树：如果一个节点的子节点按照特定的标准以某种顺序排列，则称为有序树。例如，一棵树可以从左到右按升序排列，其中同一层的节点在从左到右遍历时，其值会递增。

实例

树这种抽象数据类型是开发决策树的主要数据结构之一，这一点将在第7章中讨论。由于树的层次结构，它在网络分析的相关算法中也很受欢迎，这一点将在第6章中详细讨论。树也用于各种需要实现分治策略的查找和排序算法中。