数据结构实现 1.3：数组队列（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序实现

• 2.1 入队操作

• 2.2 出队操作

• 2.3 查找操作

• 2.4 其他操作

• 3. 算法复杂度分析

• 3.1 入队操作

• 3.2 出队操作

• 3.3 查找操作

• 4. 完整代码

1. 概念及基本框架

队列 可以看做一种特殊的 数组 ，所以我使用第一节实现的 动态数组 来实现队列这种数据结构。当然，队列也可以通过其他方式来实现。因为该队列是通过动态数组实现的，所以称之为 数组队列 。

队列的结构如上图所示，可知队列的基本特性如下：
1.队列 有 队头 和 队尾 两端。
2.入队 操作只能从 队尾 进行，出队 操作只能从 队头 进行。
3.先 入队 的先 出队 ，即 先进先出（First In First Out），FIFO 。
还有一个隐含特性，队列可以自行 扩容（缩容），而不需要用户关心，很显然，动态数组已经满足了这个要求。
由此可见，队列的操作并不多，我使用了一个由 纯虚函数 构成的 抽象类 作为一个接口来定义这些操作。具体代码如下：

下面只需要通过继承 抽象类，并且重写 纯虚函数 ，就可以完成 数组队列 的实现。数组队列类的框架如下：

这个类内部定义一个动态数组类对象，为了保护数据，把它放在 private 部分，构造函数 ArrayQueue 底层调用的就是 Array 的构造函数。用户在构造函数中也可以指定队列的大小。（默认是10）为了兼容更多类型，这里使用了泛型的概念。

2. 基本操作程序实现

2.1 入队操作

入队操作使用了动态数组的增加第一个元素的操作来实现。这里动态数组内部已经提供了扩容操作。

2.2 出队操作

出队操作使用了动态数组的删除第一个元素的操作来实现。这里动态数组内部已经提供了缩容操作。

2.3 查找操作

因为队列只能获得队首元素，所以这里的查找操作也非常简单。

2.4 其他操作

3. 算法复杂度分析

3.1 入队操作

最坏复杂度 O(1+n) 中第一个 1 是指元素移动操作，第二个 n 是指动态数组中的 resize 函数，以下同理。
入队可能会引发扩容操作，平均而言，每增加 n 个元素，会扩展一次，会发生 n 个元素的移动，所以平均下来是 O(1) 。

3.2 出队操作

3.3 查找操作

总体情况：

由此可以看出，队列操作的增、查都是 O(1) 级别的时间复杂度，而删是 O(n) 级别的时间复杂度，因为每次出队的都是队首元素，后面的元素需要一个个向前移动。
注：队列并不提供改的操作。

4. 完整代码

动态数组类 代码：

抽象类 接口代码：

数组队列 代码：