单调队列，顾名思义就是具有单调性的队列O(∩_∩)O~，一般的队列只能从队尾入队、队首出队；为了保持单调队列的单调性，单调队列除具有这两种性质外，还可以从队尾出队。
以单增的单调队列为例，当元素t要入队时，先要从队尾依次弹出所有>=t的元素，再将t加在队尾。
举个例子，如果序列：1
3 -1 -3
10要构成单调队列，
先将元素“1”放入队列中，以初始化队列，
接着元素“3”要入队，队尾元素“1”比“3”小，因此“3”可以直接入队，队列变为1
3，
接着“-1”要入队，从队尾依次弹出元素“3”“1”后将“-1”入队，队列变为-1，
同理“-3”入队后，队列变为-3,
“10”入队后，队列变为-3
10
单调队列有什么用呢？看一道例题：（poj2823）
给定含有n个元素的无序序列a[]，和一个整数k，要求求出a[]中每连续k个元素组成的序列中的最小值（或最大值），这样的值可能有1个或n-k+1个。
比较简单的方式，是每次都将k个数的最值找出，具有O(K*n)的时间复杂度。但如果用单调队列的话，我们可以在O(n)的时间内求解，原因是每个元素最多入队一次、出队一次。
要解决该题，我们还要记录每个元素在原序列中的位置p,每次只需从队首开始找到跟当前元素a[i]距离不大于k的元素（即是i-p+1<=k）输出即可。
一、
什么是单调（双端）队列
单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。
单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插入，它能够在队首、队尾同时进行删除。
【单调队列的性质】
一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：
1、在原数列中的位置（下标）
2、 他在动态规划中的状态值
而单调队列则保证这两个值同时单调。
从以上看，单调队列的元素最好用一个类来放，不这样的话，就要开两个数组。。。
单调队列：单调队列 即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。单调队列的具体作用在于，由于保持队列中的元素满足单调性，对手元素便是极小值（极大值）了。
原文：http://www.cnblogs.com/zhaoxinshanwei/p/3539029.html