c++ Stack 类的模板实例

在C++编程语言中，`Stack`是一种非常重要的数据结构，它遵循“后进先出”（LIFO）的原则。栈通常用于实现递归、表达式求值、内存管理等多种算法和程序设计问题。在这里，我们将深入探讨C++中的`Stack`类模板，以及如何通过实例来理解和使用它。 C++标准库提供了`<stack>`头文件，其中定义了`stack`容器适配器。`stack`不是一个独立的数据结构，而是基于其他容器（如`vector`或`deque`）构建的，它提供了一组特定的操作，使得容器的行为像一个栈。在实例化`stack`时，我们需要指定基础容器类型。例如： ```cpp #include <stack> #include <vector> std::stack<int, std::vector<int>> mystack; ``` 在这个例子中，我们创建了一个存储整数的栈，基础容器是`std::vector<int>`。 **1. 入栈操作（push）：** 栈的主要操作之一是将元素压入栈顶。使用`push`函数可以完成这个操作： ```cpp mystack.push(5); // 将5压入栈顶 ``` **2. 出栈操作（pop）：** 出栈操作从栈顶移除并返回元素。调用`pop`函数会删除栈顶的元素： ```cpp mystack.pop(); // 移除栈顶元素 ``` **3. 查看栈顶元素（top）：** `top`函数允许我们查看栈顶的元素，但不移除它： ```cpp int topElement = mystack.top(); // 获取栈顶元素，但不移除 ``` **4. 检查栈是否为空（empty）：** `empty`函数用于检查栈是否为空： ```cpp if (mystack.empty()) { std::cout << "Stack is empty."; } else { std::cout << "Stack is not empty."; } ``` **5. 获取栈的大小（size）：** `size`函数返回栈中元素的数量： ```cpp int stackSize = mystack.size(); // 获取栈的元素数量 ``` 在实际应用中，我们可以结合这些基本操作来解决各种问题。例如，我们可以用栈来实现深度优先搜索（DFS）或表达式的求值。为了更好地理解`Stack`类模板的使用，下面是一个简单的实例： ```cpp #include <iostream> #include <stack> #include <string> // 一个简单的逆波兰表达式求值 int evaluateRPN(const std::string& tokens) { std::stack<int> nums; for (char token : tokens) { if ('0' <= token && token <= '9') { nums.push(token - '0'); } else { int b = nums.top(); nums.pop(); int a = nums.top(); nums.pop(); switch (token) { case '+': nums.push(a + b); break; case '-': nums.push(a - b); break; case '*': nums.push(a * b); break; case '/': nums.push(a / b); break; } } } return nums.top(); } int main() { std::string expression = "2 1 + 3 *"; std::cout << "Evaluation: " << evaluateRPN(expression) << std::endl; // 输出 9 return 0; } ``` 在这个实例中，我们使用`Stack`类模板来处理逆波兰表达式（也称为后缀表达式），栈帮助我们在正确的位置进行计算。 C++的`Stack`类模板提供了一种高效且方便的方式来实现和操作栈数据结构。通过对`push`、`pop`、`top`、`empty`和`size`等成员函数的理解与实践，开发者可以更有效地解决各种算法和程序设计问题。