栈复习笔记
都说了是复习笔记，所以不会有那些过于简单的东西。
一、普通栈
例题 1.1 包含min函数的栈
原题目链接：Link。
可以发现我们只需要实现 getMin 函数即可。那我们如何实现呢？我们可以再用一个栈，存储每个元素入栈之后整个栈的最小值。代码如下：
class MinStack {
public:
/** initialize your data structure here. */
stack<int> a, b;
MinStack() {
}
void push(int x) {
a.push(x); // 直接插入
b.push(b.empty() ? x : min(b.top(), x)); // 如果 b 为空直接插入，否则将 x 与插入前的最小值比较取 min，插入 b 中
}
void pop() {
a.pop(); b.pop(); // 出栈
}
int top() {
return a.top(); // a 的栈顶元素
}
int getMin() {
return b.top(); // b 的栈顶元素，即当前最小值
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
例题 1.2 溶液模拟器
原题目链接：Link。
按照题意来即可。这里还维护了溶质质量 \(M\)。
#include <bits/stdc++.h>
using namespace std;
#define PDD pair<double, double>
const int MAXN = 25;
int n;
string s;
char op;
double V, C, M, v, c, m;
stack<PDD > a;
PDD t;
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
cin >> V >> C;
a.push(make_pair(V, C));
M = V * C / 100;
cin >> n;
while (n--) {
getline(cin, s);
cin >> op;
if (op == 'P') {
cin >> v >> c;
t = a.top();
V += v;
M += v * c / 100;
C = M / V * 100;
a.push(make_pair(V, C));
}
else if (a.size() > 1) {
a.pop();
t = a.top();
V = t.first;
M = t.first * t.second / 100;
C = M / V * 100;
}
printf("%.0lf %.5lf\n", V, C);
}
return 0;
}
例题 1.3 火车进出栈问题
原题目链接：Link。
可以发现，这就是卡特兰数（Catalan 数）的第 \(n\) 项，即 \(C_{2n}^n \over n + 1\)。但是这道恶心的题需要用高精怎么办？
人生苦短，我用 py。
我们可以写成另一种形式：
\[Cat_n = {C_{2n}^n \over n + 1} = \frac{\prod_{i=n+1}^{i=2n}i}{(\prod_{i=1}^{i=n}i) \times (n + 1)} = \frac{\prod_{i=n}^{i=2n}i}{\prod_{i=1}^{i=n}i}=\frac{\prod_{i=1}^{i=2n}i}{(\prod_{i=1}^{i=n}i)^2}={(2n)! \over n!} \]然后我们可以用 math.factorial 快速计算阶乘，代码如下：
import math
n = int(input())
a = math.factorial(n * 2)
b = math.factorial(n)
print(a // b // b // (n + 1))
二、对顶栈
例题 2.1 编辑器
原题目链接：Link。
我们可以使用对顶栈。用一个栈存储光标前的所有数，另一个栈存储光标后的所有数。另外，用一个 \(s\) 数组存储前缀和，\(f\) 数组存前缀和的最大值。代码如下：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, x, s[MAXN], f[MAXN] = {int(-1e9)};
char op;
stack<int> a, b;
string str;
int main() {
cin >> n;
while (n--) {
getline(cin, str);
cin >> op;
if (op == 'I') {
cin >> x;
a.push(x);
int k = a.size();
s[k] = s[k - 1] + x; // 求新的前缀和
f[k] = max(f[k - 1], s[k]); // 取最大值
}
else if (op == 'D') {
if (!a.empty()) a.pop(); // 如果不为空，删除栈顶元素
}
else if (op == 'L') {
if (!a.empty()) {
b.push(a.top());
a.pop();
} // 如果不为空，将光标向左移动，等价于取出 a 的栈顶元素，压入 b 中
}
else if (op == 'R') {
if (!b.empty()) {
a.push(b.top()); b.pop();
int k = a.size();
s[k] = s[k - 1] + a.top();
f[k] = max(f[k - 1], s[k]);
} // 与 L 情况类似。注意这时 a 相当于新加入了一个元素，需要维护前缀和
}
else {
cin >> x;
cout << f[x] << endl;
} // 直接输出
}
return 0;
}
三、表达式计算
栈可以用来做表达式的运算。当然后缀表达式是栈最喜欢的（笑）。
例题 3.1 后缀表达式
原题目链接：Link。
模版题，代码如下：
#include <bits/stdc++.h>
using namespace std;
stack<int> n;
char op;
int num, a, b;
int main() {
while (true) {
op = getchar();
if (op >= '0' && op <= '9') num = num * 10 + (op - '0');
// 是数字就加上
else if (op == '.') n.push(num), num = 0;
// 是点，说明数字输入完毕，将 num 压入栈中
else if (op != '@') {
// op 是运算符
a = n.top(); n.pop();
b = n.top(); n.pop();
// 取出栈顶和取出栈顶后的栈顶
// 注意如 1 2 -，取出 a = 2 b = 1，要反过来运算
switch (op) {
case '+':
n.push(b + a);
break;
case '-':
n.push(b - a);
break;
case '*':
n.push(b * a);
break;
case '/':
n.push(b / a);
break;
}
} // 很早以前的代码，竟然能看到 switch /jk
else break;
}
cout << n.top() << endl;
return 0;
}
那么，我们怎么实现中缀表达式转后缀表达式呢？代码如下：
#include <bits/stdc++.h>
using namespace std;
string s;
stack<char> a;
int v(char ch) {
if (ch == '+' || ch == '/') return 3;
else if (ch == '(') return 1;
return 2;
} // 得到运算符的权值
int main() {
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (isdigit(s[i])) putchar(s[i]), putchar(' ');
else if (s[i] == '(') a.push('(');
else if (s[i] == ')') {
while (!a.empty() && a.top() != '(') putchar(a.top()), putchar(' '), a.pop();
a.pop();
}
else {
while (!a.empty() && v(a.top()) >= s[i]) putchar(a.top()), putchar(' '), a.pop();
a.push(s[i]);
}
}
while (!a.empty()) putchar(a.top()), putchar(' '), a.pop();
return 0;
}
注意这个只能处理每个数字都是一位数的情况。如果想处理多位数，需要做一点小处理。