突破编程_C++_STL教程（ stack 的实战应用）

1 std::stack 应用于自定义数据结构

通常，std::stack 用于存储基本数据类型，如 int、float、char 等。然而，std::stack 同样可以存储自定义的数据结构，只要这些数据结构满足一定的要求。

（1）存储自定义数据结构的要求

要使自定义数据结构能够存储在 std::stack 中，该数据结构必须满足以下条件：

• 可复制性：自定义数据结构必须能够被复制。这意味着它必须有一个有效的复制构造函数和一个赋值运算符。当元素被压入栈或从栈中弹出时，会涉及到复制操作。
• 析构函数：自定义数据结构应该有一个合适的析构函数，以确保在元素从栈中删除时能够正确地释放资源。

（2）使用 std::stack 存储自定义数据结构

下面是一个简单的例子，展示了如何使用 std::stack 存储自定义的数据结构：

#include <iostream>  
#include <stack>  // 自定义数据结构  
struct MyData {  int id;  std::string name;  // 构造函数  MyData(int id, const std::string& name) : id(id), name(name) {}  // 输出数据结构的内容  void print() const {  std::cout << "ID: " << id << ", Name: " << name << std::endl;  }  
};  int main() 
{  // 创建一个存储 MyData 类型元素的栈  std::stack<MyData> dataStack;  // 创建一些 MyData 对象并将其压入栈中  dataStack.push(MyData(1, "Alice"));  dataStack.push(MyData(2, "Bob"));  dataStack.push(MyData(3, "Charlie"));  // 遍历栈并输出每个元素的内容  while (!dataStack.empty()) {  MyData topData = dataStack.top(); // 获取栈顶元素但不移除它  topData.print(); // 输出栈顶元素的内容  dataStack.pop(); // 移除栈顶元素  }  return 0;  
}

上面代码的输出为：

ID: 3, Name: Charlie
ID: 2, Name: Bob
ID: 1, Name: Alice

这个例子定义了一个名为 MyData 的自定义数据结构，它包含两个成员变量：id 和 name。然后，我们创建了一个 std::stack<MyData> 类型的栈，用于存储 MyData 对象。通过调用 push 方法将 MyData 对象压入栈中，并通过循环和 top、pop 方法遍历并输出栈中每个元素的内容。

（3）注意事项

• 内存管理：当自定义数据结构包含动态分配的内存（如指针、动态数组等）时，需要确保在复制和析构过程中正确地管理这些内存。
• 性能考虑：对于大型或复杂的自定义数据结构，频繁地复制元素可能会对性能产生显著影响。在这种情况下，可以考虑使用指针或智能指针（如 std::shared_ptr 或 std::unique_ptr）来存储数据结构的引用，而不是直接存储数据结构本身。
• 异常安全性：在自定义数据结构的复制构造函数和赋值运算符中，应确保操作是异常安全的，以避免在发生异常时导致资源泄漏或其他问题。

2 std::stack 的主要应用场景

下面是 std::stack 的一些主要应用场景：

（1）函数调用与递归：

在函数调用和递归实现中，局部变量和参数通常被存储在栈上。std::stack 可以模拟这种行为，帮助理解函数调用的过程。

（2）表达式求值：

在算术表达式或逻辑表达式的求值过程中，通常使用栈来存储操作数和操作符。例如，实现一个简单的四则运算器时，可以利用栈来处理运算符和操作数的优先级。

（3）深度优先搜索（DFS）：

在图或树的深度优先搜索中，栈可以用来保存待访问的节点。每次从栈中弹出一个节点，并访问其相邻节点，然后将相邻节点压入栈中，直到栈为空或达到搜索目标。

（4）括号匹配：

在解析包含括号的字符串（如数学表达式、编程语言中的代码块等）时，栈可以用来跟踪未闭合的括号，以确保它们的正确匹配。

（5）撤销/重做操作：

在一些需要撤销或重做功能的应用中（如文本编辑器、绘图工具等），可以使用栈来存储历史操作。撤销操作就是弹出栈顶元素，重做操作则是将之前弹出的元素再次压入栈中。

（6）解析与编译器设计：

在编译器设计中，栈可以用来跟踪语法分析过程中的符号和状态。

（7）UI导航历史：

在一些图形用户界面（GUI）应用中，栈可以用来存储用户的导航历史，以便用户可以向前或向后导航。

（8）游戏开发：

在某些游戏中，栈可以用来管理游戏状态、事件或动作序列。

（9）算法实现：

一些算法，如汉诺塔问题、中序遍历的非递归实现等，都可以使用栈来辅助实现。

2.1 std::stack 应用于函数调用与递归

下面是一个简单的示例，演示了如何使用 std::stack 来模拟函数调用和递归的过程。在这个示例中，我们将创建一个简单的函数调用栈，并模拟执行一些基本的函数调用和返回操作。

#include <iostream>  
#include <stack>  
#include <string>  // 模拟的函数调用记录结构  
struct FunctionCall {  std::string functionName; // 函数名  int returnAddress;        // 返回地址（在栈中的位置）  // 构造函数  FunctionCall(const std::string& name, int addr) : functionName(name), returnAddress(addr) {}  
};  int main() 
{  std::stack<FunctionCall> callStack; // 函数调用栈  int currentPosition = 0;             // 当前执行位置  // 模拟函数A的调用  std::cout << "Entering function A" << std::endl;  callStack.push(FunctionCall("A", currentPosition + 1)); // 压入函数调用记录  currentPosition++; // 移动到下一个执行位置  // 假设函数A调用了函数B  std::cout << "Calling function B from A" << std::endl;  callStack.push(FunctionCall("B", currentPosition + 1)); // 压入函数B的调用记录  currentPosition++; // 移动到下一个执行位置  // 执行函数B的代码（这里只是模拟）  std::cout << "Executing function B" << std::endl;  currentPosition++; // 假设函数B执行了一些操作，移动到下一个执行位置  // 函数B执行完毕，准备返回  std::cout << "Returning from function B" << std::endl;  FunctionCall topCall = callStack.top(); // 获取栈顶函数调用记录  std::cout << "Returning to " << topCall.functionName << std::endl;  callStack.pop(); // 弹出栈顶记录，表示返回  currentPosition = topCall.returnAddress; // 设置返回地址  // 继续执行函数A的剩余代码  std::cout << "Continuing execution in function A" << std::endl;  currentPosition++; // 移动到下一个执行位置（如果有的话）  // 函数A执行完毕，准备返回  std::cout << "Returning from function A" << std::endl;  if (!callStack.empty()) {  topCall = callStack.top(); // 如果有更多函数调用，则获取栈顶记录  std::cout << "Returning to " << topCall.functionName << std::endl;  callStack.pop(); // 弹出栈顶记录，表示返回到上一层调用  currentPosition = topCall.returnAddress; // 设置新的返回地址  } else {  std::cout << "Program execution finished" << std::endl;  }  return 0;  
}

上面代码的输出为：

Entering function A
Calling function B from A
Executing function B
Returning from function B
Returning to B
Continuing execution in function A
Returning from function A
Returning to A

这个示例定义了一个 FunctionCall 结构体来记录每次函数调用的信息，包括函数名和返回地址（在调用栈中的位置）。示例中使用 std::stack<FunctionCall> 来模拟函数调用栈的行为。每次函数调用时，将一个新的 FunctionCall 对象压入栈中，并记录当前的执行位置。当函数返回时，从栈顶弹出记录，并根据记录的返回地址继续执行。

注意：这个示例是为了演示目的而简化的。在实际的程序中，函数调用和返回通常涉及到更多的复杂性和细节，比如局部变量、参数传递、作用域等。此外，这个示例也没有展示如何处理函数调用中的参数和返回值。在实际的编译器或解释器实现中，函数调用栈会更加复杂，并且会紧密地与程序的执行流程相结合。

2.2 std::stack 应用于表达式求值

下面是一个使用 std::stack 来实现简单四则运算表达式求值的示例。这个示例将实现一个基本的计算器，能够处理加、减、乘、除四种运算。为了实现这个计算器，需要使用两个栈：一个用于存储操作数，另一个用于存储操作符。

#include <iostream>  
#include <stack>  
#include <cctype>  
#include <string>  
#include <cmath>  // 定义运算符的优先级  
int getPrecedence(char op) {  if (op == '+' || op == '-') return 1;  if (op == '*' || op == '/') return 2;  return 0;  
}  // 执行运算  
double applyOp(double a, double b, char op) {  switch(op) {  case '+': return a + b;  case '-': return a - b;  case '*': return a * b;  case '/':   if (b != 0.0)  return a / b;  else  throw std::invalid_argument("Division by zero");  default:   throw std::invalid_argument("Unknown operator");  }  
}  // 计算表达式的值  
double evaluateExpression(const std::string &expr) {  std::stack<double> values; // 操作数栈  std::stack<char> ops;     // 操作符栈  for (size_t i = 0; i < expr.size(); ++i) {  char ch = expr[i];  // 如果是空格，则跳过  if (std::isspace(ch)) continue;  // 如果是操作数，则压入操作数栈  if (std::isdigit(ch)) {  double val = 0;  // 处理多位数  while (i < expr.size() && std::isdigit(expr[i])) {  val = val * 10 + (expr[i] - '0');  ++i;  }  --i; // 因为for循环还会递增i，所以这里要减回去  values.push(val);  }  // 如果是左括号，则压入操作符栈  else if (ch == '(') {  ops.push(ch);  }  // 如果是右括号，则执行栈顶操作符直到遇到左括号  else if (ch == ')') {  while (!ops.empty() && ops.top() != '(') {  double val2 = values.top(); values.pop();  double val1 = values.top(); values.pop();  char op = ops.top(); ops.pop();  values.push(applyOp(val1, val2, op));  }  if (!ops.empty()) ops.pop(); // 弹出左括号  }  // 如果是操作符，则根据优先级进行处理  else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {  while (!ops.empty() && getPrecedence(ops.top()) >= getPrecedence(ch)) {  double val2 = values.top(); values.pop();  double val1 = values.top(); values.pop();  char op = ops.top(); ops.pop();  values.push(applyOp(val1, val2, op));  }  ops.push(ch);  }  // 如果是非法字符，则抛出异常  else {  throw std::invalid_argument("Invalid character in expression");  }  }  // 应用栈中剩余的操作符  while (!ops.empty()) {  double val2 = values.top(); values.pop();  double val1 = values.top(); values.pop();  char op = ops.top(); ops.pop();  values.push(applyOp(val1, val2, op));  }  // 表达式的结果应该在操作数栈的顶部  return values.top();  
}  int main() 
{  std::string expression = "(1+2)*(2+6)/2-1";try {  double result = evaluateExpression(expression);  std::cout << "Result: " << result << std::endl;  } catch (const std::exception &e) {  std::cerr << "Error: " << e.what() << std::endl;  }  return 0;  
}

上面代码的输出为：

Result: 11

程序中，首先定义了一个 getPrecedence 函数来返回运算符的优先级，然后定义了一个 applyOp 函数来执行实际的运算。在 evaluateExpression 函数中，遍历输入的表达式，并根据字符类型执行相应的操作。

当遇到数字时，将其解析为一个 double 类型的数值并压入操作数栈。当遇到左括号时，将其压入操作符栈。当遇到右括号时，弹出操作符栈顶的操作符并执行相应的运算，直到遇到左括号为止。当遇到操作符时，则根据操作符的优先级来决定是否先执行栈顶的操作符。

最后，在遍历完整个表达式后，将执行操作符栈中剩余的所有操作符，并将最终的结果存储在操作数栈的顶部。

2.3 std::stack 应用于深度优先搜索（DFS）

栈在深度优先搜索（DFS）中是一个非常有用的数据结构。以下是一个使用 std::stack 来实现深度优先搜索的简单示例。这个示例将在一个无向图中进行深度优先搜索。

#include <iostream>  
#include <vector>  
#include <stack>  
#include <unordered_set>  // 使用邻接列表表示图  
class Graph {  
public:  Graph(int vertices) : adjList(vertices) {}  // 添加边  void addEdge(int src, int dest) {  adjList[src].push_back(dest);  adjList[dest].push_back(src); // 对于无向图，需要添加反向边  }  // 深度优先搜索  void DFS(int start) {  std::stack<int> s;  std::unordered_set<int> visited;  s.push(start);  visited.insert(start);  while (!s.empty()) {  int vertex = s.top();  s.pop();  std::cout << vertex << " ";  // 遍历与当前节点相邻且未被访问过的节点  for (int neighbor : adjList[vertex]) {  if (visited.find(neighbor) == visited.end()) {  s.push(neighbor);  visited.insert(neighbor);  }  }  }  }  private:  std::vector<std::vector<int>> adjList; // 邻接列表  
};  int main() 
{  Graph g(5); // 创建一个包含5个顶点的图  // 添加边  g.addEdge(0, 1);  g.addEdge(0, 4);  g.addEdge(1, 2);  g.addEdge(1, 3);  g.addEdge(1, 4);  g.addEdge(2, 3);  g.addEdge(3, 4);  std::cout << "Depth First Traversal (starting from vertex 0): ";  g.DFS(0);  std::cout << std::endl;  return 0;  
}

上面代码的输出为：

Depth First Traversal (starting from vertex 0): 0 4 3 2 1

这个示例首先定义了一个 Graph 类，它包含一个邻接列表 adjList 来存储图的信息。addEdge 方法用于向图中添加边。

DFS 方法是深度优先搜索的实现。它使用一个栈 s 来保存待访问的节点，以及一个 visited 哈希集合来跟踪已经访问过的节点。搜索从指定的起始节点 start 开始。

在 DFS 方法中，首先将起始节点压入栈中，并标记为已访问。然后，在栈不为空的情况下，不断地从栈顶取出节点，访问它，并将其未访问过的相邻节点压入栈中。这个过程一直持续到栈为空，即所有可达的节点都已被访问。

在 main 函数中，创建了一个包含5个顶点的图，并添加了一些边。然后，从顶点0开始进行深度优先遍历，并输出遍历结果。

运行这个程序，可以看到从顶点0开始的深度优先遍历结果。由于图的结构和遍历顺序可能因实现细节和编译器行为的不同而略有差异，因此输出可能不是唯一的。

3 实现一个简单的 std::stack 容器

下面是一个简单的 MyStack 类的实现，它使用 std::vector 作为底层容器。

#include <iostream>  
#include <vector>  template <typename T>
class MyStack {
public:// 构造函数  MyStack() : elements() {}// 判断栈是否为空  bool empty() const {return elements.empty();}// 返回栈顶元素（不删除）  T& top() {if (empty()) {throw std::out_of_range("Stack is empty");}return elements.back();}const T& top() const {if (empty()) {throw std::out_of_range("Stack is empty");}return elements.back();}// 将元素压入栈顶  void push(const T& value) {elements.push_back(value);}// 弹出栈顶元素  void pop() {if (empty()) {throw std::out_of_range("Stack is empty");}elements.pop_back();}// 返回栈的大小  size_t size() const {return elements.size();}private:std::vector<T> elements; // 底层容器  
};int main() 
{MyStack<int> myStack;// 压入几个元素  myStack.push(1);myStack.push(2);myStack.push(3);// 输出栈的大小  std::cout << "Size of stack: " << myStack.size() << std::endl;// 弹出栈顶元素并输出  myStack.pop();std::cout << "Top element after pop: " << myStack.top() << std::endl;// 判断栈是否为空  if (myStack.empty()) {std::cout << "Stack is empty." << std::endl;}else {std::cout << "Stack is not empty." << std::endl;}return 0;
}

上面代码的输出为：

Size of stack: 3
Top element after pop: 2
Stack is not empty.

这个简单的 MyStack 类提供了基本的栈操作，包括 push（压栈）、pop（弹栈）、top（查看栈顶元素）、empty（判断栈是否为空）和 size（获取栈的大小）。它使用 std::vector 作为底层容器来存储元素，并利用 vector 的 push_back 和 pop_back 方法来实现栈的基本操作。