栈相关算法实战：模板实现与有效括号判定

栈相关算法实战

一、【模板】栈

1.1 题目描述

本题要求实现一个栈的基本操作，包括入栈、出栈、查询栈顶元素以及获取栈的大小。数据范围较大，需注意变量类型的选择。

1.2 算法思路

实现栈主要有两种方式：

1. 使用 C++ STL：利用 std::stack 容器，代码简洁，适合快速开发。
2. 数组模拟：手动维护栈顶指针和数组，理解底层原理，性能可控。

注意点：题目中涉及的数据范围可能超出 int 范畴，建议使用 unsigned long long 存储数值。

1.3 代码实现

1.3.1 STL 版本

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

typedef unsigned long long ULL;
const int N = 1e6 + 10;

int main() {
    int t;
    cin >> t;
    while (t--) {
        stack<ULL> stk;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            if (s == "push") {
                ULL x;
                cin >> x;
                stk.push(x);
            } else if (s == "pop") {
                if (stk.empty()) cout << "Empty" << endl;
                else stk.pop();
            } else if (s == "query") {
                if (stk.empty()) cout << "Empty" << endl;
                else cout << stk.top() << endl;
            } else if (s == "size") {
                cout << stk.size() << endl;
            }
        }
    }
    return 0;
}

1.3.2 数组模拟版本

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

typedef unsigned long long ULL;
const int N = 1e6 + 10;
ULL stk[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int size = 0; // 当前栈的元素个数
        int top = 0;  // 栈顶位置（1-based）
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            if (s == "push") {
                ULL x;
                cin >> x;
                stk[++top] = x;
            } else if (s == "pop") {
                if (!size) cout << "Empty" << endl;
                else top--;
            } else if (s == "query") {
                if (!size) cout << "Empty" << endl;
                else cout << stk[top] << endl;
            } else if (s == "size") {
                cout << size << endl;
            }
        }
    }
    return 0;
}

二、有效的括号

2.1 题目描述

给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

2.2 算法思路

利用栈的后进先出特性进行匹配：

1. 遍历字符串，遇到左括号直接入栈。
2. 遇到右括号时，检查栈是否为空：
   • 若为空，说明没有对应的左括号，返回 false。
   • 若不空，弹出栈顶元素并检查类型是否匹配。不匹配则返回 false。
3. 遍历结束后，若栈不为空，说明有未匹配的左括号，返回 false；否则返回 true。

2.3 代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == '(' || c == '[' || c == '{') {
                stk.push(c);
            } else {
                // 情况一：遇到右半部分但栈为空
                if (stk.empty()) return false;
                
                // 情况二：括号类型不匹配
                char top = stk.top();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
                
                // 情况三：匹配成功，弹出栈顶
                stk.pop();
            }
        }
        
        // 如果栈非空，说明还有左括号未匹配
        return stk.empty();
    }
};

---

以上两个案例展示了栈在基础数据结构中的典型应用。掌握栈的 STL 用法有助于提升编码效率，而数组模拟则能加深对内存管理的理解。在实际刷题中，注意边界条件（如空栈访问）是避免 Runtime Error 的关键。