队列queue是 C STL 中经典的先进先出FIFO, First In First Out数据结构元素从队尾入队从队头出队全程仅支持两端操作是解决任务调度、缓冲区管理、广度优先搜索BFS等问题的核心工具。一、核心概念与原理1. 基本特性操作规则先进先出FIFO。最先入队的元素最先出队。操作位置队尾tail仅执行入队操作push。队头front仅执行出队操作pop、获取队头元素。底层容器默认使用deque双端队列也可指定list注意vector 不可用。不支持迭代器队列是容器适配器不支持随机访问只能通过标准接口操作。2. 关键成员函数成员函数功能push(值)入队将元素添加到队尾pop()出队删除队头元素不返回值front()获取队头元素的引用back()获取队尾元素的引用size()返回队列中元素的个数empty()判断队列是否为空为空返回true二、定义与初始化使用队列必须包含头文件queue。定义时指定元素类型默认容器为deque也可手动指定底层容器。1. 基础语法#include queue // 必须包含头文件 // 格式: queue元素类型, 容器类型 队列名; queueint q1; // 最常用int类型默认deque容器 queuechar, dequechar q2; // 显式指定deque容器 queueint, listint q3; // 指定list作为底层容器2. 代码示例#include queue #include iostream #include list using namespace std; int main() { // 1. 创建空队列 queueint q; // 2. 定义不同容器的队列演示用 queuechar q1; // 默认deque queueint, listint q4; // 指定list return 0; }三、常用操作实战代码#include queue #include iostream using namespace std; int main() { // 创建一个int类型的空队列 queueint q; // 1. 入队操作 (0,1,2,...,9) for (int i 0; i 10; i) { q.push(i); } // 2. 获取队列信息 cout 队列的数据个数: q.size() endl; cout 队头元素: q.front() ,队尾元素: q.back() endl; // 3. 出队操作 (输出并删除队头元素) cout 出队: endl; while (!q.empty()) { cout q.front() ; // 输出队头 q.pop(); // 删除队头 } cout endl; return 0; }运行结果队列的数据个数:10 队头元素:0,队尾元素:9 出队: 0 1 2 3 4 5 6 7 8 9四、底层容器限制与选择1. 为什么默认是dequedeque支持在头尾快速插入 / 删除且支持随机访问是队列的最佳适配。2. 容器选择规则可以作为队列底层容器的类型必须支持以下操作front()、back()push_back()、pop_front()结论✅可用容器deque默认选择头尾操作高效。list双向链表头尾操作稳定适合大数据量。❌不可用容器vector不支持pop_front()头部删除效率极低需移动所有元素不能用作队列容器。forward_list不支持back()和pop_back()。array不支持动态扩容。五、常见应用场景1. 广度优先搜索BFS队列是 BFS 的核心数据结构按层级遍历节点// 伪代码BFS核心逻辑 queueNode q; q.push(root); while(!q.empty()) { Node cur q.front(); q.pop(); // 处理当前节点 for(auto child : cur.children) { q.push(child); } }2. 任务调度模拟现实世界的排队场景如打印任务池、消息队列queuestring taskQueue; taskQueue.push(打印文档A); taskQueue.push(打印文档B); // 按顺序处理任务六、核心总结核心特性说明核心规则先进先出FIFO操作口诀push 尾pop 头front 取顶back 取尾头文件#include queue默认容器deque容器禁忌vector 不可用不支持 pop_front时间复杂度入队 / 出队 / 获取头尾均为O(1)核心口诀队列队尾进队头出push 入pop 出front 取头back 取尾。
C++12： 队列（queue）——先进先出（FIFO）数据结构
队列queue是 C STL 中经典的先进先出FIFO, First In First Out数据结构元素从队尾入队从队头出队全程仅支持两端操作是解决任务调度、缓冲区管理、广度优先搜索BFS等问题的核心工具。一、核心概念与原理1. 基本特性操作规则先进先出FIFO。最先入队的元素最先出队。操作位置队尾tail仅执行入队操作push。队头front仅执行出队操作pop、获取队头元素。底层容器默认使用deque双端队列也可指定list注意vector 不可用。不支持迭代器队列是容器适配器不支持随机访问只能通过标准接口操作。2. 关键成员函数成员函数功能push(值)入队将元素添加到队尾pop()出队删除队头元素不返回值front()获取队头元素的引用back()获取队尾元素的引用size()返回队列中元素的个数empty()判断队列是否为空为空返回true二、定义与初始化使用队列必须包含头文件queue。定义时指定元素类型默认容器为deque也可手动指定底层容器。1. 基础语法#include queue // 必须包含头文件 // 格式: queue元素类型, 容器类型 队列名; queueint q1; // 最常用int类型默认deque容器 queuechar, dequechar q2; // 显式指定deque容器 queueint, listint q3; // 指定list作为底层容器2. 代码示例#include queue #include iostream #include list using namespace std; int main() { // 1. 创建空队列 queueint q; // 2. 定义不同容器的队列演示用 queuechar q1; // 默认deque queueint, listint q4; // 指定list return 0; }三、常用操作实战代码#include queue #include iostream using namespace std; int main() { // 创建一个int类型的空队列 queueint q; // 1. 入队操作 (0,1,2,...,9) for (int i 0; i 10; i) { q.push(i); } // 2. 获取队列信息 cout 队列的数据个数: q.size() endl; cout 队头元素: q.front() ,队尾元素: q.back() endl; // 3. 出队操作 (输出并删除队头元素) cout 出队: endl; while (!q.empty()) { cout q.front() ; // 输出队头 q.pop(); // 删除队头 } cout endl; return 0; }运行结果队列的数据个数:10 队头元素:0,队尾元素:9 出队: 0 1 2 3 4 5 6 7 8 9四、底层容器限制与选择1. 为什么默认是dequedeque支持在头尾快速插入 / 删除且支持随机访问是队列的最佳适配。2. 容器选择规则可以作为队列底层容器的类型必须支持以下操作front()、back()push_back()、pop_front()结论✅可用容器deque默认选择头尾操作高效。list双向链表头尾操作稳定适合大数据量。❌不可用容器vector不支持pop_front()头部删除效率极低需移动所有元素不能用作队列容器。forward_list不支持back()和pop_back()。array不支持动态扩容。五、常见应用场景1. 广度优先搜索BFS队列是 BFS 的核心数据结构按层级遍历节点// 伪代码BFS核心逻辑 queueNode q; q.push(root); while(!q.empty()) { Node cur q.front(); q.pop(); // 处理当前节点 for(auto child : cur.children) { q.push(child); } }2. 任务调度模拟现实世界的排队场景如打印任务池、消息队列queuestring taskQueue; taskQueue.push(打印文档A); taskQueue.push(打印文档B); // 按顺序处理任务六、核心总结核心特性说明核心规则先进先出FIFO操作口诀push 尾pop 头front 取顶back 取尾头文件#include queue默认容器deque容器禁忌vector 不可用不支持 pop_front时间复杂度入队 / 出队 / 获取头尾均为O(1)核心口诀队列队尾进队头出push 入pop 出front 取头back 取尾。
