模拟栈

栈的特性为先入后出，后入先出

如何进行模拟

根据栈的特性，我们会发现在栈弹出元素的时候弹出的都是后加入进来的

所以我们可以定义一个指针用来索引栈顶

操作流程

push元素，我们只需要将栈针向后进行移动

pop元素，只需要将指针前移

empty操作只需要判断栈针是否为0

query操作只需要打印栈针对应的元素

完整AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int st[N];
int zz = 0;
int main(){
    int m,t;string op;
    cin >> m;
    while(m--) {
        cin >> op;
        if(op == "push") {
            cin >> t;
            st[++zz] = t;
        }else if(op == "pop") {
            zz--;
        }else if(op == "empty"){
            if(zz) cout << "NO" << endl;
            else cout << "YES" << endl;
        }else {
            cout << st[zz] << endl;
        }
    }
    return 0;
}

模拟队列

队列的特征：先入先出，后入后出

我们pop元素的时候，我们发现我们想要删除的元素是先前进入的元素，所以我们需要定位这个位置，需要新开一个指针st，当pop元素的是否只需要让st++即可，我们队列中的元素也就是在[st,ed]这段区间内

队列操作

push 数组[++ed]来进行加入

pop 删除头部元素，st++

empty 判断 st <= ed

完整Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int st = 1,ed = 0;
int q[N];

int main(){
    int m,t;string op;
    cin >> m;
    while(m--) {
        cin >> op;
        if(op == "push") {
            cin >> t;
            q[++ed] = t;
        }else if(op == "empty") {
            if(st <= ed) cout << "NO" << endl;
            else cout << "YES" << endl;
        }else if(op == "pop") {
            st++;
        }else {
            cout << q[st] << endl;
        }
    }
    return 0;
}

单调栈

单调栈因名而意，单调 + 栈结构

主要用来处理当栈中的元素都满足统一特性，并且这种特性可以呈现出单调性的特点

例题：输入一个n，接下来输入n个数，要求每一个数左侧距离最近并且小于当前点的值，如果找不到比当前点小的值那么输出-1

思路

这很显然满足了单调性的特点，使用数组模拟栈，每一次添加元素判断该元素的左侧距离最近且小于当前点的值，如果从这个点向左侧出发遇到了比当前点更大的点，那么完全可以pop出这个点

解释：为什么可以pop

ex：3 4 2 7 5 10 我们从5开始向左出发，发现7比5大，pop7，因为后面如果出现了一个数能比7大，那么它肯定优先找5，因为距离近，并且还小于当前这个点

完整Coding

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int st[N];
int n,tt,t;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> t;

        while(tt && st[tt] >= t) tt--;
        if(tt) cout << st[tt] << " ";
        else cout << -1 << " ";

        st[++tt] = t;
    }


    return 0;
}

单调队列

单调队列和单调栈相似，都有单调性，主要用来对滑动窗口这一类题进行优化

例题

题目介绍

首先输入一个n，代表数组的大小，接下来输入一个k，代表滑动窗口的大小，接着我们遍历数组，从头到尾对滑动窗口里面的数取最小值和最大值，最终进行打印，滑动窗口是从头滑动到尾的，并且滑动窗口的大小被数组包含

思路

我们可以使用队列来解决，当然这里面的栈需要我们自己去模拟，设置st = 0，ed = -1，接着我们不停的向滑动窗口里面添加数，我们需要注意添加进来的元素需要判断和队列尾部的元素相比较，如果比它小的话，我们需要回退尾指针并且将新的元素添加进来，最终保证每一次滑动窗口都是在队头取最小值

前置条件

int a[N]; //用来存数
int b[N]; //用来存队列中元素的下标
for(int i = 1;i <= n;i++) cin >> a[i]; //题目要求存值
int st = -1,ed = 0; //队列前置准备

构造单调队列

for(int i = 1;i <= n;i++) {
  	
		while(st <= ed && a[i] < a[q[ed]]) ed--;
		q[++ed] = i;
		if(i - k + 1 > q[st]) st++;
		if(i >= k) cout << a[q[st]] << " ";
}