std::queue 详解：队列适配器的实现、底层容器选择、应用场景
队列这东西，说白了就是「先进先出」——你排过队吧？先来的人先服务。在 C++ 里，std::queue 就是帮我们干这个的。我最早接触它是在写一个简单的任务调度器时，那时候还自己手写数组模拟队列，后来才发现 STL 早就给你准备好了。
队列适配器是什么？
std::queue 不是一个独立的容器，它是一个适配器。什么意思呢？它底层不自己存数据，而是包装了另一个容器（比如 deque 或 list），只对外暴露队列的接口——push、pop、front、back。你想想看，这就像给一个普通容器穿了一件「队列马甲」，只让你从一头进、另一头出。
- 先进先出（FIFO）
- 不能遍历，只能访问队头和队尾
- 底层容器可替换，但必须支持
front()、back()、push_back()、pop_front()
底层容器选择
默认情况下，std::queue 使用 std::deque 作为底层容器。为什么是 deque？因为 deque 既支持 push_back，又支持 pop_front，而且效率都不错。我个人习惯在大多数场景下直接用默认的 deque，省心。
但你也可以换成 std::list。什么时候用 list？我记得有一次我在做一个内存敏感的项目，deque 的块状分配策略导致内存碎片有点多，换成 list 后问题就缓解了。不过 list 的缺点是每个元素都有额外指针开销，而且缓存局部性不如 deque。
| 底层容器 | 优点 | 缺点 | 推荐场景 |
|---|---|---|---|
| std::deque（默认） | 随机访问快，内存连续性好 | 内存块管理略复杂 | 通用场景，绝大多数情况 |
| std::list | 插入删除无内存重分配 | 额外指针开销，缓存不友好 | 元素大、频繁插入删除 |
基本用法
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
std::cout << "队头: " << q.front() << "\n"; // 10
std::cout << "队尾: " << q.back() << "\n"; // 30
q.pop(); // 移除队头
std::cout << "弹出后队头: " << q.front() << "\n"; // 20
std::cout << "队列大小: " << q.size() << "\n";
std::cout << "是否为空: " << q.empty() << "\n";
return 0;
}嗯，这里要注意：pop() 不会返回被移除的元素。如果你想拿到队头再移除，得先 front() 再 pop()。我曾经在代码 review 时看到有人写 int val = q.pop();，编译不过还一脸懵——记住，pop 是 void 的。
应用场景一：BFS（广度优先搜索）
BFS 是队列最经典的应用，没有之一。你想想看，BFS 的流程就是一层一层往外扩，先访问的节点先处理它的邻居——这不就是队列的 FIFO 特性吗？
#include <queue>
#include <vector>
#include <iostream>
void bfs(int start, const std::vector<std::vector<int>>& graph) {
std::queue<int> q;
std::vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
std::cout << "访问节点: " << node << "\n";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}我在项目中用 BFS 做过一个简单的社交关系推荐系统——从某个用户出发，找他的朋友、朋友的朋友，一层层往外推。队列在这里就是核心数据结构，没有它，BFS 根本没法写。
应用场景二：任务调度
另一个常见场景是任务调度。比如你有一个生产者线程不断产生任务，一个消费者线程不断处理任务。队列就是它们之间的缓冲区。
#include <queue>
#include <mutex>
#include <condition_variable>
std::queue<int> task_queue;
std::mutex mtx;
std::condition_variable cv;
void producer() {
for (int i = 0; i < 100; ++i) {
std::lock_guard<std::mutex> lock(mtx);
task_queue.push(i);
cv.notify_one(); // 通知消费者
}
}
void consumer() {
while (true) {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, []{ return !task_queue.empty(); });
int task = task_queue.front();
task_queue.pop();
lock.unlock();
// 处理任务...
}
}队列的局限性
说实话，std::queue 的功能非常有限。你不能遍历，不能随机访问，甚至不能清空（得一个个 pop）。如果你需要这些功能，建议直接用 std::deque 或 std::list，自己控制接口。
另外，std::queue 不是线程安全的。多线程环境下你必须自己加锁，或者用 TBB、Boost 等库提供的并发队列。
知识结构图
这张图把 queue 的核心脉络理清楚了：适配器模式、底层容器选择、核心操作、三大应用场景，以及那些容易踩的坑。我个人建议你把这张图存下来，写代码前瞄一眼，思路会清晰很多。