当前位置：首页 > news >正文

单调栈《数组模拟》

news 来源：原创 2024/9/20 15:41:49

#include <iostream>using namespace std;const int N = 100010;int m;
int stk[N], tt;int main()
{cin >> m;while (m -- ){string op;int x;cin >> op;if (op == "push"){cin >> x;stk[ ++ tt] = x;//插入x}else if (op == "pop") tt -- ;//弹出  stk[tt]取出栈顶元素else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;else cout << stk[tt] << endl;//判断是不是空的// if(tt>0)// cout << "不空";// else // cout << "空"}return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int n;            // n表示输入的元素个数
int stk[N], tt;   // stk[]数组模拟栈, tt表示栈顶指针int main()
{cin >> n;     // 读取元素的个数for(int i = 0; i < n; i++){int x;cin >> x; // 读取当前元素x// 核心部分：维护栈的过程// 如果栈不为空，并且栈顶元素大于等于当前元素x，则弹出栈顶元素while(tt && stk[tt] >= x) tt--;// 如果栈中还有元素，说明栈顶元素就是最近的一个比当前元素x小的数if(tt) cout << stk[tt] << " ";else // 否则栈为空，说明前面没有比当前元素小的数cout << -1 << " ";// 将当前元素x压入栈中，栈顶指针tt加1stk[++tt] = x;}return 0;
}

执行过程
// 初始状态
// n = 5（表示输入的元素个数为5）。
// 栈 stk[] 和栈顶指针 tt 初始化为空，tt = 0。
// 逐步执行过程
// 处理第1个元素 3：

// 读取 x = 3。
// 当前栈为空（tt = 0），没有比 3 小的数，输出 -1。
// 将 3 压入栈中，栈状态为 [3]，栈顶指针 tt = 1。
// 处理第2个元素 4：

// 读取 x = 4。
// 栈顶元素 stk[tt] = 3 小于 4，输出 3。
// 将 4 压入栈中，栈状态为 [3, 4]，栈顶指针 tt = 2。
// 处理第3个元素 2：

// 读取 x = 2。
// 栈顶元素 stk[tt] = 4 大于 2，弹出 4，栈状态变为 [3]，栈顶指针 tt = 1。
// 栈顶元素 stk[tt] = 3 也大于 2，继续弹出 3，栈状态变为 []，栈顶指针 tt = 0。
// 栈为空，输出 -1。
// 将 2 压入栈中，栈状态为 [2]，栈顶指针 tt = 1。
// 处理第4个元素 7：

// 读取 x = 7。
// 栈顶元素 stk[tt] = 2 小于 7，输出 2。
// 将 7 压入栈中，栈状态为 [2, 7]，栈顶指针 tt = 2。
// 处理第5个元素 5：

// 读取 x = 5。
// 栈顶元素 stk[tt] = 7 大于 5，弹出 7，栈状态变为 [2]，栈顶指针 tt = 1。
// 栈顶元素 stk[tt] = 2 小于 5，输出 2。
// 将 5 压入栈中，栈状态为 [2, 5]，栈顶指针 tt = 2。
// 最终输出
// 对于每个元素，输出结果分别是：-1 3 -1 2 2。

// 栈的状态变化
// 输入 3：输出 -1，栈 [3]
// 输入 4：输出 3，栈 [3, 4]
// 输入 2：输出 -1，栈 [2]
// 输入 7：输出 2，栈 [2, 7]
// 输入 5：输出 2，栈 [2, 5]