模拟栈 与 单调栈

发表于 更新于 分类于 ，
本文字数： 712

使用数组实现栈与单调栈的功能

st[N]作为栈数组，tt作为栈顶指针 (初始为0)

一、模拟栈

向栈顶插入一个元素（push）

1
st[++tt] = x;

弹出栈顶元素（pop）

1
tt--;

查询栈是否为空（empty）

1
2
3
4
if (!tt)
    cout << "YES";
else
    cout << "NO";

返回栈的大小（size）

1
cout << tt;

返回栈顶元素（top）

1
cout << st[tt];

二、单调栈

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int st[N], tt = 0;

int main()
{
    int x, m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        while (tt && st[tt] >= x)
            tt--;
        if (tt)
            cout << st[tt];
        else
            cout << -1;
        st[++tt] = x;
        cout << " ";
    }
    return 0;
}

思想：

按序检查每一个数，如果当前栈顶元素大于等于当前数则弹出当前栈顶元素并且继续检查新的栈顶元素，直到栈顶元素小于当前数或者栈中无元素 ，检查栈的大小不为零后输出栈顶元素，并且把当前数入栈 (最后栈中元素严格单调递增)