题目描述

1.栈：
模拟格式：

 stk[],tt;

操作集：

push pop query empty
push:stk[++tt]=x;
pop:tt--;
empty:tt!=0;
query:stk[tt];

2.队列
模拟格式：

que[]; hh,tt;

操作集：

push pop query empty
push:que[tt++]=x;
pop:hh++;
empty:hh!=tt;
query:stk[hh];

3.单调栈：
应用场景：寻找一个数左边或者右边比他大或者小的数
例子：寻找每一个数的左边比他小的第一个数
思路：设置一个栈用来存储，如果stk[tt]>=x 在之后的操作中x会永远优先于stk[tt]输出，（就比如下一次操作中x1要 寻找左边比他小的第一个数如果stk[tt]<x1那么x必定也小于x1并且会优先于stk[tt]输出，所以stk[tt]没有用处 所以将stk[t–]出栈，

算法1

(模拟栈)

#include<iostream>

using namespace std;

int const maxn=1e5+10;
int stk[maxn],tt;

void push(int x)
{
    stk[++tt]=x;
}

void empty()
{
    if(tt!=0) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}
void pop()
{
    tt--;
}
void query()
{
    cout<<stk[tt]<<endl;
}

int main()
{
    int n; cin>>n;
    while(n--)
    {
        string aim;
        cin>>aim;
        if(aim=="push")
        {
            int x; cin>>x;
            push(x);
        }
        else if(aim=="pop")
        {
            pop();
        }
        else if(aim=="empty")
        {
            empty();
        }
        else if(aim=="query")
        {
            query();
        }
    }
}

算法2

(模拟队列)

#include<iostream>

using namespace std;

int const maxn =1e5+10;

int que[maxn],hh,tt;

void push(int x)
{
    que[tt++]=x;
}
void empty()
{
    if(tt!=hh) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}
void pop()
{
    hh++;
}
void query()
{
    cout<<que[hh]<<endl;
}


int main()
{
    int n; cin>>n;
    while(n--)
    {
        string aim; cin>>aim;
        if(aim=="push")
        {
            int x; cin>>x;
            push(x);
        }
        else if(aim=="pop")
        {
            pop();
        }
        else if(aim=="empty")
        {
            empty();
        }
        else if(aim=="query")
        {
            query();
        }
    }
}

算法3

(单调栈)

#include<iostream>

using namespace std;

int const maxn=1e5+10;
int stk[maxn],tt;

int main()
{
    int n; cin>>n;
    while(n--)
    {
        int t; cin>>t;
        while(stk[tt]>=t) tt--;
        if(tt!=0) cout<<stk[tt]<<" ";
        else cout<<"-1"<<" ";
        stk[++tt]=t;
    }
}

算法3

(单调栈)

#include<iostream>

using namespace std;

int const maxn=1e5+10;
int stk[maxn],tt;

int main()
{
    int n; cin>>n;
    while(n--)  
    {
        int t; cin>>t;                  
        while(stk[tt]>=t) tt--;         //将stk[tt]>=t 的数据全部出栈
        if(tt!=0) cout<<stk[tt]<<" ";   //当tt!=0 说明stk[tt]就是t左侧比他小的第一个数；
        else cout<<"-1"<<" ";           //当队列为空表示没有找到
        stk[++tt]=t;                    //将t入队 
    }
}

算法4

(单调队列)