單調(diào)隊(duì)列，顧名思義就是具有單調(diào)性的隊(duì)列O(∩_∩)O~，一般的隊(duì)列只能從隊(duì)尾入隊(duì)、隊(duì)首出隊(duì)；為了保持單調(diào)隊(duì)列的單調(diào)性，單調(diào)隊(duì)列除具有這兩種性質(zhì)外，還可以從隊(duì)尾出隊(duì)。
以單增的單調(diào)隊(duì)列為例，當(dāng)元素t要入隊(duì)時(shí)，先要從隊(duì)尾依次彈出所有>=t的元素，再將t加在隊(duì)尾。
舉個(gè)例子，如果序列：1 3 -1 -3 10要構(gòu)成單調(diào)隊(duì)列，
先將元素“1”放入隊(duì)列中，以初始化隊(duì)列，
接著元素“3”要入隊(duì)，隊(duì)尾元素“1”比“3”小，因此“3”可以直接入隊(duì)，隊(duì)列變?yōu)? 3，
接著“-1”要入隊(duì)，從隊(duì)尾依次彈出元素“3”“1”后將“-1”入隊(duì)，隊(duì)列變?yōu)?1，
同理“-3”入隊(duì)后，隊(duì)列變?yōu)?3,
“10”入隊(duì)后，隊(duì)列變?yōu)?3 10

單調(diào)隊(duì)列有什么用呢？看一道例題：（poj2823）
給定含有n個(gè)元素的無序序列a[]，和一個(gè)整數(shù)k，要求求出a[]中每連續(xù)k個(gè)元素組成的序列中的最小值（或最大值），這樣的值可能有1個(gè)或n-k+1個(gè)。
比較簡(jiǎn)單的方式，是每次都將k個(gè)數(shù)排序后輸出最值，具有O(N^2logN)的時(shí)間復(fù)雜度。但如果用單調(diào)隊(duì)列的話，我們可以在O(N)的時(shí)間內(nèi)求解，原因是每個(gè)元素最多入隊(duì)一次、出隊(duì)一次。
要解決該題，我們還要記錄每個(gè)元素在原序列中的位置p，每次只需從隊(duì)首開始找到跟當(dāng)前元素a[i]距離不大于k的元素（即是i-p+1<=k）輸出即可。
以下是zoj2823的部分代碼，只寫出了最小值的情況，最大值大的家自己想吧。

#include<stdio.h>
#include<stdlib.h>
#define LEN 1000010
typedef struct 
{
    int p;//記錄元素在原序列中的位置
    int num;//記錄該元素的值
}SQ; 
SQ q1[LEN];
int a[LEN];
int f, r;
int n, k;
void InQueue1(int i)
{
    while(q1[--r].num >= a[i] && r >= f);
    q1[++r].p = i;
    q1[r].num = a[i];
    r++;
}
int main()
{
    int i, j;
    int gard;
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    gard = 0;
    q1[1].p = 1;//初始化隊(duì)列，首元素入隊(duì)
    q1[1].num = a[1];
    r = 2;
    f = 1;
    for(i = 2; i <= k - 1 && i <= n; i++)//k有可能大于n
        InQueue1(i);    
    if(k == 1)//如果k == 1，第一個(gè)元素也要輸出
    {
        gard++;
        printf("%d", q1[f].num);
    }    
    for(; i <= n; i++)
    {
        InQueue1(i);
        while(i - q1[f].p + 1 > k)//確定隊(duì)首元素
            f++;
        if(gard++ == 0)
            printf("%d", q1[f].num);
        else
            printf(" %d", q1[f].num);    
    }
    if(k > n)
        printf("%d", q1[1].num);
    putchar(10);
    //system("pause");
}