队列

一、队列

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

数组模拟队列

通常用一个数组模拟一个队列，用两个变量标记队列的首尾。

int q[SIZE], ql = 1, qr, x; 
//队列操作对应的代码如下：
q[++qr] = x;        //插入元素
ql++;                //删除元素
x = q[ql];            //访问队首
x = q[qr];            //访问队尾
ql = 1; qr = 0;        //清空队列

STL中的队列

C++ 在 STL 中提供了一个容器 std::queue，使用前需要先引入 头文件。

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class queue;

T 为 queue 中要存储的数据类型。
Container 为用于存储元素的底层容器类型。这个容器必须提供通常语义的下列函数：

• back()
• front()
• push_back()
• pop_front()

STL 容器 std::deque 和 std::list 满足这些要求。如果不指定，则默认使用 std::deque 作为底层容器。
使用详情 -> STL标准模板库

二、双端队列¶

双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 4 个：

• 在队首插入一个元素
• 在队尾插入一个元素
• 在队首删除一个元素
• 在队尾删除一个元素

数组模拟双端队列的方式与普通队列相同。

C++ STL 中的双端队列

C++ 在 STL 中也提供了一个容器 std::deque，使用前需要先引入 头文件。
使用详情 -> STL标准模板库
头文件中还提供了优先队列 std::priority_queue，因其与 堆 更为相似，在此不作过多介绍。