先进先出（FIFO）的容器适配器——就像排队买东西，先来的人先被服务，只能从队尾进、从队首出。
queue（队列）是一种先进先出（FIFO，First In First Out）的数据结构，就像排队买东西——先来的人先被服务。它和 stack 一样是容器适配器，底层默认用 deque 实现。使用前需引入 <queue> 头文件。
stack 一样：queue 没有迭代器，不能遍历。要访问元素只能通过 front() 取队首，然后 pop() 弹出。| 1 | #include <iostream> |
| 2 | #include <queue> // 必须包含这个头文件 |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | queue<int> q1; // 空队列 |
| 8 | queue<int> q2(q1); // 拷贝另一个队列 |
| 9 | return 0; |
| 10 | } |
| 1 | queue<int> q; |
| 2 | q.push(1); // 入队：[1] |
| 3 | q.push(2); // 入队：[1, 2] |
| 4 | q.push(3); // 入队：[1, 2, 3] |
| 5 | |
| 6 | cout << q.front() << endl; // 输出：1——队首元素 |
| 7 | cout << q.back() << endl; // 输出：3——队尾元素 |
| 8 | |
| 9 | q.pop(); // 队首出队：[2, 3] |
| 10 | |
| 11 | cout << q.size() << endl; // 输出：2 |
| 12 | cout << q.empty() << endl; // 输出：0（false） |
| 13 | |
| 14 | // 逐个出队 |
| 15 | while (!q.empty()) |
| 16 | { |
| 17 | cout << q.front() << " "; // 输出：2 3 |
| 18 | q.pop(); |
| 19 | } |
queue 比 stack 多了一个 back()，因为队列两端都有意义——front() 看即将出队的元素，back() 看刚刚入队的元素。但和 stack 一样，pop() 仍然不返回值，要拿值得先用 front()。| 1 | #include <iostream> |
| 2 | #include <queue> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | queue<int> q; |
| 8 | |
| 9 | // 模拟排队：依次入队 |
| 10 | q.push(1); |
| 11 | q.push(2); |
| 12 | q.push(3); |
| 13 | |
| 14 | cout << "队首: " << q.front() << endl; // 输出：1 |
| 15 | cout << "队尾: " << q.back() << endl; // 输出：3 |
| 16 | |
| 17 | // 依次出队（先进先出） |
| 18 | cout << "依次出队: "; |
| 19 | while (!q.empty()) |
| 20 | { |
| 21 | cout << q.front() << " "; // 输出：1 2 3 |
| 22 | q.pop(); |
| 23 | } |
| 24 | cout << endl; |
| 25 | |
| 26 | return 0; |
| 27 | } |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用。
| 方法 | 分类 | 作用 |
|---|---|---|
| q.push(x) | 修改 | 从队尾插入元素 |
| q.pop() | 修改 | 从队首删除元素，不返回值 |
| q.front() | 访问 | 读取队首元素（即将出队） |
| q.back() | 访问 | 读取队尾元素（刚刚入队） |
| q.size() / q.empty() | 容量 | 元素个数 / 判断是否为空 |
| q1.swap(q2) | 修改 | 交换两个队列的全部内容 |
queue 的典型用法。