queue容器详解

queue（队列）是STL中的容器适配器，基于序列式容器（默认deque）封装而成，遵循“先进先出（FIFO）”原则，即先插入的元素先被访问、先被删除，与stack（先进后出）形成互补，常与set、map等容器配合使用。

一、queue核心特性

1. 容器适配器：不独立存储数据，依赖底层容器（默认deque，也可指定vector、list）；
2. 先进先出（FIFO）：第一个插入的元素第一个被删除，类似排队买票，先到先得；
3. 操作限制：仅支持在队尾插入、队头删除和访问，不支持随机访问和中间插入删除；
4. 效率：插入（队尾）和删除（队头）效率高，具体取决于底层容器（deque默认最优）。

queue与set、stack的核心区别：

• 与set：set是关联式容器，侧重去重、查找；queue是容器适配器，侧重“先进先出”的顺序操作；
• 与stack：stack是“先进后出”，queue是“先进先出”，二者均为容器适配器，适用场景不同。

二、queue基础用法（完整代码）

#include <iostream>
#include <queue>  // queue的头文件
#include <list>   // 可指定底层容器为list
using namespace std;

int main() {
    // 1. 定义queue（多种方式）
    queue<int> q1;  // 默认底层容器为deque，存储int类型
    queue<int, list<int>> q2;  // 指定底层容器为list
    queue<int> q3(q1);  // 拷贝构造
    
    // 2. 插入元素（队尾插入）
    q1.push(1);  // 队尾插入1，队列：[1]
    q1.push(2);  // 队尾插入2，队列：[1, 2]
    q1.push(3);  // 队尾插入3，队列：[1, 2, 3]
    
    // 3. 访问元素（仅能访问队头和队尾）
    cout << "队头元素：" << q1.front() << endl;  // 输出：1（队头，第一个插入的元素）
    cout << "队尾元素：" << q1.back() << endl;   // 输出：3（队尾，最后一个插入的元素）
    
    // 4. 删除元素（队头删除）
    q1.pop();  // 删除队头元素1，队列：[2, 3]
    cout << "删除队头后，队头元素：" << q1.front() << endl;  // 输出：2
    
    // 5. 常用操作
    cout << "\n队列大小（元素个数）：" << q1.size() << endl;  // 输出：2
    if (q1.empty()) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列非空" << endl;
    }
    
    // 6. 遍历队列（需通过弹出元素实现，会破坏原队列）
    cout << "\n队列遍历（弹出元素）：";
    while (!q1.empty()) {
        cout << q1.front() << " ";
        q1.pop();  // 弹出队头元素
    }
    cout << endl;  // 输出：2 3（遍历后队列为空）
    
    // 补充：指定list为底层容器的queue
    q2.push(10);
    q2.push(20);
    cout << "\nq2队头：" << q2.front() << "，队尾：" << q2.back() << endl;  // 输出：10 20
    
    return 0;
}

三、queue 的底层容器选择

queue 是容器适配器，底层依赖其他容器实现，常用的底层容器有 3 种，各有优劣：

1. deque（默认）：兼顾了 vector 和 list 的优势，队头和队尾操作效率都很高，是最推荐的底层容器；
2. list：插入删除效率高，适合频繁插入删除的场景，但随机访问效率低（不影响 queue，因为 queue 不支持随机访问）；
3. vector：队尾插入效率高，但队头删除效率低（需移动所有元素），不推荐作为 queue 的底层容器。

四、常用操作汇总

操作	语法	说明
插入（队尾）	push (元素)	在队列尾部插入一个元素，效率 O (1)
删除（队头）	pop()	删除队列头部的元素，无返回值，效率 O (1)
访问队头	front()	返回队列头部的元素（不删除），需确保队列非空
访问队尾	back()	返回队列尾部的元素（不删除），需确保队列非空
判空	empty()	队列为空返回 true，否则返回 false
获取大小	size()	返回队列中元素的个数

五、常见误区与注意事项

无 clear () 方法：queue 没有直接的 clear () 方法，清空队列需通过循环 pop () 弹出所有元素；

• 不能访问中间元素：queue 仅支持访问队头和队尾，无法访问队列中间的元素；
• 弹出元素前需判空：调用 pop ()、front ()、back () 前，需先通过 empty () 判断队列是否非空，否则会导致未定义行为；
• 底层容器影响效率：选择不同的底层容器会影响 queue 的插入删除效率，默认 deque 即可满足绝大多数场景。

六、适用场景总结

queue 的 “先进先出” 特性决定了其适用场景，常与 set、map 等容器配合使用：

1. 任务排队场景（如：后台任务队列、消息队列）；
2. 广度优先搜索（BFS）：算法中常用 queue 存储待访问的节点，按顺序处理；
3. 需按插入顺序处理数据的场景（如：订单处理、日志输出）；
4. 限流场景（如：控制请求访问频率，按顺序处理请求）。

补充：priority_queue（优先队列，queue 的延伸）

priority_queue 是 queue 的变种，同样是容器适配器，核心区别是「不遵循先进先出」，而是按照元素的优先级排序，优先级最高的元素最先被访问（默认大顶堆，即值越大优先级越高），常与 set 配合使用（如：按优先级处理数据，同时去重）。

基础用法示例：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 默认大顶堆（值越大优先级越高）
    priority_queue<int> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    
    // 遍历（每次弹出优先级最高的元素）
    cout << "priority_queue遍历（按优先级）：";
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 访问优先级最高的元素（队头）
        pq.pop();
    }
    cout << endl;  // 输出：5 3 2 1
    
    // 小顶堆（值越小优先级越高）
    priority_queue<int, vector<int>, greater<int>> pq_min;
    pq_min.push(3);
    pq_min.push(1);
    pq_min.push(5);
    cout << "\n小顶堆遍历：";
    while (!pq_min.empty()) {
        cout << pq_min.top() << " ";
        pq_min.pop();
    }
    cout << endl;  // 输出：1 3 5
    
    return 0;
}