文章目录
- 1. 队列(queue)
- 1.1 定义
- 1.2 函数
- 1.3 习题
- 1.3.1 例题(周末舞会)
- 2. 双向队列(deque)
- 2.1 定义
- 2.2 函数
- 2.3 题目
- 2.3.1 例题(打BOSS)
1. 队列(queue)
队列也是一种特殊的数据类型,它遵守了先进先出(FIFO, First In First Out)原则
1.1 定义
形象点儿说,队列相当于学校的排队的食堂,先来排队的先得到饭,然后先走;后来排队的最后得到饭,最后走。
STL 专门提供了关于栈和队列的容器,还拓展了一个双向队列(deque)
导入栈(stack):#include <stack>
导入队列(queue):#include <queue>
导入双向队列(deque):#include <deque>
三个库均可使用 #include <bits/stdc++.h>
导入
1.2 函数
想要构造一个队列,可以使用queue<类型> 队列名称
这种方式构造,一般定义的名称:Q
,T
,q
,Queue
等
名称.push(x)
:让x入队,也就是x排到队列后方名称.pop()
:让队头出队,后面的代替队头名称.front()
:返回队头数据名称.size()
:返回队列长度名称.empty()
:队列是否为空,空返回1,否则返回0名称.clear()
:清空
遍历队列一般都是程序末尾的事
#include <iostream>
#include <queue>
using namespace std; int main () {queue<int> T; ...while(T.size()) {cout << T.front() << ' '; T.pop(); }return 0;
}
1.3 习题
它和栈还有一种特殊的出法:DFS 与 BFS
这个后面会有关于它的文章
1.3.1 例题(周末舞会)
题目链接
题目描述
假设在周末舞会上, x x x 个男士和 y y y 个女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。舞曲总共播放 n n n 次。现要求写一个程序,模拟上述舞伴配对问题。
输入
第一行输入两个数 x x x 和 y y y,表示两队的人数;
第二行输入一个数 n n n,表示舞曲的数目。
输出
输出 n n n 排,每排两个数,表示男士编号和女士编号
样例输入
4 6
7
样例输出
1 1
2 2
3 3
4 4
1 5
2 6
3 1
题解
仔细观察输出,你会发现规律:左边以 1 , 2 , . . . , x , 1 , 2 , . . . , x , . . . 1, 2, ..., x, 1, 2, ..., x, ... 1,2,...,x,1,2,...,x,... 的顺序输出,右边以 1 , 2 , y , . . . , 1 , 2 , . . . , y , . . . 1, 2, y, ..., 1, 2, ..., y, ... 1,2,y,...,1,2,...,y,... 的顺序输出
#include <iostream>
#include <queue>
using namespace std;
int main() {int x, y, n; cin >> x >> y >> n; queue<int> M, F; //M:男士 F:女士for(int i=1; i<=x; i++) //初始化男士编号M.push(i); for(int i=1; i<=y; i++) //初始化女士编号F.push(i); for(int i=1; i<=n; i++) {M.push(M.front()); //跳完后男士排在队伍后面F.push(F.front()); //跳完后女士排在队伍后面cout << M.front() << ' ' << F.front() << endl; //输出M.pop(); F.pop(); }return 0; //结束程序
}
2. 双向队列(deque)
2.1 定义
这是 STL 独有的专属容器,它也有队头和队尾,但插入和删除可以同时进行。形象一点就是医院的“军人优先”。还是一个队列,普通人往后排,军人们有可以排在前面的特权。因此,队头可以插入删除,队尾也可以。
2.2 函数
使用deque<类型> 名称
构造一个双向队列,一般名称T
,Deque
等
名称.push_front(x)
:向队头插入元素x名称.push_back(x)
:向队尾插入元素x名称.pop_front()
:队头出队名称.pop_back()
:队尾出队名称.front()
:返回队头元素名称.back()
:返回队尾元素名称.size()
:返回队列大小名称.empty()
:队列是否为空,是返回1,否则返回0名称.clear()
:清空
2.3 题目
双向队列只是stack
和queue
的整合,所以关于它的题目很少
2.3.1 例题(打BOSS)
这个复制不了,请点开 题目链接 查看
题解
#include <bits/stdc++.h>
using namespace std; int main () {int m, s, hp; cin >> m >> s >> hp; deque<int> T; for(int i=1; i<=m; i++) {string o; cin >> o; if(o=="add") {int n; cin >> n; if(T.size()<s) {T.push_back(n); }} else {if(!T.empty()) {if(T.front()>=T.back()) {hp -= T.front(); T.pop_front(); } else {hp -= T.back(); T.pop_back(); }if(hp<=0) {cout << i; return 0; }}}}cout << "-1"; return 0;
}
预览
- 二十六:vector容器
- 二十七:递推
- 二十八:set容器
- 二十九:map容器
- 三十:二分查找
- 三十一:前缀和与差分
- 三十二:栈(stack)
- 三十三:队列(queue)
- 三十四:神奇的计算机
- 三十五:链表
- 三十六:树与遍历
- 三十七:图与DFS、BFS
- 三十八:
array
容器 - 三十九:
priority_queue
容器
…