A3阶段 第二课 队列
2025年6月7日
学习时长
约1.5小时
难度
A3阶段/CSP-J
标签
数据结构
讲师
王骏峣
队列
核心概念： 队列是先进先出（FIFO）的线性表
如果A比B更早进入队列，那A一定比B先退出队列（FIFO，先进先出）
入队的一段叫队尾，出队的一端叫队首
队列的有关操作
入队：将新元素从队尾加入队列
出队：把排在最前面的元素从队列里出来
用数组模拟队列
创建队列
数组队列的创建
int q[N]; //开辟数组队列，N是队列最大的大小int l = 0,r = 0; //使用变量记录队首和队尾位置
操作数组队列
数组队列的操作，注意：错误码按照自己的习惯更改
//入队q[++r] = x;
//出队
if(l <= r) l ++;
//询问队首元素
if(l <= r)return q[l];
else return 0x3f3f3f04;
STL中的队列容器（queue）
特点：简单易用，好记
queue的操作
| 代码 | 说明 |
|---|---|
|
STL queue操作
#include<queue>;
|
导入头文件 |
|
STL queue操作
queue<int> q;
|
创建一个存储int类型数据的队列 |
|
STL queue操作
q.push(a);
|
将a入队 |
|
STL queue操作
q.pop();
|
将队首出队 |
|
STL queue操作
int t = q.front();
|
将t赋值为q的队首元素 |
|
STL queue操作
int si = q.size();
|
将si赋值为q的大小（元素个数） |
|
STL queue操作
bool isempty = q.empty();
|
将isempty赋值为q的是否为空（bool） |
例题
第一题 【模板】队列
前往第二题 约瑟夫问题
前往第三题 [NOIP2010 提高组] 机器翻译
前往第四题 [ABC335C] Loong Tracking
前往第五题 [COCI2007-2008#5] AVOGADRO
前往学习要点总结
- 队列是一种基础的数据结构，是一种具有FIFO特性的线性表
- 队列最重要的操作：入队和出队
- 如果所有元素都有出队，那么对于任意入队序列，出队序列有且仅有一种，并且与入队序列相同
- 可以用数组模拟栈，也可以用更方便的queue容器