感谢lzxskjo先生让我“剽窃”他的劳动成果。当然，更要感谢被他剽窃了的那个人。

以下引用某论文：

一．       什么是单调（双端）队列

单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。

单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插入，它能够在队首、队尾同时进行删除。

【单调队列的性质】

一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：

1.      在原数列中的位置（下标）

2.      他在动态规划中的状态值

而单调队列则保证这两个值同时单调。

 从以上看，单调队列的元素最好用一个类来放，不这样的话，就要开两个数组。。。

 插入方法（以最大单调队列为例）：

在插入一个元素前，先判断队列是否为空（head<=tail），然后再判断队尾元素是否比要插入的元素小（q[tail].val<data[insert]），如果是的话，则将队尾元素删除（--tail）。

重复以上过程，直至为空或队尾元素比其大。

删除方法：

    这个要根据具体题目而定。在本题是如果当前的INDEX与队首的INDEX相差大于等于K，则删除。

1 #include 
      
        2 #define MAXN 1000001 3 int a[MAXN],bque[MAXN],sque[MAXN]; 4 int n,k; 5 void getmax() 6 { 7     int i,head = 1,tail = 1; 8     for(i = 1;i < k;i++) 9     {10         while(tail >= head && a[i] > a[bque[tail]])//队列不为空且当前元素大于队尾元素11             tail--;//删除队尾元素12         tail++;13         bque[tail] = i;14     }15     for(i = k;i <= n;i++)16     {17         while(tail >= head && i - bque[head] >= k)//队列不为空，且当前元素下标减去队首元素的下标>=k18             head++;//删除队首元素19         while(tail >= head && a[i] > a[bque[tail]])//队列不为空且当前元素大于队尾元素20             tail--;21         tail++;22         bque[tail] = i;23         if(i != n)24             printf("%d ",a[bque[head]]);25     }26     printf("%d\n",a[bque[head]]);27 }28 void getmin()29 {30     int i,head = 1,tail = 1;31     for(i = 1;i < k;i++)32     {33         while(tail >= head && a[i] < a[sque[tail]])34             tail--;35         tail++;36         sque[tail] = i;37     }38     for(i = k;i <= n;i++)39     {40         while(tail >= head && i - sque[head] >= k)41             head++;42         while(tail >= head && a[i] < a[sque[tail]])43             tail--;44         tail++;45         sque[tail] = i;46         if(i != n)47             printf("%d ",a[sque[head]]);48     }49     printf("%d\n",a[sque[head]]);50 }51 int main()52 {53     while(~scanf("%d%d",&n,&k))54     {55         for(int i = 1;i <= n;i++)56             scanf("%d",&a[i]);57         getmin();58         getmax();59     }60     return 0;61 }