4.2.4. 队列：C++实现、STL容器

本节介绍如果自己编程实现链式队列，并介绍STL库提供的两种队列容器：队列 queue 和有点奇怪的双头队列 deque。事实上，deque 与其说是一种队列的变种，更不如说是向量 vector 的一种变种。至于优先级队列容器 priority_queue，我们留到以后讲解完堆这种高级数据结构之后再做介绍。

4.2.4.1. 链式队列的实现

我们用C++语言实现一个标准意义上的队列，采用链式存储结构，支持模板类型，用编程管理来模拟封装。根据前面的介绍，我们应该把数据节点、底层单链表和具体的成员变量都隐蔽起来，对外只提供以下功能接口：

  1. 创建一个新队列，初始为空队列。

  2. 元素入队。

  3. 访问队头元素。

  4. 队头元素出队。

  5. 判断队列是否为空。

  6. 获取队列长度。

所以我们只要模仿以前实现过的单链表代码就可以很方便地实现这样一个链式队列，而且由于队列的访问限制，我们甚至不需要提供指示器之类的元素定位访问能力。如果有点忘记了，可以回顾一下这里：链表的C++实现。

所有操作的原理我们在上一节已经介绍过了，这里先直接给出代码再进行说明。

template<typename T>
struct LinkedQueue {
	struct _Node {		// 元素节点的结构，嵌套在队列结构内部
		T _val;		// 元素值
		_Node *_next;	// 后继指针

		_Node() { _next = NULL; }	// 构造一个新的节点，后继为空
	};

	_Node *_head, *_tail;	// 头尾指针，注意可以省略命名限定 LinkedQueue<T>::
	int _size;		// 队列长度

	LinkedQueue()		// 构造一个新的空队列
	{
		_tail = new _Node;
		_head = _tail;
		_size = 0;
	}
	bool empty() const { return _head == _tail; }	// 判断队列是否为空
	int size() const { return _size; }	// 获取队列长度
	void enqueue(const T &val)		// 元素val入队
	{
		_tail->_val = val;
		_tail->_next = new _Node;
		_tail = _tail->_next;
		++_size;
	}
	T &head()				// 访问队头元素
	{
		if (_head == _tail) throw *this;
		return _head->_val;
	}
	void dequeue()				// 队头元素出队
	{
		if (_head == _tail) return;
		_Node *temp = _head;
		_head = temp->_next;
		delete temp;
		--_size;
	}
	~LinkedQueue()		// 析构函数，删除队列，销毁当前队列中所有节点
	{
		while (_head != _tail) dequeue();
		delete _tail;
	}
};

注解

相信真正理解了上一节介绍的链式队列原理之后是很容易看懂上面这段代码的，这里做一些简单说明：

  1. 节点结构 _Node 是队列结构 LinkedQueue 的内部结构，如我们在介绍链表的C++实现时所给出的代码，这个节点结构的全名应该在前面加上其父结构名称的命名修饰，即 LinkedQueue<T>::_Node。但是由于我们所有用到这个节点结构的代码都是定义在外部结构 LinkedQueue<T> 内的，也就是说是在 _Node 的命名空间内，所以我们实际上可以在代码中省略命名修饰。

  2. 元素入队时，我们先将队尾指针所指向的空节点的元素值赋为要入队的元素值，这样这个空节点就变成了一个有效的元素节点，它是队列实际上的尾节点。然后我们要生成一个新节点作为它的后继，这个新节点就是新的队尾指针指向的空节点。最后别忘了修正队列长度。

  3. 元素出队时，我们把队头指针改成它的后继，然后销毁原队头指针指向的队头元素节点即可，同样别忘了修正队列长度。

  4. 元素出队和访问队头元素两个操作，都有可能遇到空队列的情况，对于空队列进行这样的操作就会引发错误操作或者让获得的结果不确定。所以我们在这两个操作中都做了预判处理，但是二者处理预判的方式不一样，这里有什么不同，又是什么原因，请自行弄懂。

  5. 最后别忘了，凡是用到动态内存的结构，都需要有一个析构函数以便清除掉所有占用的空间。

练习

模仿上面的代码，编写一个具体类型的链式队列结构并编写 main() 函数进行测试，要求如下：

  1. 元素类型为 int。

  2. 不提供 head() 函数以访问队头元素，而是在元素出队的时候同时返回被出队元素的值。

  3. 甚至可以不采用封装惯例形式。

4.2.4.2. STL队列容器

C++的STL库当然也提供了队列容器，叫做 queue。和所有STL容器一样，要使用它就要先引入库 queue 并使用标准命名空间 std。

queue 容器的使用非常简单，首先它同样具备所有STL容器都支持的以下几个常规功能：

  1. 构造函数，用于定义出一个新的空队列。

  2. 成员函数 empty() 用于判断队列是否为空。

  3. 成员函数 size() 用于获取队列长度。

  4. 支持六种比较运算，比较两个队列的字典序先后。

此外是队列的特殊操作：入队、出队、访问队头元素，而 queue 容器还额外提供了一个访问队尾元素的功能，这是标准的队列所没有的操作。注意，queue 的队头、队尾元素访问都是以引用的方式来返回元素的，可以直接修改函数返回值从而实现修改队头、队尾元素，这也是标准的队列所不具备的能力。另外，可能是出于STL容器名称一致性的考虑，queue 的成员函数命名并没有采用标准的数据结构惯用名称。

  1. 成员函数 push() 用于元素入队，该函数接收一个参数，即要入队的元素，没有返回值。

  2. 成员函数 pop() 用于元素出队，该函数没有参数，也没有返回值，只是单纯地将当前队头元素删除。

  3. 成员函数 front() 用于访问队头元素，该函数没有参数，返回队头元素的引用，并不删除该元素，因此可用于直接修改队头元素。

  4. 成员函数 back() 用于访问队尾元素，该函数没有参数，返回队尾元素的引用，并不删除该元素，因此可用于直接修改队尾元素。

例如：

#include <queue>
#include <iostream>

using namespace std;

int main()
{
        queue<int> q;        // 定义一个新的空队列q，元素类型为int
        q.push(100);         // 入队一个元素100
        for (int i = 1; i <= 10; ++i) {
                q.push(i);
                q.front() -= q.back();
        }
        while (!q.empty()) {
                cout << q.front() << endl;
                q.pop();
        }

        return 0;
}

练习

不运行直接写出上面这段小程序的输出。

4.2.4.3. STL双头队列容器

STL库还提供了一个非常独特的队列容器：双头队列（deque），这个英文单词读作deck。虽然它的名称听起来是队列，但是实际上它更接近于顺序表。

引入 deque 库，使用 std 命名空间，然后就可以使用 deque 容器了。它拥有和顺序表容器 vector 几乎一模一样的使用方法，只是它支持常数时间效率的表头元素增删操作。

我们知道，向量 vector 是一种标准的顺序表数据结构，可以看作是一个动态长度的数组。由于顺序表的特性，在头部位置，即下标为0的位置增加或删除元素会导致表中所有现有元素的搬移，所以效率很低，是 \(O(n)\) 时间的操作。但是 deque 容器则不同，它支持 \(O(1)\) 时间效率的头部元素增删操作。因此它比 vector 多这样两个成员函数：

1、在头部插入一个元素：

void push_front(const value_type& val);

这个函数接收一个参数，即要在头部插入的元素，以常数时间将其插入在队头位置上。它没有返回值。

2、删除头部元素：

void pop_back();

这个函数将队头元素删除，没有参数，也没有返回值。

除了上述两个函数以外，deque 容器的所有其他功能和 vector 几乎完全一样，有几乎完全一致的成员函数，也可以使用迭代器来访问元素，甚至可以用方括号加下标形式来访问队列中任意位置的元素。所以与其说 deque 是一种队列，不如说它更加是一个顺序表比较合适。

练习

vector 容器和 deque 容器的对比实验：

  1. 分别随机生成106个 int 型数用来填充一个 vector 和一个 deque，均从头部插入，记录和对比整个过程二者的运行时间。（提示：vector 使用 insert() 成员函数，deque 使用 push_front() 成员函数）。

  2. 使用STL算法库的 sort() 函数分别对上述的 vector 和 deque 进行排序，记录并对比二者的运行时间。

  3. 从头部位置逐个删除元素直到清空，记录并对比二者的运行时间。

  4. 分别用105个和104个 int 型数的数据量再次做上述对比实验，对比观察随着数据量的倍增带来的运行时间增长规律。

通过上述三个不同数据量的对比实验得到的九组运行时间数据，你能得出怎样的结论？

队列是一种非常重要的数据结构，它广泛应用在进程间通信、操作系统、编译系统、网络通讯等各种领域，在算法编程中也有极为广泛的应用，它是宽度优先搜索的基础数据结构。今后在讲述高级数据结构和算法的时候我们会看到许多队列结构的应用。