csp信奥赛C++标准模板库STL（9）：queue的使用详解

csp信奥赛C++标准模板库STL（9）：queue的使用详解

一、队列的基本概念

1.1 什么是队列

队列是一种先进先出（First In First Out，FIFO）的线性数据结构。它有两个基本操作：

• 入队（Enqueue）：在队尾添加元素
• 出队（Dequeue）：从队头移除元素

1.2 队列的特点

• 元素访问受限：只能在队头和队尾操作
• 时间有序：先进入的元素先被处理
• 常用于任务调度、缓冲区等场景

二、C++ STL queue 的基本用法

2.1 头文件和定义

#include<queue>// 包含queue头文件#include<iostream>usingnamespacestd;// 定义queuequeue<int>q;// 整型队列queue<string>strQueue;// 字符串队列queue<pair<int,int>>pointQueue;// 坐标队列，常用于BFS

2.2 常用成员函数

2.3 基本操作示例

#include<iostream>#include<queue>usingnamespacestd;intmain(){queue<int>q;// 入队操作q.push(10);q.push(20);q.push(30);cout<<"队列大小: "<<q.size()<<endl;// 输出: 3cout<<"队首元素: "<<q.front()<<endl;// 输出: 10cout<<"队尾元素: "<<q.back()<<endl;// 输出: 30// 出队操作q.pop();cout<<"出队后队首: "<<q.front()<<endl;// 输出: 20// 遍历队列（注意：queue没有迭代器）cout<<"队列元素: ";while(!q.empty()){cout<<q.front()<<" ";q.pop();}// 输出: 20 30return0;}

三、在CSP信奥赛中的典型应用

3.1 广度优先搜索（BFS）

queue是BFS算法的核心数据结构，常用于：

• 迷宫最短路径
• 图的遍历
• 状态搜索

// 迷宫BFS示例：计算从起点到终点的最短步数#include<iostream>#include<queue>#include<vector>usingnamespacestd;constintN=100;intmp[N][N];// 0表示可走，1表示障碍intd[N][N];// 记录距离intn,m;// 迷宫大小// 方向数组：上下左右intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};intbfs(intstartX,intstartY,intendX,intendY){queue<pair<int,int>>q;// 初始化距离数组for(inti=0;i<n;i++)for(intj=0;j<m;j++)d[i][j]=-1;// 起点入队q.push({startX,startY});d[startX][startY]=0;while(!q.empty()){auto[x,y]=q.front();q.pop();// 到达终点if(x==endX&&y==endY){returndist[x][y];}// 向四个方向扩展for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];// 检查边界和可通行性if(nx>=0&&nx<n&&ny>=0&&ny<m&&mp[nx][ny]==0&&d[nx][ny]==-1){d[nx][ny]=d[x][y]+1;q.push({nx,ny});}}}return-1;// 无法到达终点}

3.2 滑动窗口问题

// 使用队列维护滑动窗口#include<iostream>#include<queue>#include<vector>usingnamespacestd;// 计算滑动窗口最大值vector<int>fun(vector<int>&nums,intk){vector<int>result;deque<int>dq;// 使用deque实现单调队列for(inti=0;i<nums.size();i++){// 维护队列单调递减while(!dq.empty()&&nums[dq.back()]<=nums[i]){dq.pop_back();}dq.push_back(i);// 移除窗口外的元素if(dq.front()<=i-k){dq.pop_front();}// 记录窗口最大值if(i>=k-1){result.push_back(nums[dq.front()]);}}returnresult;}

3.3 拓扑排序

// 有向无环图的拓扑排序vector<int>fun(intn,vector<vector<int>>&edges){vector<vector<int>>graph(n);vector<int>indegree(n,0);// 建图并计算入度for(auto&edge:edges){graph[edge[0]].push_back(edge[1]);indegree[edge[1]]++;}queue<int>q;// 将所有入度为0的节点入队for(inti=0;i<n;i++){if(indegree[i]==0){q.push(i);}}vector<int>result;while(!q.empty()){intnode=q.front();q.pop();result.push_back(node);// 将后继节点的入度减1for(intneighbor:graph[node]){indegree[neighbor]--;if(indegree[neighbor]==0){q.push(neighbor);}}}// 检查是否有环if(result.size()!=n){return{};// 存在环，无法拓扑排序}returnresult;}

四、queue的注意事项和技巧

4.1 清空队列

// 方法1：循环popwhile(!q.empty()){q.pop();}// 方法2：重新构造（推荐，更简洁）q=queue<int>();

4.2 队列为空时的处理

queue<int>q;// 错误：空队列访问front()会导致未定义行为// int x = q.front(); // 错误！// 正确：先检查是否为空if(!q.empty()){intx=q.front();q.pop();}

五、总结

在CSP信奥赛中，queue是最常用的数据结构之一，尤其适用于：

1. BFS算法：求最短路径、最少步数等问题
2. 模拟过程：排队系统、任务调度等
3. 状态空间搜索：游戏状态、组合状态等

关键要点：

• 理解FIFO原理和队列操作的时间复杂度
• 掌握BFS中队列的应用模式
• 学会处理队列边界条件（空队列访问）
• 了解手写队列的实现方法

通过大量练习，熟练掌握queue的使用，能够显著提高解决CSP竞赛中搜索类和模拟类问题的能力。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}