AKSZ-栈、队列和优先队列
2024-05-02 17:38:04
发布于:广东
栈和队列——标准模板库(STL)
栈(stack)
stack<int> |
---|
1.定义 stack<int> stk
栈名
2.入栈 stk.push(变量名);
入栈
3.出栈 stk.pop();
查看栈顶int tmp = stk.top();
栈顶
4.栈长度 stk.size();
例题:验证栈序列
#include<bits/stdc++.h>
#include<stack>
using namespace std;
const int N=100010;
int q,n,sum;
int a[N],b[N];
int main(){
cin>>q;
while(q--){
sum=1;
stack<int> stk;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
for(int i=1;i<=n;++i){
stk.push(a[i]);
while(stk.top()==b[sum]){
stk.pop();++sum;
if(stk.empty())break;
}
}
if(stk.empty())cout<<"Yes"<<endl;
else cout<<"No"<<endl;
while(!stk.empty())stk.pop();
}
return 0;
}
队列(queue)
1.定义:一种线性表;
2.性质:先进先出,后进后出;
队列数组实现
步骤 | 代码 | 释义 |
---|---|---|
1 | front rear = 0; |
一个指向队头前一个元素,一个尾巴 |
2 | q[++rear]=x; |
入队 |
3 | front++; |
|
4 | cout<<q[front+1]; |
|
5 | cout<<rear-front; |
|
6 | 当front ,rear 相等时记得先判空 |
例题:约瑟夫问题2
题目描述
n个人(编号0到n-1)围成一圈,从第一个人开始报数1,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,问最后一个人,编号多少?
输入格式
n m
输出格式
出圈的编号
输入输出样例
输入#1
8 3
输出#1
6
说明/提示
50%的数据0<n,m<=100
100%的数据0<n<=1000000,0<m<=100
参考代码如下
#include <iostream>
using namespace std;
int main(){
int n,m,r= 0;
cin>>n>>m;
for (int i=2;i<=n;i++) {
r=(r+m)%i;
}
cout<<r;
return 0;
}
优先队列()
定义优先队列
priority_queue<int>q;//定义一个优先队列(大根堆)
priority_queue<int ,vector<int> ,greater<int> > q;//定义一个小根堆
取最大值
int t = q.top();//取出一个元素,最大值。
删除最大的元素
q.pop();
放入一个元素
q.push(x);
判断是否为空
q.empty();
优先队列的长度
q.size();
结构体重载
struct node{
int x,y;//x 大的放在堆里面
//重载
friend bool operator <(node a,node b){
return a.x < b.x; //把大的x放在前面
}
};
注:可以将return a.x < b.x;
改成//return a.x > b.x;
,意思就变成了把小的x放在前面
。大根堆为默认
。
这里空空如也
有帮助,赞一个