c++ stack适配器基于vector、deque或list实现LIFO结构，提供push、pop、top操作，适用于括号匹配、表达式求值等场景，可通过自定义容器实现有界栈以满足特定需求。
C++
stack
适配器本质上是利用现有的容器（如
vector
、
deque
或
list
）来实现后进先出（LIFO）的数据结构。它提供了一种方便的方式来管理数据的进出顺序，常用于解决需要追踪最近操作或需要回溯算法的问题。
解决方案
C++
stack
适配器允许你使用标准容器作为底层存储，并提供
push
、
pop
、
top
等方法来实现栈的功能。
#include <iostream> #include <stack> #include <vector> int main() { // 使用 vector 作为底层容器 std::stack<int, std::vector<int>> myStack; myStack.push(10); myStack.push(20); myStack.push(30); std::cout << "Top element: " << myStack.top() << std::endl; // 输出: 30 myStack.pop(); std::cout << "Top element after pop: " << myStack.top() << std::endl; // 输出: 20 std::cout << "Stack size: " << myStack.size() << std::endl; // 输出: 2 return 0; }
在这个例子中，我们使用了
std::vector
作为
std::stack
的底层容器。当然，你也可以选择
std::deque
或
std::list
，这取决于你的具体需求。例如，如果你需要频繁地在栈的底部进行操作，
std::deque
可能更合适，因为它在两端插入和删除元素的时间复杂度都是 O(1)。
如何选择 stack 的底层容器？性能考量
选择
stack
的底层容器时，需要考虑你的应用场景和性能需求。
vector
通常是默认的选择，因为它在大多数情况下提供了良好的性能。但是，
vector
在内存重新分配时可能会导致性能下降。
deque
在两端插入和删除元素时具有更好的性能，但访问中间元素可能会比较慢。
list
在插入和删除元素时具有最佳性能，但访问任何元素都需要线性时间。
立即学习“C++免费学习笔记（深入）”；
例如，如果你的栈需要频繁地插入和删除元素，但很少访问中间元素，那么
list
可能是一个不错的选择。但是，如果你的栈需要频繁地访问中间元素，那么
vector
或
deque
可能会更好。
#include <iostream> #include <stack> #include <deque> int main() { // 使用 deque 作为底层容器 std::stack<int, std::deque<int>> myStack; myStack.push(10); myStack.push(20); myStack.push(30); std::cout << "Top element: " << myStack.top() << std::endl; return 0; }
stack 在解决算法问题中的典型应用场景
stack
在解决算法问题中有很多典型的应用场景，例如：
- 括号匹配： 检查表达式中的括号是否正确匹配。
- 表达式求值： 将中缀表达式转换为后缀表达式，并计算表达式的值。
- 深度优先搜索（DFS）： 在图或树中进行深度优先搜索。
- 函数调用栈： 模拟函数调用栈的行为。
- 浏览器的前进/后退功能： 记录用户浏览历史。
下面是一个使用
stack
实现括号匹配的例子：
#include <iostream> #include <stack> #include <string> bool isMatching(const std::string& expression) { std::stack<char> s; for (char c : expression) { if (c == '(' || c == '[' || c == '{') { s.push(c); } else if (c == ')' || c == ']' || c == '}') { if (s.empty()) { return false; // 缺少左括号 } char top = s.top(); s.pop(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; // 括号不匹配 } } } return s.empty(); // 所有括号都匹配 } int main() { std::string expression1 = "([]{})"; std::string expression2 = "([)]"; std::cout << expression1 << " is matching: " << isMatching(expression1) << std::endl; // 输出: true std::cout << expression2 << " is matching: " << isMatching(expression2) << std::endl; // 输出: false return 0; }
如何自定义 stack 的底层容器以满足特定需求
虽然
vector
、
deque
和
list
已经提供了很好的通用性，但在某些特殊情况下，你可能需要自定义
stack
的底层容器。例如，你可能需要使用一个固定大小的数组来实现一个有界栈，或者你可能需要使用一个自定义的内存分配器来优化内存使用。
要自定义
stack
的底层容器，你需要创建一个满足以下要求的类：
- 提供
push_back
方法，用于在容器末尾添加元素。
- 提供
pop_back
方法，用于删除容器末尾的元素。
- 提供
back
方法，用于访问容器末尾的元素。
- 提供
empty
方法，用于检查容器是否为空。
- 提供
size
方法，用于获取容器的大小。
下面是一个使用固定大小数组实现有界栈的例子：
#include <iostream> #include <stack> template <typename T, size_t N> class BoundedArray { private: T data[N]; size_t currentSize = 0; public: void push_back(const T& value) { if (currentSize == N) { throw std::overflow_error("Stack overflow"); } data[currentSize++] = value; } void pop_back() { if (currentSize == 0) { throw std::underflow_error("Stack underflow"); } currentSize--; } T& back() { if (currentSize == 0) { throw std::underflow_error("Stack is empty"); } return data[currentSize - 1]; } bool empty() const { return currentSize == 0; } size_t size() const { return currentSize; } }; int main() { std::stack<int, BoundedArray<int, 5>> myStack; try { myStack.push(10); myStack.push(20); myStack.push(30); myStack.push(40); myStack.push(50); myStack.push(60); // 触发 overflow } catch (const std::exception& e) { std::cerr << "Exception: " << e.what() << std::endl; // 输出: Stack overflow } std::cout << "Stack size: " << myStack.size() << std::endl; // 输出: 5 return 0; }
在这个例子中，我们创建了一个
BoundedArray
类，它使用一个固定大小的数组来存储数据。
BoundedArray
类提供了
push_back
、
pop_back
、
back
、
empty
和
size
方法，满足了
stack
对底层容器的要求。当栈满时，
push_back
方法会抛出一个
std::overflow_error
异常。当栈空时，
pop_back
和
back
方法会抛出一个
std::underflow_error
异常。
