2.2 栈

2.1.1 模拟栈

概念：

• 栈是一种先进后出的数据结构
• 只允许对栈顶元素操作，不允许遍历

操作思想

• 利用静态数组模拟栈
• 实现进栈，出栈等操作

模板

const int N=1e6+10;  

int stk[N],tt=0;  //stk[N]用于模拟栈，类型可自定义，tt表示栈顶

void add(int x){  //栈顶插入x
    stk[++tt]=x;
}

int top(){  //返回栈顶元素
    return stk[tt];
}

void pop(){  //弹出栈顶元素
    tt--;
}

bool empty(){  //判断是否为空
    return tt==0;  //若为空则返回true
}

例题 828.模拟栈

原题链接

描述

实现一个栈，栈初始为空，支持四种操作：

1. push x – 向栈顶插入一个数 x；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围
1≤M≤100000,
1≤x≤109
所有操作保证合法。

输入样例：

输出样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int stk[N],tt=0;

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

void pop(){
    tt--;
}

bool empty(){  //判断是否为空
    return tt==0;  //若为空则返回true
}

int top(){
    return stk[tt];
}

int main()
{
    int n;
    cin>>n;

    while(n--){
        string s;
        cin>>s;
        if(s=="push"){
            int x;
            cin>>x;
            add(x);
        }
        else if(s=="pop"){
            pop();
        }
        else if(s=="empty"){
            if(empty()){
                cout<<"YES"<<endl;
            }
            else cout<<"NO"<<endl;
        }
        else if(s=="query"){
            cout<<top()<<endl;
        }
    }

    return 0;

}

2.1.2 单调栈

概念

• 栈中的元素满足单调性质

应用

• 常见模型：找出每个数左边离它最近的比它大/小的数

例题 830. 单调栈

原题链接

描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式
第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：

输出样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int stk[N],tt=0;

int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        while(tt>0&&x<=stk[tt]) tt--;  //当栈不为空时，判断x与栈顶元素关系，若构成逆序，则删除栈顶元素
        if(tt>0) cout<<stk[tt]<<" ";
        else cout<<-1<<" ";
        stk[++tt]=x;
    }

    return 0;

}