C++ queue队列的用法（附带实例）

队列（queue）是一种遵循先进先出（First In First Out，FIFO）原则的数据结构，允许元素按照被添加的顺序进行移除。

队列有两个主要的操作接口（入队和出队），此外还提供了一些辅助方法，如访问队列首尾元素、获取队列长度以及检查队列是否为空。

利用 C++ 的标准模板库（STL），可以便捷地实现和使用队列。

C++ queue队列的结构

队列属于线性数据结构的一种，可以视为一种“功能受限”的数组。虽然数组可以完成队列的所有操作，但队列有其特定限制：仅允许从队尾添加元素和从队头移除元素。

这种限制赋予了队列一些独特的优势，尤其在广度优先搜索（BFS）中，队列确保了结点按照特定顺序被遍历，如下图所示。

C++ queue队列的初始化

在使用队列之前，需要引入相应的头文件。如果已包含万能头文件（如 <bits/stdc++.h>），则无须单独引入队列头文件。

#include <queue>
// #include <bits/stdc++.h>        // 万能头文件中包含队列头文件
using namespace std;               // 队列在std命名空间中

可以声明一个队列，其中 T 代表数据类型（如int、double、char 等基本数据类型，或用户自定义的结构体或类）。需要注意的是，一个队列中的所有元素必须具有相同的数据类型。

通常情况下，我们只需要声明一个空队列，然后向其中添加元素。以下是两种声明队列的方式：

queue<T> q;       // 声明一个通用类型的队列，其中T为数据类型
queue<int> qint;  // 声明一个内部元素为int的队列

C++ queue队列的基本操作

C++ 中的 <queue> 头文件提供了 queue 类，用于实现队列的基本操作。下表列举了常用的队列操作方法及其时间复杂度。

方法	作用	时间复杂度
push(x)	将元素 x 从队尾推入	O(1)
pop()	将队头元素弹出，但不返回该元素	O(1)
size()	返回队列的大小，即队列中的元素个数	O(1)
empty()	返回队列是否为空；若为空返回 true，否则返回 false	O(1)
front()	返回队头元素，但不删除该元素	O(1)
back()	返回队尾元素	O(1)

需要注意的是，队列没有类似向量中的 clear() 方法用于直接清空整个队列。如果想要清空队列，可以使用以下两种方法之一。

1) 逐个判断队头元素并清空：

queue<int> q;               // 声明一个整数类型的队列
for (int i = 1; i <= 5; ++i)
    q.push(i);              // 向队列中添加一些数据

while (!q.empty())
    q.pop();                // 弹出队头元素直到队列为空

cout << q.empty() << '\n';  // 运行结果：输出 1（表示 true，队列为空）

2) 重新赋值为空队列：

queue<int> q;               // 声明一个整数类型的队列
for (int i = 1; i <= 5; ++i)
    q.push(i);              // 向队列中添加一些数据

q = queue<int>();           // 重新赋值一个空队列给 q
cout << q.empty() << '\n';  // 运行结果：输出 1（表示 true，队列为空）

在广度优先搜索中，我们会用到队列这种数据结构。