在这篇博客中，我们将详细介绍栈（Stack）这一重要的数据结构，包括其基本概念、常用操作、C++ 中的实现，以及一些实际应用。
什么是栈？
栈是一种数据结构，它遵循“后进先出”（LIFO - Last In, First Out）的原则。栈就像是一叠盘子，你只能从最上面拿盘子，也只能在最上面放盘子。栈的这一特性使其在很多场景中非常有用，例如递归、回溯算法和表达式计算等。
栈的常用操作
在 C++ 中，我们通常使用 std::stack（定义在 <stack> 头文件中）来实现栈。以下是一些常用操作：
1. 创建栈
#include <stack>
#include <iostream>
std::stack<int> myStack;
这行代码创建了一个存储整数类型的栈。
2. push 操作
将元素添加到栈的顶部。
myStack.push(10);
myStack.push(20);
myStack.push(30);
这几行代码将元素 10、20 和 30 依次推入栈中，其真实存储结构如下：
3. top 操作
访问栈顶部的元素，但不移除它。
std::cout << "Top element: " << myStack.top() << std::endl;
这行代码访问栈顶元素，结果为 30。
4. pop 操作
移除栈顶部的元素。
myStack.pop();
这行代码移除栈顶元素。
5. size 操作
返回栈中的元素个数。
std::cout << "Stack size: " << myStack.size() << std::endl;
这行代码输出栈的大小，结果为 3。
6. empty 操作
检查栈是否为空。
if (myStack.empty()) {
std::cout << "Stack is empty" << std::endl;
} else {
std::cout << "Stack is not empty" << std::endl;
}
这段代码检查栈是否为空，并输出结果。
栈的实际应用
1. 将 stack<char> 转换为字符串
有时我们可能需要将栈中的字符转换为字符串。我们可以通过弹出栈中的元素并将它们连接起来实现这一点。
特别需要注意的是：因为栈的先进后出（LIFO）性质，所以很多时候我们从前往后遍历的时候，在最后输出结果的时候需要 reverse 一下。
#include <stack>
#include <string>
#include <iostream>
#include <algorithm> // for std::reverse
std::string stackToString(std::stack<char> &charStack) {
std::string result;
while (!charStack.empty()) {
result += charStack.top();
charStack.pop();
}
// 反转结果以获得正确的顺序
std::reverse(result.begin(), result.end());
return result;
}
int main() {
std::stack<char> charStack;
charStack.push('a');
charStack.push('b');
charStack.push('c');
std::string result = stackToString(charStack);
std::cout << "Stack to string: " << result << std::endl; // 输出 "abc"
return 0;
}
2. 括号匹配问题
括号匹配是栈的经典应用之一。我们可以使用栈来检查一个字符串中的括号是否匹配。
#include <stack>
#include <string>
#include <iostream>
bool isValid(std::string s) {
std::stack<char> stack;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
int main() {
std::string s = "{[()]}";
if (isValid(s)) {
std::cout << "Valid brackets" << std::endl;
} else {
std::cout << "Invalid brackets" << std::endl;
}
return 0;
}
在这段代码中，我们使用栈来处理括号匹配问题。遍历字符串，如果是左括号就压入栈中，如果是右括号则检查栈顶是否为匹配的左括号。如果匹配则弹出栈顶，否则返回 false。最后如果栈为空则括号匹配成功。
总结
通过这篇博客，我们详细介绍了栈的基本概念及其在 C++ 中的实现。栈是一种非常有用的数据结构，尤其在处理递归、回溯和表达式计算等问题时。我们还讨论了如何将栈中的字符转换为字符串，以及如何使用栈解决括号匹配问题。
特别需要注意的是，栈的先进后出（LIFO）性质在很多应用场景中都需要我们进行结果的反转，以确保顺序正确。希望这篇博客能够帮助你更好地理解栈的使用及其在实际问题中的应用。