数据结构实现 2.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 。
因为链表对链表末端操作时间复杂度较大，所以添加了一个 tail 指针，使得原来 O(n) 的时间复杂度变成了 O(1) 级别的。由于 tail 指针的加入，而且我们的操作也只针对 head 和 tail ，所以可以去掉虚拟头结点，因此我们需要从底层来重新构建这个类。
与数组队列类似，可以利用一个由 纯虚函数 构成的 抽象类 作为一个接口来定义这些操作。具体代码如下：

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

其中的 Node 类是第五节链表中定义的一个类，这里不再重复定义，直接使用，Node 类的定义如下：

LinkedListQueue 类内部定义头指针、尾指针以及链表长度，为了保护数据，把变量都放在 private 部分，为了兼容更多类型，这里使用了泛型的概念。

2. 基本操作程序实现

2.1 入队操作

由于使用了尾指针，入队操作十分方便。但是要注意，当链表为空时的特殊情况。

2.2 出队操作

2.3 查找操作

队列只能获得队首元素。

2.4 其他操作

3. 算法复杂度分析

3.1 入队操作

3.2 出队操作

3.3 查找操作

总体情况：

由此可以看出，链表队列操作的增、删、查都是 O(1) 级别的时间复杂度。

注：队列并不提供改的操作。

4. 完整代码

Node类 代码：

抽象类 接口代码：

链表队列 代码：