栈

栈的特点是先进先出，是一种基础的数据结构，可以用来解决一些特定的问题

实现

可以调用stl库的stack，也可以使用数组和一个变量tt来模拟，tt用来记录栈顶

数组模拟栈

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

const int N=1e6+10;

ll x;
int m,n;
int b[N];

void push(ll x){
    b[++n]=x;
}

void pop(){
    n--;
}
bool empty(){
    if(n>0) return true;
    else return false;
}
int query(){
    return b[n];
}
int main(){
    cin>>m;
    while(m--){
        string a;
        cin>>a;
        if(a=="push"){
            int x;
            cin>>x;
            push(x);
        }
        else if(a=="pop"){
            pop();
        }
        else if(a=="empty"){
            bool ans=empty();
            if(!ans) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else{
            int ans=query();
            cout<<ans<<endl;
        }
    }
    return 0;
}

题目

表达式求值 此题思路式通过栈模拟中缀表达式树，一个栈存放操作符，一个栈存放数字

#include <iostream>
#include <stack>
#include <unordered_map>
#include <cstring>
#include <algorithm>
using namespace std;

// 存放计算的数字
stack<int> num;
// 存放运算符和括号
stack<char> op;

void eval()
{
    // 注意取值顺序，由于栈的特性要先取b后取a，再减法和除法会有影响
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
    
}

int main()
{
    string s;
    cin>>s;
    // 定义运算符的优先级
    unordered_map<char,int> pr={{'+',1},{'-',1},{'*',2},{'/',2}};
    for(int i=0;i<s.size();i++)
    {
        auto c=s[i];
        // 取得整个数字，存入栈
        if(isdigit(c))
        {
            int x=0,j=i;
            while(j<s.size()&&isdigit(s[j]))
                x=x*10+s[j++]-'0';
            i=j-1;
            num.push(x);
        }
        // 左括号直接存入
        else if(c=='(') op.push(c);
        else if(c==')')
        {
            // 将括号内的运算全部算出
            while(op.top()!='(') eval();
            op.pop();
        }
        else
        {
            // 如果当前的符号栈内的运算符优先级大于当前的运算符，则代表栈顶符号的子树已经全部计算完毕
            while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    //计算剩余的数字
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

单调栈

单调栈最常用的用法是求某一个序列左边第一个比它小的元素之类的题，只需要维护一个单调栈，在每次扫描到一个数时判断它和栈顶元素的大小，如果小于栈顶元素那么我们可以就可以将栈顶pop，继续向下判断，直到找到比他小的元素，之后将它压入栈，这样就在扫描的过程中可以保证栈的单调性

题目和讲解

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

int main() {
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        while(m.size()&&m.top()>=x) m.pop();
        if(m.size()) cout<<m.top()<<" ";
        else cout<<"-1"<<" ";
        m.push(x);
    }
    return 0;
}

队列

队列和栈类似，只不过是先进先出

实现

使用两个变量模拟队头和队尾

数组模拟队列

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

const int N=1e6+10;

int a[N];
int first,last=-1;

int main(){
    string b;
    int m;
    cin>>m;
    while(m--){
    cin>>b;
    if(b=="pop"){
        first++;
    }
    else if(b=="push"){
        int x;
        cin>>x;
        a[++last]=x;
    }
    else if(b=="empty"){
        if(last-first<0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    else {
        cout<<a[first]<<endl;
    }
    }
    return 0;
}

题目

滑动窗口

通过每次的扫描元素和队尾元素的比较，来保证队列的单调性，使得在O(1)的复杂度内完成一次查询操作

#include <bits/stdc++.h>                
#define ll long long

using namespace std;
const int N=1000010;

int a[N],q[N];//q是队列，存放a数组的下标



int main() {
    int n,k;
    cin>>n>>k;                        //k是题目给的窗口大小
    for(int i=0;i<n;i++) cin>>a[i];
    int h=0,t=-1;                  //头h，，，t尾
    for (int i = 0; i <n; i ++ ){
        //h<=t是队列不为空的条件，i-k+1是窗口的左端应该位于的坐标，如果说大于q【h】，那么队列左端就应该更新
        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) cout<<a[q[h]]<<" ";//判断条件是是指应该等到窗口内元素大于3个是在输出
    }
    cout<<endl;
    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) cout<<a[q[h]]<<" ";
    }

    return 0;
}