栈的应用【实验题】
使用栈实现后缀表达式计算，其中，在后缀表达式中，输入的数字为整数，且为正数，数字、符号之间用空格隔开，整个后缀表达式用“#”表示结束。其中，整个后缀表达式长度不超过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)。
典型例题：
题目描述
给出项数为 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;
}出栈顺序判断
题目描述
给出两个序列 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;
}