本文主要是介绍栈复习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈复习笔记

都说了是复习笔记，所以不会有那些过于简单的东西。

一、普通栈

例题 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;
}

注意这个只能处理每个数字都是一位数的情况。如果想处理多位数，需要做一点小处理。

四、单调栈

这篇关于栈复习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！