4.1 队列和双端队列概述

4.1.1 队列和双端队列的定义

队列的示意图如图4.1所示，队列中保存一个数据序列[ a ₀ ， a ₁ ，…， a _{n -1} ]，共有两个端点，队头的一端（ a ₀ 端）用于删除（出队）元素，队尾的一端（ a _{n -1} 端）用于插入（进队）元素。队列元素遵循“先进先出”的原则，即最先进队的元素最先出队。注意，不能直接对队列中的元素进行顺序遍历。

在算法设计中，队列通常用于存储临时数据。在一般情况下，若先存储的元素先处理，则使用队列数据结构存储这些元素。 n 个不同的元素经过一个队列产生的出队序列只有一个，与进队的顺序相同。

双端队列与队列类似，两个端点分别称为前端和后端，不同之处是两端都可以做进队和出队操作，如图4.2所示。双端队列具有队列和栈的特性，因此使用更加灵活。

队列和双端队列都可以使用数组和链表存储结构实现。

4.1.2 队列和双端队列的知识点

1.C++中的队列和双端队列

在C++STL中提供了queue类模板，实现了队列的基本运算，而且在使用时不必考虑队满上溢出的情况，但不能顺序遍历队列中的元素。queue的主要成员函数如下。

·　empty（）：判断队列是否为空，当队列中没有元素时返回true，否则返回false。

·　size（）：返回队列中当前元素的个数。

·　front（）：返回队头元素。

·　back（）：返回队尾元素。

·　push（e）：将元素e进队。

·　pop（）：元素出队，只是删除队头元素，并不返回该元素。

例如，以下代码定义一个整数队列qu，依次进队1、2、3，再依次出队所有元素，出队结果是1，2，3。

C++：

在C++STL中还提供了deque类模板，实现了双端队列的基本运算。deque使用双向开口的连续线性空间，由若干缓冲区块构成，每个块中元素的地址是连续的，块之间的地址是不连续的，系统提供了一个维护其整体的机制。deque两端均能以常数时间插入和删除，支持随机元素访问和顺序遍历，其容量大小可以自动伸缩。deque的主要成员函数如下。

·　empty（）：判断双端队列是否为空，当队列中没有元素时返回true，否则返回false。

·　size（）：返回双端队列中当前元素的个数。

·　front（）：返回双端队列中前端的元素。

·　back（）：返回双端队列中后端的元素。

·　push_front（e）：在双端队列中的前端插入元素e。

·　push_back（e）：在双端队列中的后端插入元素e。

·　pop_front（）：删除双端队列的前端元素。

·　pop_back（）：删除双端队列的后端元素。

·　clear（）：删除双端队列中的所有元素。

·　begin（）：用于正向遍历，返回双端队列中首元素的位置。

·　end（）：用于正向遍历，返回双端队列中尾元素的后一个位置。

·　rbegin（）：用于反向遍历，返回双端队列中尾元素的位置。

·　rend（）：用于反向遍历，返回双端队列中首元素的前一个位置。

说明： 通过限制deque在一端插入元素、在另一端删除元素，则deque变为队列。通过限制deque在同一端插入和删除元素，则deque变为栈。由于deque可以顺序遍历元素，而stack和queue不能顺序遍历元素，所以在需要时用deque作为栈或者队列更方便进行算法设计。

2.Python中的队列和双端队列

在Python中没有直接提供队列，但提供了双端队列deque，可以使用deque作为队列或者栈。deque的主要操作如下。

·　dq，len（dq）==0：判断双端队列是否为空。

·　len（dq）：返回双端队列中当前元素的个数。

·　dq[0]：返回双端队列中左端（前端）的元素。

·　dq[-1]：返回双端队列中右端（后端）的元素。

·　dq.clear（）：清除双端队列中的所有元素。

·　dq.appendleft（x）：从双端队列的左端（前端）进队元素 x 。

·　dq.append（x）：从双端队列的右端（后端）进队元素 x 。

·　dq.popleft（）：从双端队列的左端（前端）出队元素。

·　dq.pop（）：从双端队列的右端（后端）出队元素。

3.单调队列

将一个从队头到队尾（或者前端到后端）的元素有序的队列称为单调队列，如果从队头到队尾的元素是递减的（队头元素最大），称之为单调递减队或者大头队，例如[5，2，1]是一个单调递减队；如果从队头到队尾的元素是递增的（队头元素最小），称之为单调递增队或者小头队，例如[1，3，4，5]（1是队头，5是队尾）是一个单调递增队。

单调队列的主要功能是寻找某个查找区间的最值（一个区间中的最大或者最小值），需要在两端出队元素，以维护其单调性，所以单调队列通常用双端队列实现。

这里以单调递增队（小头队）为例，其基本操作如下。

（1）获取最值：队头就是区间的最小值。

（2）元素 x 进队：将 x 和队尾元素比较，如果队尾元素大于 x ，则将队尾元素从队尾出队，重复此操作，直到队为空或者队尾元素小于 x 为止，再将 x 从队尾进队。

（3）过期处理：若队头超过当前窗口范围，即过期，则从队头出队该元素。

单调队列和单调栈类似，不同之处是单调队列从队尾进队，把违反单调性的元素从队尾出队，将过期元素从队头出队；而单调栈是从栈顶进栈，把违反单调性的元素从栈顶出栈，不会过滤过期元素。 wV8vLrukD0xSqqrkvYwn92tBUnkpnADWv/dHv4ah9SyPjAMC9GTX+8ngRK0U0iim