C++ 栈 (Stack) 的基本用法与经典例题

栈的基本用法

1. 入栈：如 s.push(x)；
2. 出栈：如 s.pop()。注意：出栈操作只是删除栈顶的元素，并不返回该元素。
3. 访问栈顶：如 s.top()；
4. 判断栈空：如 s.empty()。当栈空时返回 true。
5. 访问栈中的元素个数：如 s.size()。

以下代码将详细解释栈在 C++ 中的用途。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // 1. 栈的声明和初始化
    stack<int> s; // 创建一个存储 int 类型的栈

    // 2. 向栈中添加元素 (压栈)
    s.push(10); // 栈底 -> [10]
    s.push(20); // 栈底 -> [10, 20]
    s.push(30); // 栈底 -> [10, 20, 30] <- 栈顶

    // 3. 访问栈顶元素
    cout << "栈顶元素：" << s.top() << endl; // 输出：30

    // 4. 移除栈顶元素 (弹栈)
    s.pop(); // 移除 30
    cout << "弹出后栈顶元素：" << s.top() << endl; // 输出：20

    // 5. 检查栈是否为空
    if (!s.empty()) {
        cout << "栈不为空" << endl;
    }

    // 6. 获取栈的大小
    cout << "当前栈的大小：" << s.size() << endl; // 输出：2

    // 7. 遍历栈 (注意：栈没有迭代器，只能边弹出边遍历)
    cout << "栈中元素 (从顶到底): ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop(); // 弹出当前栈顶元素
    }
    cout << endl;

    // 8. 清空栈
    // 实际上上面的循环已经清空了栈
    cout << "清空后栈的大小：" << s.size() << endl; // 输出：0

    // 9. 交换两个栈的内容
    stack<int> s1, s2;
    s1.push(1);
    s1.push(2);
    s1.push(3);
    s2.push(4);
    s2.push(5);
    s1.swap(s2);
    cout << "s1 栈顶：" << s1.top() << endl; // 输出：5
    cout << "s2 栈顶：" << s2.top() << endl; // 输出：3

    return 0;
}

有关栈的例题训练

有效的括号

LeetCode 20. 有效的括号

这是一个基础的栈操作题目。当遇到左括号时让其入栈，当遇到右括号时看是否有与之匹配的左括号，如果有就让它出栈，最后判断栈是否为空即可。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        if (s.empty()) return false;
        st.push(s[0]);
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == ')') {
                if (st.empty()) st.push(s[i]);
                else {
                    if (st.top() == '(') st.pop();
                    else st.push(s[i]);
                }
            } else if (s[i] == '}') {
                if (st.empty()) st.push(s[i]);
                else {
                    if (st.top() == '{') st.pop();
                    else st.push(s[i]);
                }
            } else if (s[i] == ']') {
                if (st.empty()) st.push(s[i]);
                else {
                    if (st.top() == '[') st.pop();
                    else st.push(s[i]);
                }
            } else {
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};

最长有效括号

LeetCode 32. 最长有效括号

用栈来实现。如果是左括号 (，就让其入栈。如果是右括号：

1. 先判断栈是否为空，如果不空，先将一个栈顶左括号弹出。若弹出后非空，就更新最大值 ans 为当前下标减去 s.top()，即更新一段新的连续的格式正确的长度值；若弹出后空，就可让此时的下标值减去 f 来更新最大值。
2. 如果栈一开始就空，就更新 f 的值，即新连续子串的初值 -1。

class Solution {
public:
    int longestValidParentheses(string s) {
        /* 任意前缀中 '(' 数量大于等于 ')' 的数量，左右括号数量相等 */
        stack<int> st;
        int ans = 0;
        int f = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                st.push(i); // 如果是左括号就压入栈中
            } else {
                // 如果是右括号
                if (!st.empty()) { // 若不为空
                    st.pop(); // 先将与之匹配的左括号弹出
                    if (!st.empty()) { // 若弹出后非空
                        ans = max(ans, i - st.top()); // 更新最大值，此时 i-st.top() 就是一段新的长度
                    } else { // 若弹出后栈空
                        ans = max(ans, i - f); // 则用 i-f 记录新的长度，并更新最大值
                    }
                } else { // 若栈一开始便是空的就更新起始位置
                    f = i;
                }
            }
        }
        return ans;
    }
};

括号的分数

LeetCode 856. 括号的分数

假设一个虚拟左括号用来存储最后的值。遍历字符串 s：

1. 当遇到左括号时，入栈，我们用 0 来记录分数，即将 0 入栈，因为只有一个左括号没有分数。
2. 遇到右括号时：
   • 如果只是 () 形式，即栈顶元素为 0，那么就是 1 分，将匹配过的这个左括号踢出栈，并将此时的分数加上一分赋值给前一个左括号。
   • 如果是 (A) 情况，即栈顶元素不为 0，同样将匹配过的这个左括号踢出栈，不同的是将此时的分数乘以 2 后赋值给前一个左括号。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 6;

void solve() {
    string s = "(()()())";
    stack<int> st;
    st.push(0); // 相当于虚拟的初始左括号
    for (auto c : s) {
        if (c == '(') {
            // 如果是左括号就让 0 入栈
            st.push(0);
        } else {
            // 如果是右括号再分情况讨论
            int t = st.top(); // 先将栈顶元素赋值给 t
            st.pop(); // 然后出栈
            if (t == 0) {
                // 如果是 () 第一种情况
                st.top() += 1;
            } else {
                // (A) 情况
                st.top() += 2 * t;
            }
        }
    }
    cout << st.top();
}

signed main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

Rails

NowCoder Rails

本题的意思就是给你两个序列，第一个序列按顺序进栈看情况出栈，看是否能满足第二个序列的顺序。这题主要注意输入输出格式。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, f, a[N];

int main() {
    int n_in;
    cin >> n_in;
    while (n_in) {
        while (n_in) {
            cin >> a[1];
            if (a[1] == 0) {
                // 如果是 0 直接无果
                cout << endl;
                break;
            } else {
                stack<int> s;
                while (!s.empty()) s.pop(); // 记得清栈
                for (int i = 2; i <= n_in; i++) cin >> a[i];
                for (int i = 1, j = 1; i <= n_in; i++) {
                    s.push(i);
                    while (!s.empty() && s.top() == a[j]) {
                        // 当栈顶元素符合时出栈
                        s.pop();
                        j++;
                    }
                }
                // 最后通过判断栈是否为空输出结果
                if (s.empty()) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
            cin >> n_in;
        }
    }
    return 0;
}

吐泡泡

NowCoder 吐泡泡

很巧妙的一道题。如果用字符串单独模拟来做的话比较麻烦，但如果用栈来模拟做就非常方便了。一开始栈为空，遍历字符串 s：

• 如果 s[i] 是小 o：
  • 如果栈不为空并且栈顶元素为小 o：那么二者就可以合并成为一个大 O。先让栈顶的小 o 出栈，然后再判断是否栈不空且新的栈顶元素为大 O。如果是就可以让栈顶的大 O 出栈，相当于二者抵消了；如果新的栈顶不是大 O 或者栈此时为空，就让新组成的这个大 O 入栈。
  • 如果栈为空或者栈顶元素不是小 o，就让小 o 入栈。
• 如果 s[i] 是大 O：
  • 如果栈不为空并且栈顶元素是大 O：二者可以抵消，所以栈顶元素出栈。
  • 如果栈为空或者栈顶元素不是大 O，让 s[i] 入栈。

最后将栈中元素依次出栈赋值给新的字符串，记得要翻转再输出，然后要清空。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 6;
string s, s1;
stack<char> st;

void solve() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'o') {
            if (!st.empty() && st.top() == 'o') {
                st.pop();
                if (!st.empty() && st.top() == 'O') {
                    st.pop();
                } else {
                    st.push('O');
                }
            } else {
                st.push('o');
            }
        }
        if (s[i] == 'O') {
            if (!st.empty() && st.top() == 'O') {
                st.pop();
            } else {
                st.push('O');
            }
        }
    }
    while (!st.empty()) {
        s1 += st.top();
        st.pop();
    }
    reverse(s1.begin(), s1.end());
    cout << s1 << endl;
    s1.clear();
}

signed main() {
    IOS;
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}