一、什么是 std::queue
std::queue 是 C++ 标准库中提供的一个**先进先出（FIFO）**的顺序容器适配器。它在元素插入和删除时遵循“队列”的原则：
- 入队（push）：元素从 尾部（back） 插入；
- 出队（pop）：元素从 头部（front） 移除。
std::queue 是容器适配器（container adaptor），底层默认使用 std::deque 作为实现容器，但你也可以替换为 std::list 等。
二、常用接口函数说明
| 函数 | 含义 |
|---|
push() | 插入元素（入队） |
pop() | 移除头部元素（出队） |
front() | 返回头部元素引用 |
back() | 返回尾部元素引用 |
empty() | 判断队列是否为空 |
size() | 返回元素数量 |
emplace() | 原地构造新元素（C++11） |
swap() | 与其他队列交换内容 |
三、完整示例代码
#include <iostream>
#include <queue>int main() {std::queue<int> q;q.push(10);q.push(20);q.push(30);std::cout << "队头元素: " << q.front() << std::endl; std::cout << "队尾元素: " << q.back() << std::endl; std::cout << "当前大小: " << q.size() << std::endl; while (!q.empty()) {std::cout << "出队元素: " << q.front() << std::endl;q.pop();}return 0;
}
四、自定义类型使用 std::queue
struct Task {int id;std::string name;
};int main() {std::queue<Task> taskQueue;taskQueue.push({1, "Load data"});taskQueue.push({2, "Process data"});while (!taskQueue.empty()) {Task t = taskQueue.front();std::cout << "任务ID: " << t.id << ", 名称: " << t.name << std::endl;taskQueue.pop();}
}
五、和 std::vector 的对比
| 特性 | std::vector | std::deque |
|---|
| 内存结构 | 单块连续 | 多块分段连续 |
push_front() | ❌ 慢（需整体移动） | ✅ 快（O(1)） |
push_back() | ✅ 快 | ✅ 快 |
| 随机访问 | ✅ 支持 operator[] | ✅ 支持 operator[] |
| 内存局部性 | ✅ 好 | ❌ 较差（分块） |
| 指针/引用稳定性 | ❌ 容易失效 | ❌ 插入也可能失效 |
六、底层结构（分段连续）
deque 将内存划分为多个固定大小的缓冲区（block），每个 block 通常为 512 字节或更多；- 使用**一个中心数组（map）**来管理这些 block；
- 插入新元素时，分配新的 block 而不必整体拷贝（避免
vector 的 resize）； - 虽然可随机访问，但访问效率略低于
vector（因为需先跳转到 block）。
七、性能分析
| 操作 | 时间复杂度 | 性能分析 |
|---|
push_back | O(1) | 快，可能偶尔分配新 block |
push_front | O(1) | 快，vector 不支持 |
pop_back | O(1) | 快 |
pop_front | O(1) | 快 |
insert/erase 中间位置 | O(n) | 慢，仍需移动大量元素 |
operator[] | O(1) | 但比 vector 慢一点 |
内存局部性
vector 更适合需要大量遍历的场景；deque 更适合频繁前后端操作（如滑动窗口、缓存队列）。
八、注意事项
std::queue 不能随机访问（不能用 [] 索引元素）；front() 和 back() 返回的是引用，可以直接修改元素；- 若调用
front() 或 pop() 时队列为空，会导致 未定义行为（UB）； - 默认底层容器是
std::deque，可以替换为 std::list（只要支持 push_back() 和 pop_front() 即可）：std::queue<int, std::list<int>> myQueue;
九、典型应用场景
| 场景 | 使用理由 |
|---|
| 滑动窗口算法 | 快速前后进出元素 |
| 双端缓存 | LRU缓存中维护活跃元素 |
| 实时图像处理 | 处理固定宽度时间窗口 |
| 调度器实现 | 实现动态任务调度队列 |
替代 queue | 更灵活，可随机访问 |
十、线程安全封装建议
std::queue 本身不是线程安全的。可以加互斥锁封装：
#include <mutex>
#include <queue>template<typename T>
class ThreadSafeQueue {
private:std::queue<T> queue_;std::mutex mutex_;
public:void push(const T& value) {std::lock_guard<std::mutex> lock(mutex_);queue_.push(value);}bool try_pop(T& result) {std::lock_guard<std::mutex> lock(mutex_);if (queue_.empty()) return false;result = queue_.front();queue_.pop();return true;}bool empty() {std::lock_guard<std::mutex> lock(mutex_);return queue_.empty();}
};
十一、性能测试建议
- 若用于大规模随机读写，请使用
std::vector； - 若数据频繁前后“推入-弹出”，使用
deque 更高效； - 若使用
std::queue 但又需访问队头/队尾/搜索，请改用 deque 直接操作； - 若关心 CPU 缓存命中率，
vector 更有优势。
十二、总结
| 点 | 结论 |
|---|
| 适合用途 | 双端插入/删除频繁的场景 |
| 不适用途 | 高频中间插入/随机排序 |
| 替代容器 | vector：更快遍历；list：更好插入中间 |
| 易错点 | 内存不连续、遍历效率低于 vector |
| 高级用法 | 环形缓冲区、线程安全消息队列 |
