单调队列
单调队列是指：队列中元素之间的关系具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。
以单调不减队列为例：队列内的元素（e1，e2，e3...en）存在（e1<=e2<=e3<=...<=en）的关系，所以队首元素e1一定是最小的元素。与优先队列不同的是，当有一个新的元素e入队时，先要将队尾的所有大于e的元素弹出，以保证单调性，再让元素e入队尾。
例如这样一组数（1，3，2，1，5，6），进入单调不减队列的过程如下：
1入队，得到队列（1）；
3入队，得到队列（1，3）；
2入队，这时，队尾的的元素3>2，将3从队尾弹出，新的队尾元素1<2，不用弹出，将2入队，得到队列（1，2）；
1入队，2>1，将2从队尾弹出，得到队列（1，1）；
5入队，得到队列（1，1，5）；
6入队，得到队列（1，1，5，6）；
代码实现：
#include <iostream>using namespace std;class MonotonicQueue{#define MAXN 1000000public:MonotonicQueue(void){q = new int[MAXN+5];f = r = 0;}void push(const int val){while (r > f && q[r-1] > val)//弹出大于新元素的队尾元素{r--;}q[r++] = val;}int front(void){if (f < r){return q[f];}return 0;}void pop_front(void){if (f < r){f++;}}bool isEmpty(void){return f == r;}void clear(void){f = r = 0;}~MonotonicQueue(void){delete q;}private:int *q;int f;int r;};int main(void){MonotonicQueue mq;int n;while (cin >> n){int i;for (i = 0; i < n; i++){int a;cin >> a;mq.push(a);}while (!mq.isEmpty()){cout << mq.front() << endl;mq.pop_front();}mq.clear();}return 0;}访问队首和删除队首元素的时间复杂度为O(1)，在队尾加入元素的最坏情况下的时间复杂度为O(n)，n为队列当前长度。所以，可以采用二分查找，来确定新加入元素应该插入的位置。