栈与队列

2.栈与队列

1）数组模拟栈

主要思想：先进后出，设置一个数组存储数据，一个栈顶指针指向栈顶（初始化为0）

注意：数据出栈，只是指针单纯前移，无需在意数组还存储数据造成浪费

AcWing 828.模拟栈

#include <iostream>
#include <string>
using namespace std;
const int N=1000010;
int st[N],tt;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string op;
        cin>>op;
        if(op=="push")
        {
            int x;
            cin>>x;
            st[++tt]=x;
        }
        else if(op=="pop")
        {
            tt--;
        }
        else if(op=="query")
        {
            cout<<st[tt]<<endl;
        }
        else
        {
            if(tt>0) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

2）数组模拟队列

主要思想：先进先出，队尾插入，队头删除。设置一个数组存储数据，队头指针指向队列第一个元素（初始为0），队尾指针指向最后一个元素（初始为-1）

AcWing 829.模拟队列

#include <iostream>
#include <string>
using namespace std;
const int N=1000010;
int queue[N],hh,tt=-1;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string op;
        cin>>op;
        if(op=="push")
        {
            int x;
            cin>>x;
            queue[++tt]=x;
        }
        else if(op=="pop")
        {
            hh++;
        }
        else if(op=="query")
        {
            cout<<queue[hh]<<endl;
        }
        else
        {
            if(hh<=tt) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

3）单调栈

主要应用：对一个序列中的某个数，输出这个数左边第一个比他小的数

AcWing 830.单调栈

实现思路：

若采用暴力算法，直接两重循环逐个遍历比较，时间复杂度为O(n^2)。
采用构造单调栈的思想，降低时间复杂度为O(2n)。每次输入一个数据就判断它左边第一个比他小的数
- 比如对于序列[3, 4, 2, 7, 5]，求解每个数左边最近的且比它小的数（不存在则返回-1）。对于第i个元素，假设j < k < i如果a[k] < a[j]，那么a[j] 绝对不会是i的答案（即后来者比前面的小，则答案只会在后来者或者更后来的更小的数中选出，而不会在前面的数中得到，那么这个前面的数就可以除去）。以此构造一个栈，当后来者小于栈顶元素时，栈顶元素不断出栈（弹出栈的元素已失去角逐后续输出答案的机会，后来者居上），然后当前元素入栈（在栈顶），这样就构造了一个单调递增栈。
用数组构造一个栈，栈顶指针为tt。每次输出一个数据就将他与当前栈顶元素比较。
- 若栈不为空且栈顶元素大于当前数据，弹出栈，指针tt前移。若直到栈空，则左边不存在比当前元素小的数，输出-1；
- 若找到比当前元素的小的栈顶元素，即为答案输出栈顶元素
最后要将当前数入栈，因为当前元素也可能是后来者的答案

#include <iostream>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0,n;
int main(){
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        while(tt && stk[tt]>= x) tt--;
        if(tt) printf("%d ",stk[tt]);//当前数左端存在比当前数小的数
        else printf("-1");//不存在
        stk[++tt]=x;//当前数入栈
    }
    return 0;
    
}

4）单调队列

主要应用：求滑动窗口中的最小、最大值

AcWing 154. 滑动窗口

实现思路：以输出窗口最小值为例，考虑暴力算法，每滑动一次窗口，都比较k次，寻找到最小值，注意到如果左侧的数据大于右侧的数据，则可以在下一次滑动前删除左侧的数据，以此减少比较的次数，就能构造一个单调递增的队列，每次只需输出队头元素即为窗口内的最小值

设置一个滑动窗口队列(队头在左，队尾在右)，比较队尾和当前即将进入滑动窗口的数字大小，如果队尾数字大，则删除队尾。因此该队列中的数字全都小于待插入的数字，并且队头是最小的数字，再将该元素插入到队尾，最后输出队头即可。
使用一个q[]数组表示该队列，hh指向队头，tt指向队尾前一个位置，注意该数组存储的是对应元素的下标而不是实际元素值。
先判断队列队头元素是否还在当前窗口中(用数组下标比较)，若不在则队头指针后移，即寻找下一个窗口最小值。
循环比较待插入元素和队尾的关系，两种情况
- ①队列不为空且待插元素一直比队尾元素小，则队尾元素不断出队。若直到队列为空，退出当前循环，让待插入元素存入队尾（此时队列仅一个元素）
- ②若出现待插入元素比队尾元素大，那直接退出循环，让待插入元素存到队尾
- 最终就使得队列中的元素是递增的
当窗口中的元素已满足k个，满足输出条件，输出最小值，即队头q[hh]所指元素；最大值即队尾元素q[tt]。

其他理解：

AcWing 154. 滑动窗口---海绵宝宝来喽 - AcWing

#include <iostream>
using namespace std;
const int N= 1e6+10;
int a[N],q[N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    
    //输出窗口内最小值
    int hh=0,tt=-1;//队头队尾指针初始化
    for(int i=0;i<n;i++){
        //先判断队头元素是否还在窗口内
        while(hh<=tt && i-k+1>q[hh]) hh++; //这里用if也行 因为hh只会加一次
        //使队列元素单增
        while(hh<=tt && a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;//存的是下标
        //窗口内已有k个值，可以输出最小值
        if(i-k+1>0) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    
    
    //输出窗口内最大值
    hh=0,tt=-1;//队头队尾指针初始化
    for(int i=0;i<n;i++){
        //先判断队头元素是否还在窗口内
        if(hh<=tt && i-k+1>q[hh]) hh++;
        //使队列元素单减
        while(hh<=tt && a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;//存的是下标
        //窗口内已有k个值，可以输出最大值
        if(i-k+1>0) cout<<a[q[hh]]<<" ";
    }
    return 0;
}

编程笔记

探索