优先队列
引自：
洛谷P3378 【模板】堆
#输入
5
1 2
1 5
2
3
2
#输出
2
5
AC代码：
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<int>,greater<int> > q;
int main()
{
ll n;
cin>>n;
while(n--){
int key;
ll num;
cin>>key;
if(key == 1){
cin>>num;
q.push(num);
}
else if(key == 2){
cout<<q.top()<<endl;
}
else if(key == 3){
q.pop();
}
}
return 0;
}
解析：
①看到题目中第二第三条操作都是对输入的最小的数进行操作，显然能够想到一边输入一边排序的思想。边录入数据边排序，每输入一次进行一次 sort() 显然时间会爆表，结合过去的刷题经验，很容易就能想到使用优先队列进行排序操作。
②使用优先队列需包含头文件
#include <queue>
③优先队列泛型容器类的定义
priority_queue<Type, Container, Functional>
。其中Type为该容器存储的类型，Container必须是填入一个用数组实现的容器，此处，经过在网上的资料查阅的知，vector和deque( 虽然deque我也从来没用过，vector只是有所耳闻，除了用于优先对联也并未真正实用过 )均可，但list不行。Functional即为对于优先队列给出一个排序方式，格式一般为
greater<int>
或
less<int>
( 此处仅是打比方 )。本题将要给出的优先队列定义为
priority_queue<ll,vector<int>,greater<int> > q;
一定要注意的是
greater<int>
后面一定要加一个空格，与最后一个
>
分离开。
④根据题意进行模拟即可，轻松的AC。
单调栈
优先队列也称单调队列，因此将优先队列与单调栈放在一起讲。
引自：
P5788 【模板】单调栈
#输入
5
1 4 2 3 5
#输出
2 5 4 5 0
AC代码：
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 3000005;
int a[maxn] = {0},f[maxn] = {0};
stack<int> s;//用于存储下标的栈
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]<=a[i]){
s.pop();
}
f[i] = s.empty()?0:s.top();
s.push(i);
}
for(int i=1;i<=n;i++){
printf("%d ",f[i]);
}
return 0;
}
解析：
①单调栈的概念：单调栈的定义与优先队列大同小异，都是根据数据的大小按照一定的顺序在容器中进行排序，只不过C++的STL没有现成的单调栈模板，因此只能靠C++STL中的栈进行模拟。单调栈与优先队列不同，不直接存储元素，而是先将数据读入数组，再将数据在数组中的下标存储到栈中（就题论题而言，是这样的）。
②在本题中如何理解单调栈：在阅读相关题解之前，对于这个问题我也是毫无头绪的，但是其中一篇题解对我的启发很大，即在进行数据分析得到结果时，
逆向遍历数组
。显然，本题的目标是寻找该元素之后与它距离最近的比它大的元素，将问题具象，即人们站队排成一排，寻找你能看到的第一个比你高的人。
③代码中
最重要的部分
：
for(int i=n;i>=1;i--){//如前面所述，逆序遍历数组
while(!s.empty()&&a[s.top()]<=a[i]){/*！倘若目前的元素
比它之后的所有元素都大，后面的数据就毫无意义了<重温题意：寻找
该元素之后第一个比它大的元素>！*/
s.pop();//没有意义的元素直接弹出即可
}
f[i] = s.empty()?0:s.top();/*加一个三元运算符，若栈为空
则代表后面没有元素比它大，按照题意置零，否则，栈顶就是答案。*/
s.push(i);//将当前的下标压入栈
}
④
优化：
大量刷题的朋友们都知道，C++的cin和cout速度不及C的scanf和printf，在本题中也是如此，对于洛谷的OJ，倘若使用C++的输入输出流，会造成最后四个测试点TLE，而改换成C的scanf和eprintf即可AC。
以上就是优先队列和单调栈的内容。