数据结构实现 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类代码：

抽象类接口代码：

链表队列代码：

标签：