栈的应用【实验题】
使用栈实现后缀表达式计算，其中，在后缀表达式中，输入的数字为整数，且为正数，数字、符号之间用空格隔开，整个后缀表达式用“#”表示结束。其中，整个后缀表达式长度不超过200，每个数字位数不超过10。
提示：读取数据的过程中，可以利用栈处理每个数字。
输入样例：
11 2 3 + * #（注：对应的中缀表达式是11*(2+3)）
6 2 3 + * 5 / 7 - #（注：对应的中缀表达式是6*(2+3)/5-7）
输出样例：
55
-1
#include<iostream>
#include<string>
using namespace std;
struct stack
{int a[300];int index = -1;void instack(int x) //入栈操作{a[++index] = x;}void calculate(char k) //k是运算符{int sum = 0;int k1, k2;k1 = showtop(); outstack();k2 = showtop(); outstack();if (k == '+'){sum = k1 + k2;}else if (k == '-'){sum = k2 - k1;}else if (k == '*'){sum = k1 * k2;}else if (k == '/'){sum = k2 / k1;}instack(sum);}void outstack() //出栈{index--;}int showtop() //显示栈顶字符{return a[index];}
};
int main()
{stack f;string b;while (cin >> b && b != "#"){if (b == "+" || b == "-" || b == "*" || b == "/"){f.calculate(b[0]);}else{int num = stoi(b);f.instack(num);}}cout << f.showtop() << endl;return 0;
}整体还是很简单的，主要操作步骤如下
1.写一个栈的结构，这里面设置栈结构（a[]数组），index索引指向目前栈顶，并包含入栈、出栈、显示栈顶字符操作
2.输入字符
3.写运算calculate函数
要注意的问题是cin可以隔断输入的string b，此时比如单个输入的"11"就是要给字符串b
string b;while (cin >> b && b != "#"){if (b == "+" || b == "-" || b == "*" || b == "/"){f.calculate(b[0]);}else{int num = stoi(b);f.instack(num);}}同时calculate()也可以用switch写，更简洁一些
void calculate(char k) {int right = a[index--]; // 右操作数（栈顶）int left = a[index--]; // 左操作数（次栈顶）int sum = 0;switch(k) {case '+': sum = left + right; break;case '-': sum = left - right; break;case '*': sum = left * right; break;case '/': sum = left / right; break; // 修正为 left / right}a[++index] = sum; // 结果入栈}单调栈
这是种特殊的栈结构，其元素按照单调递增或单调递减的顺序排列
普通暴力方法是 O(n²) ，这个可以优化至 O(n)。
典型例题：
P5788 【模板】单调栈 - 洛谷
题目描述
给出项数为 n 的整数数列 a1…n。
定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，即 f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0。
试求出 f(1…n)。
输入格式
第一行一个正整数 n。
第二行 n 个正整数 a1…n。
输出格式
一行 n 个整数表示 f(1),f(2),…,f(n) 的值。
输入输出样例
输入
5 1 4 2 3 5
输出
2 5 4 5 0
说明/提示
【数据规模与约定】
对于 30% 的数据，n≤100；
对于 60% 的数据，n≤5×103 ；
对于 100% 的数据，1≤n≤3×106，1≤ai≤109。
整体做法就是，用栈来存储索引值，先从前往后遍历数列，遇到第 i 个元素 x ，让它和栈顶元素比较
- 如果栈顶元素小于它，就把栈顶元素踢出去，索引值 i 成为栈顶，此时栈顶索引对应的那个第一个比它大的索引就是 i 。
- 如果栈顶元素大于等于它，保存原来栈顶那个元素，把 i 直接加进来。
这样就形成了一个单调递减的栈，遍历每一个元素，后面的元素如果比它前面那个小就会进去待命，反正前面那个大数的结果不是后面那个小数，它只会在遇到比它大的数的时候才会找到答案，此时前面那堆小的答案也是那个新遇到的大数，所以就叽里咕噜全跑出栈来了。
还有一个比较形象的例子，这个题就好像是很多人同时向右看，求看到第一个比自己高的人的那个位置
为什么可以将复杂度降到 O(n)？
我想这是一个一边遍历数组一边比大小的过程，因为在遍历数组的同时本身就形成了一个递减的顺序，所以能够同时遍历数组 + 比大小，高
#include<iostream>
using namespace std;
int res[3000000]; //盛放答案 res[1]的值是第一个大于首元素的元素索引
int st[3000000]; //盛放索引，索引对应的值从大到小排列
int num[3000000]; //盛放原先的数列
int p = 0; //指针，首元素是1
int main()
{int n,x;cin >> n;for (int i = 1; i <= n; i++){cin >> x;num[i] = x;}for (int i = 1; i <= n; i++){while (p && num[i] > num[st[p]])
//num[st[p]]:表示当前st栈中栈顶元素（索引）对应的那个数值{int j = st[p]; //设一个整数j存索引值p--;res[j] = i;//该索引值第一个比它大的索引是i}p++;st[p] = i; //不管num[i]是大是小都要入栈}for (int i = 1; i <= n; i++)cout << res[i] << " ";return 0;
}出栈顺序判断
P4387 【深基15.习9】验证栈序列 - 洛谷
题目描述
给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据，不超过 5 组。
输入格式
第一行一个整数 q，询问次数。
接下来 q 个询问，对于每个询问：
第一行一个整数 n 表示序列长度；
第二行 n 个整数表示入栈序列；
第三行 n 个整数表示出栈序列；
输出格式
对于每个询问输出答案。
输入输出样例
输入
2 5 1 2 3 4 5 5 4 3 2 1 4 1 2 3 4 2 4 1 3
输出
Yes No
其实是一个模拟出栈过程的题
#include<iostream>
#include<string.h>
using namespace std;
int push[100000];
int pop[100000];
int q, n;
struct stack
{int st[100000];int ttop = -1; //top指向当前栈顶元素void popp() { ttop--; }void pushh(int x) { ttop++; st[ttop] = x; }bool isempty() { return ttop == -1 ? 1 : 0; }int top() { return st[ttop]; }
};
bool check() //模拟出栈过程
{int cnt = 0; //表示pop[]的索引stack s;for (int i = 0; i < n; i++){s.pushh(push[i]); //入栈while (s.top() == pop[cnt]) //当栈顶元素等于pop[cnt]的时候出栈{cnt++; //pop[]顺便往后移s.popp(); //出栈if (s.isempty())
//如果出完栈以后栈空了，就直接退出，因为原来那个s.top()不会判断栈有没有空，会出现错误{break;}}}if (s.isempty()) return true;else return false;while (!s.isempty()) //清空栈{s.popp();}}
int main()
{for (cin>>q; q; q--){cin >> n;for (int i = 0; i < n; i++) cin >> push[i];for (int i = 0; i < n; i++) cin >> pop[i];if (check()) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
