单调队列
参考资料：
基础概念
单调队列的重点分为 "单调" 和 "队列"
"单调" 指的是元素的的 "规律"——递增（或递减）
"队列" 指的是元素只能从队头和队尾进行操作
\(PS\):此处的 "队列" 跟普通队列的一大不同就在于可以从队尾进行操作，\(STL\)中有类似的数据结构\(deque\)
解题思路
正如基础概念所说的，单调队列与普通队列之区别在于可以在队尾弹出元素，使得可以比较容易的维护其单调性，操作主要如下：
int a[MAXN];//用数组模拟单调队列
int head=0,tail=0;//还没元素
tail++;
cin>>a[tail]//扩展，推入元素
head++;//从队首弹出
tail--;//从队尾弹出
一般单调队列（递减）思路为：
1.入队一个
2.\(for\)循环输入，如果比前面大，则把前面的数从队尾弹出
3.最后输出队首
例题
1.给一个长度为\(n\)的数组，编程输出每\(k\)个连续的数中的最大值和最小值。
这时，很容易想到传统的暴力枚举：对于每一段\(i\) 至 \(i+k-1\)的序列，逐个比较来找出最大值（和最小值），时间复杂度约为\(O(n*k)\),但这种方法在\(k\)稍大的时候就会十分轻易的超时
这时，单调队列闪亮登场！！！
要求的是每连续的 个数中的最大（最小）值，很明显，当一个数进入所要 "寻找" 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。
也就是说——当满足以上条件时，可将前面的数 "弹出"，再将该数真正\(push\)进队尾。
这就相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，不仅如此，由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。
显而易见的是，在这样的算法中，每个数只要进队与出队各一次，因此时间复杂度被降到了 。
而由于查询区间长度是固定的，超出查询空间的值再大也不能输出，因此还需要 \(site\)数组记录第\(i\)个队中的数在原数组中的位置，以弹出越界的队头。
2.队员选拔
夏令营马上就要开幕了，学校组织了一次队员选拔活动。参加队员选拔的同学们排队接受面试官们的面试。
他们按照先来先面试并且先结束的原则接受面试官们的考查。
在面试中每位同学的能力值是重点考察指标，作为主面试官的\(John\)想知道当前正在接受面试的同学中能力值最高的人叫什么，他请你帮忙编写一个程序来计算。
第一行一个数字\(N\)，表示操作次数
第\(2\)到\(N+1\)行，每一行表示一个操作，总共有\(3\)种操作，格式如下
C操作
\(Name\) \(Value\)表示名字为\(NAME\)能力值为\(VALUE\)的同学加入面试队列\((|Name|≤10,0≤Value≤10^9|Name|≤10,0≤Value≤10^9)\)
G操作
位于队首的同学离开队列
Q操作
\(John\)想知道当前队列中能力值最高的人的姓名，如果队列为空，输出\(EMPTY\)
对于每一个询问，输出答案，如果多个人拥有最高能力值，请输出最早进队的人的姓名
例题代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[1000005], q[1000005], front = 1, tail = 1, cur = 0, cnt = 0;
char c, s[1000005][25];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
scanf(" %c", &c);
if (c == 'G') { //判断操作类型
cur++; //数的数量++
if (front < tail && cur >= q[front]) //队不为空且队首元素已经过期，就把队首元素从队首弹出（记住一定是队首，这很重要）
front++;
}
else if (c == 'C') {
++cnt;
scanf(" %s %d", s[cnt], &a[cnt]);
while (front < tail && a[q[tail - 1]] < a[cnt]) //队不为空且新插入的数比前面的数大，就把前面的数挤开
tail--;//从后面弹出
q[tail++] = cnt;
}
else {
if (front == tail)
printf("EMPTY\n");//如果为空
else
printf("%s\n", s[q[front]]);//不然输出队首
}
}
return 0;
}