queue 队列

读完能做什么

• 能创建 queue，用 push 入队、front 和 back 看队首队尾、pop 出队。
• 能按“先来先处理”的顺序模拟排队叫号，并说出每一步之后队列里还剩哪些元素。
• 能解释 front() 和 pop() 的区别，知道空队列不能取队首。
• 能说出什么是容器适配器，以及为什么 queue 没有迭代器、不能从中间访问元素。

为什么需要它

排队是最常见的规则：先来的人先被服务。用数组也能模拟，但要自己维护两个下标：

int a[1005];
int head = 0, tail = 0;      // head 指向队首，tail 指向队尾后面一个位置

a[tail++] = 101;             // 入队
int first = a[head++];       // 出队：先取值，再让 head 后移

这段片段（省略了头文件和 main）没有语法错误，但有几个麻烦：数组长度写死了，head 和 tail 得自己记得更新，head 越写越大还会浪费前面空出来的位置。我们需要一个把这些细节都包好的工具，这就是 queue。

它是什么

一句话：queue 是先进先出的容器——元素只能从队尾加入，只能从队首取出。先进去的先出来，这就是“先来先处理”。

直观模型如下。下面的箭头只表示排队的先后顺序（从队首指向队尾），不代表数据流动方向：新元素从右端的队尾加入，从最左端的队首离开。

graph LR
    h["101 队首 最早进来 最先离开"] --> m["102"] --> t["103 队尾 最后进来 最后离开"]

把队首放在左边、队尾放在右边，和程序里 队首 -> ... <- 队尾 的打印顺序、后面的操作表完全一致：

队列 101 102 103 中，front() 是 101，back() 是 103。执行 pop() 后 101 离开，队首变成 102；执行 push(104) 后 104 排在 103 后面，成为新的队尾。

容器适配器。 queue 自己没有重新实现存储，它拿一个现成的容器（默认是 deque，一种两端都能高效增删的容器）当底座，只把允许的操作重新包装一遍：push 就是往底座尾部加元素，pop 就是删掉底座头部的元素。所以它叫“适配器”——把底座的接口适配成队列需要的接口。代价是它只开放两端操作，你没法跳到队列中间去。

迭代器。 迭代器是“指向容器中某个位置的游标”：begin() 给出第一个元素的位置，end() 给出最后一个元素后面一个位置，两个位置一起表示一段区间。数组里我们用下标表示位置，迭代器是容器通用的位置表示法。queue 故意不提供 begin()、end()，因为队列只允许在两端操作——没有游标，也就没法从中间插队。

模板尖括号。 queue<int> 里的 <int> 表示队列里放什么类型的数据，queue<string> 就是存字符串的队列。

使用时要 #include <queue>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;              // 一个空的队列

    q.push(101);               // 从队尾进
    q.push(102);
    q.push(103);

    cout << "size = " << q.size() << '\n';
    cout << "front = " << q.front() << '\n';   // 队首（最早进来的）
    cout << "back = " << q.back() << '\n';     // 队尾（最后进来的）
    return 0;
}

输出：

size = 3
front = 101
back = 103

逐行看：

• queue<int> q; 创建一个空的整数队列，size() 是 0。
• 三次 push 依次把 101、102、103 放到队尾。101 最先来，所以它在队首。
• q.front() 读队首，得到 101；q.back() 读队尾，得到 103。
• front() 和 back() 只是“看”，不会把元素拿走，所以 size() 仍是 3。

一步步看变化

沿 101 102 103 这组数据走一遍。下表左端是队首，右端是队尾，与上面的图方向一致：

第 4 步的 pop() 没有指定元素，它删掉的永远是队首那一个。第 5 步之后队列空了，此时再调用 front() 是错的（见易错点）。

对应的完整程序：

#include <bits/stdc++.h>
using namespace std;

// 参数是副本：函数里弹出的是副本，不会改变调用者的队列
void printQueue(queue<int> q) {
    cout << "队首 -> ";
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << "<- 队尾\n";
}

int main() {
    queue<int> q;
    cout << "初始：";
    printQueue(q);
    cout << "size = " << q.size() << ", empty = " << q.empty() << '\n';

    q.push(101);
    q.push(102);
    q.push(103);
    cout << "入队 101 102 103 后：";
    printQueue(q);
    cout << "front = " << q.front() << ", back = " << q.back() << ", size = " << q.size() << '\n';

    q.pop();
    cout << "处理掉队首 101 后：";
    printQueue(q);
    cout << "front = " << q.front() << ", back = " << q.back() << ", size = " << q.size() << '\n';

    cout << "继续按顺序处理：";
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << '\n';
    cout << "全部处理完：size = " << q.size() << ", empty = " << q.empty() << '\n';
    return 0;
}

输出：

初始：队首 -> <- 队尾
size = 0, empty = 1
入队 101 102 103 后：队首 -> 101 102 103 <- 队尾
front = 101, back = 103, size = 3
处理掉队首 101 后：队首 -> 102 103 <- 队尾
front = 102, back = 103, size = 2
继续按顺序处理：102 103 
全部处理完：size = 0, empty = 1

几点说明：

• printQueue 的参数是按值传递，函数收到的是队列的一份副本。函数里 pop() 弹出的是副本的元素，调用者的队列一点没变——这一点从后面的 front、back、size 输出就能看出来。想让函数改到原队列，参数要写成引用 queue<int>& q。
• 想“看一眼队列里有什么”只能这样：不断取 front() 再 pop()。如果直接对原队列这么写，队列就被清空了，所以本页用副本打印。
• 输出第 1 行的 队首 -> <- 队尾 是空队列的样子：箭头之间什么都没有。

逐项扩展核心操作

出队顺序就是入队顺序

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(101);
    q.push(102);
    q.push(103);

    cout << "叫号顺序：";
    while (!q.empty()) {
        cout << q.front() << ' ';   // 先看队首
        q.pop();                    // 处理完，离开队首
    }
    cout << '\n';
    cout << "处理完后 size = " << q.size() << ", empty = " << q.empty() << '\n';
    return 0;
}

输出：

叫号顺序：101 102 103 
处理完后 size = 0, empty = 1

while (!q.empty()) 是处理队列的标准写法：只要还有人等着，就取出队首处理掉。因为每次取的都是队首，所以叫号顺序和入队顺序完全相同。把这段和“用栈”对比一下就很清楚：栈是最后进来的先出去，队列是先进来的先出去。

数据从输入进来

队列的数据常常是先读进来、再按顺序处理。下面读入 5 个数，按先进先出的顺序输出：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;                  // 数据个数

    queue<int> q;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }

    cout << "出队顺序：";
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << '\n';
    return 0;
}

输入：

5
3 1 4 1 5

输出：

出队顺序：3 1 4 1 5 

读入 3、1、4、1、5 依次入队，出队顺序一模一样：队列只改变“什么时候取”，不改变“取的顺序”。注意这里没有排序，也没有去重，重复的 1 会照样出队两次。

空队列不能取队首

// 错误示例：空队列既不能取队首，也不能弹出
#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;              // q 是空的

    cout << q.front() << '\n'; // 空队列没有队首，结果不确定
    q.pop();                   // 空队列也没有元素可删，结果不确定
    return 0;
}

这段不能运行出确定结果。空队列调用 front()、back()、pop() 都是未定义行为，程序可能打印出垃圾值，也可能崩溃。所以每次取队首之前先用 q.empty() 或 q.size() == 0 判断，就像上一节的 while (!q.empty()) 那样。

适配器没有迭代器

// 错误示例：queue 是容器适配器，不提供迭代器，下面这段不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(101);

    for (auto it = q.begin(); it != q.end(); it++) {   // queue 没有 begin()/end()
        cout << *it << '\n';
    }
    return 0;
}

这段不能通过编译：queue 没有 begin() 和 end()。这是适配器的设计意图——队列只允许在队首离开、在队尾加入，如果还能用游标跳到中间，队列的规则就被破坏了。需要遍历所有元素时，只能不断出队（像前面那样），或者改用 deque。

什么时候选它、哪里容易错

pop() 没有返回值。 它只负责删除，不告诉你删掉了谁。取值和删除要分两步：先 q.front() 拿到值，再 q.pop() 删掉。写成 int x = q.pop(); 会编译失败。

访问前先判空。 front()、back()、pop() 都要求队列非空，空队列上调用属于未定义行为，不能靠“它应该会给我 0”来猜。

没有下标，也没有迭代器。 q[0]、q.begin()、q.end() 都不存在。想看队列内容只能出队或打印副本。

打印副本不会改变原队列。 本页 printQueue(queue<int> q) 的写法会把整个队列复制一份，函数里怎么弹出都不影响调用者。反过来，如果参数写成 queue<int>& q，函数里就会真的把队列清空。

复杂度。 push、pop、front、back、empty、size 都是常数时间 O(1)。底层默认容器 deque 在两端增删的代价是摊还常数时间（“摊还”指偶尔一次重新分配比较贵，把开销平摊到很多次操作上，平均仍是常数）。

选读。 底层容器可以换：queue<int, list<int>> q; 表示用 list 当底座。默认的 deque 对队列这种“一头进一头出”的用法已经足够，本页不需要改动它。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

queue<int> q;
q.push(1);
q.push(2);
q.pop();                  // 1 处理完
q.push(3);
q.push(4);
q.pop();                  // 2 处理完

cout << q.front() << ' ' << q.back() << ' ' << q.size() << '\n';

第 2 题：修改代码

把上一节的叫号程序改成读入 n 个号码，处理完所有号码后输出“最后一个被处理的号码”和“队列是否为空”：

输入：

4
11 12 13 14

输出：

最后一个被处理：14
队列是否为空：1

验证条件：先说出循环结束时队列里还剩什么，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.pop();                   // 1 处理完
    q.push(3);
    q.push(4);
    q.pop();                   // 2 处理完

    cout << q.front() << ' ' << q.back() << ' ' << q.size() << '\n';
    return 0;
}

3 4 2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    queue<int> q;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }

    int last = -1;             // 记录最后一个被处理的号码
    while (!q.empty()) {
        last = q.front();
        q.pop();
    }

    cout << "最后一个被处理：" << last << '\n';
    cout << "队列是否为空：" << q.empty() << '\n';
    return 0;
}

4
11 12 13 14

最后一个被处理：14
队列是否为空：1

立即练习

两道题都只需要数组、循环和本页讲过的队列操作。做完后请说明：为什么这里用队列而不是用栈？如果换成栈，输出的顺序会变成什么样？