C++ STL栈stack提供后进先出的数据结构，支持push、pop、top、empty和size操作，适用于表达式求值、浏览器前进后退、括号匹配等场景，但不具线程安全性，需用互斥锁保证多线程安全。
C++ STL 栈 stack 提供了一种后进先出（LIFO）的数据结构，用于管理元素的顺序。它主要用于需要回溯、撤销或跟踪历史记录的场景。
栈 stack 的操作包括：
-
push(element)
: 将元素压入栈顶。
-
pop()
: 移除栈顶元素。
-
top()
: 返回栈顶元素（但不移除）。
-
empty()
: 检查栈是否为空。
-
size()
: 返回栈中元素的数量。
#include <iostream> #include <stack> int main() { std::stack<int> myStack; myStack.push(10); myStack.push(20); myStack.push(30); std::cout << "栈顶元素: " << myStack.top() << std::endl; // 输出 30 myStack.pop(); // 移除栈顶元素 std::cout << "栈顶元素: " << myStack.top() << std::endl; // 输出 20 std::cout << "栈的大小: " << myStack.size() << std::endl; // 输出 2 while (!myStack.empty()) { std::cout << "栈顶元素: " << myStack.top() << std::endl; myStack.pop(); } std::cout << "栈是否为空: " << myStack.empty() << std::endl; // 输出 1 (true) return 0; }
C++ STL 栈 stack 在实际编程中有很多应用场景，下面介绍几个常见的例子。
如何使用 C++ STL 栈 stack 实现表达式求值？
立即学习“C++免费学习笔记（深入）”；
表达式求值是一个经典的栈的应用。我们可以使用两个栈，一个操作数栈和一个运算符栈。从左到右扫描表达式：
- 如果遇到操作数，则将其压入操作数栈。
- 如果遇到运算符，则：
- 如果运算符栈为空，或者当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符压入运算符栈。
- 否则，弹出运算符栈顶的运算符，从操作数栈中弹出两个操作数，执行运算，将结果压入操作数栈，然后重复步骤 2。
- 扫描完成后，如果运算符栈不为空，则依次弹出运算符，从操作数栈中弹出两个操作数，执行运算，将结果压入操作数栈。
- 最后，操作数栈中剩下的唯一元素就是表达式的结果。
#include <iostream> #include <stack> #include <string> #include <cctype> // isdigit int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; } int evaluate(int a, int b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: return 0; } } int evaluateExpression(const std::string& expression) { std::stack<int> operands; std::stack<char> operators; for (size_t i = 0; i < expression.length(); ++i) { if (isspace(expression[i])) continue; if (isdigit(expression[i])) { int num = 0; while (i < expression.length() && isdigit(expression[i])) { num = num * 10 + (expression[i] - '0'); i++; } i--; // 回退一个字符，因为循环会再次递增 operands.push(num); } else if (expression[i] == '(') { operators.push(expression[i]); } else if (expression[i] == ')') { while (!operators.empty() && operators.top() != '(') { char op = operators.top(); operators.pop(); int b = operands.top(); operands.pop(); int a = operands.top(); operands.pop(); operands.push(evaluate(a, b, op)); } operators.pop(); // Pop the '(' } else { while (!operators.empty() && precedence(expression[i]) <= precedence(operators.top())) { char op = operators.top(); operators.pop(); int b = operands.top(); operands.pop(); int a = operands.top(); operands.pop(); operands.push(evaluate(a, b, op)); } operators.push(expression[i]); } } while (!operators.empty()) { char op = operators.top(); operators.pop(); int b = operands.top(); operands.pop(); int a = operands.top(); operands.pop(); operands.push(evaluate(a, b, op)); } return operands.top(); } int main() { std::string expression = "10 + 2 * (6 - (3 + 1))"; std::cout << expression << " = " << evaluateExpression(expression) << std::endl; return 0; }
如何使用 C++ STL 栈 stack 实现浏览器的前进后退功能？
这个挺常见的，后退用一个栈，前进用另一个栈。当用户访问一个新的页面时，将当前页面压入后退栈，并清空前进栈。当用户点击后退按钮时，从后退栈中弹出一个页面，并将其压入前进栈。当用户点击前进按钮时，从前进栈中弹出一个页面，并将其压入后退栈。
#include <iostream> #include <stack> #include <string> class BrowserHistory { public: std::stack<std::string> backStack; std::stack<std::string> forwardStack; std::string currentPage; BrowserHistory(std::string homepage) : currentPage(homepage) {} void visit(std::string url) { backStack.push(currentPage); currentPage = url; while (!forwardStack.empty()) { forwardStack.pop(); } } std::string back(int steps) { while (steps > 0 && !backStack.empty()) { forwardStack.push(currentPage); currentPage = backStack.top(); backStack.pop(); steps--; } return currentPage; } std::string forward(int steps) { while (steps > 0 && !forwardStack.empty()) { backStack.push(currentPage); currentPage = forwardStack.top(); forwardStack.pop(); steps--; } return currentPage; } std::string getCurrentPage() { return currentPage; } }; int main() { BrowserHistory browser("google.com"); browser.visit("baidu.com"); browser.visit("youtube.com"); std::cout << "Current page: " << browser.getCurrentPage() << std::endl; // youtube.com std::cout << "Back to: " << browser.back(1) << std::endl; // baidu.com std::cout << "Back to: " << browser.back(1) << std::endl; // google.com std::cout << "Forward to: " << browser.forward(1) << std::endl; // baidu.com std::cout << "Current page: " << browser.getCurrentPage() << std::endl; // baidu.com return 0; }
C++ STL 栈 stack 在算法题中如何应用？
栈在解决算法问题中非常有用，特别是在处理涉及回溯、深度优先搜索（DFS）或需要维护特定顺序的问题时。
举个例子，括号匹配问题。给定一个包含括号的字符串，判断其中的括号是否匹配。 可以使用栈来解决这个问题。 遍历字符串，如果遇到左括号，则将其压入栈中。如果遇到右括号，则判断栈是否为空，如果为空，则说明右括号没有匹配的左括号，返回 false。 否则，弹出栈顶的左括号，判断其是否与当前的右括号匹配，如果不匹配，则返回 false。 遍历完成后，如果栈为空，则说明所有括号都匹配，返回 true。 否则，说明有左括号没有匹配的右括号，返回 false。
#include <iostream> #include <stack> #include <string> bool isValid(std::string s) { std::stack<char> parentheses; for (char c : s) { switch (c) { case '(': case '[': case '{': parentheses.push(c); break; case ')': if (parentheses.empty() || parentheses.top() != '(') return false; parentheses.pop(); break; case ']': if (parentheses.empty() || parentheses.top() != '[') return false; parentheses.pop(); break; case '}': if (parentheses.empty() || parentheses.top() != '{') return false; parentheses.pop(); break; } } return parentheses.empty(); } int main() { std::string s1 = "(){}[]"; std::string s2 = "([)]"; std::cout << s1 << " is valid: " << isValid(s1) << std::endl; // 1 (true) std::cout << s2 << " is valid: " << isValid(s2) << std::endl; // 0 (false) return 0; }
C++ STL 栈 stack 的线程安全性如何？
C++ STL 栈 stack 本身不是线程安全的。如果多个线程同时访问同一个栈，可能会导致数据竞争和未定义的行为。
为了在多线程环境中使用栈，需要采取适当的同步机制，例如互斥锁（mutex）。 每个线程在访问栈之前，需要先获取互斥锁，访问完成后再释放互斥锁，以确保同一时间只有一个线程可以访问栈。
#include <iostream> #include <stack> #include <thread> #include <mutex> std::stack<int> myStack; std::mutex stackMutex; void pushToStack(int value) { std::lock_guard<std::mutex> lock(stackMutex); // RAII 风格的锁 myStack.push(value); std::cout << "Thread " << std::this_thread::get_id() << " pushed " << value << std::endl; } int main() { std::thread t1(pushToStack, 10); std::thread t2(pushToStack, 20); t1.join(); t2.join(); std::cout << "Stack size: " << myStack.size() << std::endl; return 0; }
git go 浏览器 ai c++ ios switch youtube 同步机制 运算符 字符串 数据结构 栈 线程 多线程 算法