队列 QUEUE

· · 科技·工程

队列 QUEUE

一、队列的定义：

是一种区别于栈但同样简单的数据结构，关键特征在于“先进先出”，即“先进去的先出来”。

队列就像一个羽毛球筒，一端只进不出，一端只出不进。

二、数组模拟队列的实现：

#include<iostream>
#include<cstring>
using namespace std;

string s;
int a[10010],l=-1,r=0;

int main(){
    int m,x;
    scanf("%d",&m);
    while(1){
        cin>>s;
        if(s=="push"){
            cin>>x,a[r++]=x;
        }else if(s=="pop"){
            l++;
        }else if(s=="empty"){
            if(r-l==1)  printf("YES\n");
            else    printf("NO\n");
        }else{
            printf("%d\n",a[l+1]);
        }

        printf("queue  :  ");                     //
        for(int i=l+1;i<r;i++)  printf("%d ",a[i]);      //
        printf("\n-----------------------------------\n"); //

    }

    return 0;
}

三、单调队列：

如其名，单调队列是具有单调性的一段队列，与单调栈类似，单调队列通常用于求一些数据特殊的最大最小值（见例题）。

例题

给定一个大小为 n≤ 10^6 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置 __ 最小值 _____ 最大值

[1 3 -1] -3 5 3 6 7__ -1____3

1 [3 -1 -3] 5 3 6 7 _ -3____ 3

1 3 [-1 -3 5] 3 6 7__-3____ 5

1 3 -1 [-3 5 3] 6 7_ -3____ 5

1 3 -1 -3 [5 3 6] 7__ 3____6

1 3 -1 -3 5 [3 6 7] __ 3___7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k ，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码实现，

#include<iostream>
using namespace std;
int n,k;
int a[100010],q[100010];  //这里是将数的下标存入队列
int main(){
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++)   scanf("%d",&a[i]);

    int h=0,t=-1;
    for(int i=0;i<n;i++){
        if(h<=t && i-k+1>q[h])  h++;
        while(h<=t && a[q[t]]>=a[i]) t--;  //单调性：单调递减
        q[++t]=i;
        if(i>=k-1)  printf("%d ",a[q[h]]);
    }
    h=0;t=-1;
    printf("\n");
    for(int i=0;i<n;i++){
        if(h<=t && i+1-k>q[h])  h++;
        while(h<=t && a[i]>=a[q[t]])    t--;  //单调性：单调递增
        q[++t]=i;
        if(i+1>=k)  printf("%d ",a[q[h]]);
    }
    return 0;
}

四、练习