模拟栈

int stk[N], tt = 0;

// 插入元素x
stk[++t] = x;

// 出栈
tt --;

// 栈是否为空
if(tt > 0) not empty;
else empty;

// 栈顶元素
stk[tt];

模拟队列

int q[N], hh = 0, tt = -1;

// 入队
q[++ tt] = x;

// 出队
hh ++;

// 判断是否为空
if(hh <= tt) not empty;
else empty;

// 取出队头元素
q[hh]

单调栈

单调栈使用场景有限，经典题型：给定一个序列，求序列中每个数左边离它最近的且比它小的数在哪个位置。

• 用栈存储第i个数的左边的所有元素，从栈顶往下找第一个比第i个数小的数

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

const int N = 100010;
int n;
int stk[N], tt;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if (tt) cout << stk[tt] << endl;
        else cout << -1 < ' ' << endl;
        stk[++ tt] = x;
    }
    return 0;
}