栈的深度解析：从基础实现到高级算法应用——C++实现与实战指南

一、栈的核心算法与应用场景

栈的先进后出特性使其在以下算法中表现优异：

括号匹配：校验表达式合法性。表达式求值：中缀转后缀，逆波兰表达式求值。深度优先搜索（DFS）：模拟递归调用。单调栈：解决区间最值问题。函数调用栈：模拟程序执行流程。

---

二、括号匹配算法 1. 问题描述

给定一个包含()、[]、{}的字符串，判断其是否合法。

2. 实现代码 #include <stack> #include <string> #include <unordered_map> bool isValidParentheses(const std::string& s) { std::stack<char> stack; std::unordered_map<char, char> mapping = { {')', '('}, {']', '['}, {'}', '{'} }; for (char ch : s) { if (mapping.count(ch)) { // 右括号 if (stack.empty() || stack.top() != mapping[ch]) { return false; } stack.pop(); } else { // 左括号 stack.push(ch); } } return stack.empty(); } 3. 关键点 使用哈希表存储括号映射关系。栈为空时遇到右括号直接返回false。最终栈为空才表示匹配成功。

---

三、表达式求值算法 1. 中缀转后缀（逆波兰表达式） #include <stack> #include <string> #include <vector> #include <cctype> std::vector<std::string> infixToPostfix(const std::string& expr) { std::vector<std::string> output; std::stack<char> operators; std::unordered_map<char, int> precedence = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3} }; for (size_t i = 0; i < expr.size(); ++i) { char ch = expr[i]; if (isdigit(ch)) { // 数字直接输出 std::string num; while (i < expr.size() && isdigit(expr[i])) { num += expr[i++]; } output.push_back(num); --i; } else if (ch == '(') { // 左括号入栈 operators.push(ch); } else if (ch == ')') { // 右括号弹出至左括号 while (!operators.empty() && operators.top() != '(') { output.push_back(std::string(1, operators.top())); operators.pop(); } operators.pop(); // 弹出左括号 } else { // 运算符 while (!operators.empty() && precedence[ch] <= precedence[operators.top()]) { output.push_back(std::string(1, operators.top())); operators.pop(); } operators.push(ch); } } // 弹出剩余运算符 while (!operators.empty()) { output.push_back(std::string(1, operators.top())); operators.pop(); } return output; } 2. 逆波兰表达式求值 #include <stack> #include <vector> #include <string> int evalRPN(const std::vector<std::string>& tokens) { std::stack<int> stack; for (const std::string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = stack.top(); stack.pop(); int a = stack.top(); stack.pop(); if (token == "+") stack.push(a + b); else if (token == "-") stack.push(a - b); else if (token == "*") stack.push(a * b); else stack.push(a / b); } else { stack.push(std::stoi(token)); } } return stack.top(); }

---

四、单调栈算法 1. 问题描述

给定一个数组，找到每个元素的下一个更大元素（Next Greater Element）。

2. 实现代码 #include <stack> #include <vector> std::vector<int> nextGreaterElements(const std::vector<int>& nums) { std::vector<int> result(nums.size(), -1); std::stack<int> stack; for (int i = 0; i < nums.size(); ++i) { while (!stack.empty() && nums[stack.top()] < nums[i]) { result[stack.top()] = nums[i]; stack.pop(); } stack.push(i); } return result; } 3. 关键点 栈中存储数组下标，便于更新结果。时间复杂度为O(n)，空间复杂度为O(n)。

---

五、深度优先搜索（DFS）与栈 1. 递归DFS void dfsRecursive(Node* node) { if (!node) return; // 处理当前节点 for (auto child : node->children) { dfsRecursive(child); } } 2. 迭代DFS（使用栈） void dfsIterative(Node* root) { if (!root) return; std::stack<Node*> stack; stack.push(root); while (!stack.empty()) { Node* curr = stack.top(); stack.pop(); // 处理当前节点 for (auto it = curr->children.rbegin(); it != curr->children.rend(); ++it) { stack.push(*it); // 子节点逆序压栈 } } }

---

六、函数调用栈模拟 1. 问题描述

模拟函数调用栈的行为，实现一个简单的解释器。

2. 实现代码 #include <stack> #include <string> #include <iostream> void executeFunction(const std::string& name) { std::cout << "Entering function: " << name << std::endl; // 模拟函数执行 std::cout << "Exiting function: " << name << std::endl; } void simulateCallStack() { std::stack<std::string> callStack; callStack.push("main"); executeFunction(callStack.top()); callStack.push("func1"); executeFunction(callStack.top()); callStack.push("func2"); executeFunction(callStack.top()); while (!callStack.empty()) { callStack.pop(); if (!callStack.empty()) { std::cout << "Returning to function: " << callStack.top() << std::endl; } } }

---

七、总结

栈作为一种基础数据结构，在算法设计中具有广泛的应用。通过深入理解栈的特性和应用场景，可以高效解决括号匹配、表达式求值、单调栈、DFS等问题。同时，栈在系统级编程（如调用栈）中也扮演着重要角色。掌握栈的实现和应用，是提升算法能力和编程水平的关键。