1 std::stack 應用于自定義數(shù)據(jù)結構

通常，std::stack 用于存儲基本數(shù)據(jù)類型，如 int、float、char 等。然而，std::stack 同樣可以存儲自定義的數(shù)據(jù)結構，只要這些數(shù)據(jù)結構滿足一定的要求。

（1）存儲自定義數(shù)據(jù)結構的要求

要使自定義數(shù)據(jù)結構能夠存儲在 std::stack 中，該數(shù)據(jù)結構必須滿足以下條件：

• 可復制性：自定義數(shù)據(jù)結構必須能夠被復制。這意味著它必須有一個有效的復制構造函數(shù)和一個賦值運算符。當元素被壓入?；驈臈Ｖ袕棾鰰r，會涉及到復制操作。
• 析構函數(shù)：自定義數(shù)據(jù)結構應該有一個合適的析構函數(shù)，以確保在元素從棧中刪除時能夠正確地釋放資源。

（2）使用 std::stack 存儲自定義數(shù)據(jù)結構

下面是一個簡單的例子，展示了如何使用 std::stack 存儲自定義的數(shù)據(jù)結構：

#include <iostream>  
#include <stack>  // 自定義數(shù)據(jù)結構  
struct MyData {  int id;  std::string name;  // 構造函數(shù)  MyData(int id, const std::string& name) : id(id), name(name) {}  // 輸出數(shù)據(jù)結構的內(nèi)容  void print() const {  std::cout << "ID: " << id << ", Name: " << name << std::endl;  }  
};  int main() 
{  // 創(chuàng)建一個存儲 MyData 類型元素的棧  std::stack<MyData> dataStack;  // 創(chuàng)建一些 MyData 對象并將其壓入棧中  dataStack.push(MyData(1, "Alice"));  dataStack.push(MyData(2, "Bob"));  dataStack.push(MyData(3, "Charlie"));  // 遍歷棧并輸出每個元素的內(nèi)容  while (!dataStack.empty()) {  MyData topData = dataStack.top(); // 獲取棧頂元素但不移除它  topData.print(); // 輸出棧頂元素的內(nèi)容  dataStack.pop(); // 移除棧頂元素  }  return 0;  
}

上面代碼的輸出為：

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

這個例子定義了一個名為 MyData 的自定義數(shù)據(jù)結構，它包含兩個成員變量：id 和 name。然后，我們創(chuàng)建了一個 std::stack<MyData> 類型的棧，用于存儲 MyData 對象。通過調用 push 方法將 MyData 對象壓入棧中，并通過循環(huán)和 top、pop 方法遍歷并輸出棧中每個元素的內(nèi)容。

（3）注意事項

• 內(nèi)存管理：當自定義數(shù)據(jù)結構包含動態(tài)分配的內(nèi)存（如指針、動態(tài)數(shù)組等）時，需要確保在復制和析構過程中正確地管理這些內(nèi)存。
• 性能考慮：對于大型或復雜的自定義數(shù)據(jù)結構，頻繁地復制元素可能會對性能產(chǎn)生顯著影響。在這種情況下，可以考慮使用指針或智能指針（如 std::shared_ptr 或 std::unique_ptr）來存儲數(shù)據(jù)結構的引用，而不是直接存儲數(shù)據(jù)結構本身。
• 異常安全性：在自定義數(shù)據(jù)結構的復制構造函數(shù)和賦值運算符中，應確保操作是異常安全的，以避免在發(fā)生異常時導致資源泄漏或其他問題。

2 std::stack 的主要應用場景

下面是 std::stack 的一些主要應用場景：

（1）函數(shù)調用與遞歸：

在函數(shù)調用和遞歸實現(xiàn)中，局部變量和參數(shù)通常被存儲在棧上。std::stack 可以模擬這種行為，幫助理解函數(shù)調用的過程。

（2）表達式求值：

在算術表達式或邏輯表達式的求值過程中，通常使用棧來存儲操作數(shù)和操作符。例如，實現(xiàn)一個簡單的四則運算器時，可以利用棧來處理運算符和操作數(shù)的優(yōu)先級。

（3）深度優(yōu)先搜索（DFS）：

在圖或樹的深度優(yōu)先搜索中，?？梢杂脕肀４娲L問的節(jié)點。每次從棧中彈出一個節(jié)點，并訪問其相鄰節(jié)點，然后將相鄰節(jié)點壓入棧中，直到棧為空或達到搜索目標。

（4）括號匹配：

在解析包含括號的字符串（如數(shù)學表達式、編程語言中的代碼塊等）時，?？梢杂脕砀櫸撮]合的括號，以確保它們的正確匹配。

（5）撤銷/重做操作：

在一些需要撤銷或重做功能的應用中（如文本編輯器、繪圖工具等），可以使用棧來存儲歷史操作。撤銷操作就是彈出棧頂元素，重做操作則是將之前彈出的元素再次壓入棧中。

（6）解析與編譯器設計：

在編譯器設計中，?？梢杂脕砀櫿Z法分析過程中的符號和狀態(tài)。

（7）UI導航歷史：

在一些圖形用戶界面（GUI）應用中，?？梢杂脕泶鎯τ脩舻膶Ш綒v史，以便用戶可以向前或向后導航。

（8）游戲開發(fā)：

在某些游戲中，?？梢杂脕砉芾碛螒驙顟B(tài)、事件或動作序列。

（9）算法實現(xiàn)：

一些算法，如漢諾塔問題、中序遍歷的非遞歸實現(xiàn)等，都可以使用棧來輔助實現(xiàn)。

2.1 std::stack 應用于函數(shù)調用與遞歸

下面是一個簡單的示例，演示了如何使用 std::stack 來模擬函數(shù)調用和遞歸的過程。在這個示例中，我們將創(chuàng)建一個簡單的函數(shù)調用棧，并模擬執(zhí)行一些基本的函數(shù)調用和返回操作。

#include <iostream>  
#include <stack>  
#include <string>  // 模擬的函數(shù)調用記錄結構  
struct FunctionCall {  std::string functionName; // 函數(shù)名  int returnAddress;        // 返回地址（在棧中的位置）  // 構造函數(shù)  FunctionCall(const std::string& name, int addr) : functionName(name), returnAddress(addr) {}  
};  int main() 
{  std::stack<FunctionCall> callStack; // 函數(shù)調用棧  int currentPosition = 0;             // 當前執(zhí)行位置  // 模擬函數(shù)A的調用  std::cout << "Entering function A" << std::endl;  callStack.push(FunctionCall("A", currentPosition + 1)); // 壓入函數(shù)調用記錄  currentPosition++; // 移動到下一個執(zhí)行位置  // 假設函數(shù)A調用了函數(shù)B  std::cout << "Calling function B from A" << std::endl;  callStack.push(FunctionCall("B", currentPosition + 1)); // 壓入函數(shù)B的調用記錄  currentPosition++; // 移動到下一個執(zhí)行位置  // 執(zhí)行函數(shù)B的代碼（這里只是模擬）  std::cout << "Executing function B" << std::endl;  currentPosition++; // 假設函數(shù)B執(zhí)行了一些操作，移動到下一個執(zhí)行位置  // 函數(shù)B執(zhí)行完畢，準備返回  std::cout << "Returning from function B" << std::endl;  FunctionCall topCall = callStack.top(); // 獲取棧頂函數(shù)調用記錄  std::cout << "Returning to " << topCall.functionName << std::endl;  callStack.pop(); // 彈出棧頂記錄，表示返回  currentPosition = topCall.returnAddress; // 設置返回地址  // 繼續(xù)執(zhí)行函數(shù)A的剩余代碼  std::cout << "Continuing execution in function A" << std::endl;  currentPosition++; // 移動到下一個執(zhí)行位置（如果有的話）  // 函數(shù)A執(zhí)行完畢，準備返回  std::cout << "Returning from function A" << std::endl;  if (!callStack.empty()) {  topCall = callStack.top(); // 如果有更多函數(shù)調用，則獲取棧頂記錄  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 結構體來記錄每次函數(shù)調用的信息，包括函數(shù)名和返回地址（在調用棧中的位置）。示例中使用 std::stack<FunctionCall> 來模擬函數(shù)調用棧的行為。每次函數(shù)調用時，將一個新的 FunctionCall 對象壓入棧中，并記錄當前的執(zhí)行位置。當函數(shù)返回時，從棧頂彈出記錄，并根據(jù)記錄的返回地址繼續(xù)執(zhí)行。

注意：這個示例是為了演示目的而簡化的。在實際的程序中，函數(shù)調用和返回通常涉及到更多的復雜性和細節(jié)，比如局部變量、參數(shù)傳遞、作用域等。此外，這個示例也沒有展示如何處理函數(shù)調用中的參數(shù)和返回值。在實際的編譯器或解釋器實現(xiàn)中，函數(shù)調用棧會更加復雜，并且會緊密地與程序的執(zhí)行流程相結合。

2.2 std::stack 應用于表達式求值

下面是一個使用 std::stack 來實現(xiàn)簡單四則運算表達式求值的示例。這個示例將實現(xiàn)一個基本的計算器，能夠處理加、減、乘、除四種運算。為了實現(xiàn)這個計算器，需要使用兩個棧：一個用于存儲操作數(shù)，另一個用于存儲操作符。

#include <iostream>  
#include <stack>  
#include <cctype>  
#include <string>  
#include <cmath>  // 定義運算符的優(yōu)先級  
int getPrecedence(char op) {  if (op == '+' || op == '-') return 1;  if (op == '*' || op == '/') return 2;  return 0;  
}  // 執(zhí)行運算  
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; // 操作數(shù)棧  std::stack<char> ops;     // 操作符棧  for (size_t i = 0; i < expr.size(); ++i) {  char ch = expr[i];  // 如果是空格，則跳過  if (std::isspace(ch)) continue;  // 如果是操作數(shù)，則壓入操作數(shù)棧  if (std::isdigit(ch)) {  double val = 0;  // 處理多位數(shù)  while (i < expr.size() && std::isdigit(expr[i])) {  val = val * 10 + (expr[i] - '0');  ++i;  }  --i; // 因為for循環(huán)還會遞增i，所以這里要減回去  values.push(val);  }  // 如果是左括號，則壓入操作符棧  else if (ch == '(') {  ops.push(ch);  }  // 如果是右括號，則執(zhí)行棧頂操作符直到遇到左括號  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(); // 彈出左括號  }  // 如果是操作符，則根據(jù)優(yōu)先級進行處理  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));  }  // 表達式的結果應該在操作數(shù)棧的頂部  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 函數(shù)來返回運算符的優(yōu)先級，然后定義了一個 applyOp 函數(shù)來執(zhí)行實際的運算。在 evaluateExpression 函數(shù)中，遍歷輸入的表達式，并根據(jù)字符類型執(zhí)行相應的操作。

當遇到數(shù)字時，將其解析為一個 double 類型的數(shù)值并壓入操作數(shù)棧。當遇到左括號時，將其壓入操作符棧。當遇到右括號時，彈出操作符棧頂?shù)牟僮鞣?zhí)行相應的運算，直到遇到左括號為止。當遇到操作符時，則根據(jù)操作符的優(yōu)先級來決定是否先執(zhí)行棧頂?shù)牟僮鞣?/p>

最后，在遍歷完整個表達式后，將執(zhí)行操作符棧中剩余的所有操作符，并將最終的結果存儲在操作數(shù)棧的頂部。

2.3 std::stack 應用于深度優(yōu)先搜索（DFS）

棧在深度優(yōu)先搜索（DFS）中是一個非常有用的數(shù)據(jù)結構。以下是一個使用 std::stack 來實現(xiàn)深度優(yōu)先搜索的簡單示例。這個示例將在一個無向圖中進行深度優(yōu)先搜索。

#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); // 對于無向圖，需要添加反向邊  }  // 深度優(yōu)先搜索  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 << " ";  // 遍歷與當前節(jié)點相鄰且未被訪問過的節(jié)點  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); // 創(chuàng)建一個包含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 方法是深度優(yōu)先搜索的實現(xiàn)。它使用一個棧 s 來保存待訪問的節(jié)點，以及一個 visited 哈希集合來跟蹤已經(jīng)訪問過的節(jié)點。搜索從指定的起始節(jié)點 start 開始。

在 DFS 方法中，首先將起始節(jié)點壓入棧中，并標記為已訪問。然后，在棧不為空的情況下，不斷地從棧頂取出節(jié)點，訪問它，并將其未訪問過的相鄰節(jié)點壓入棧中。這個過程一直持續(xù)到棧為空，即所有可達的節(jié)點都已被訪問。

在 main 函數(shù)中，創(chuàng)建了一個包含5個頂點的圖，并添加了一些邊。然后，從頂點0開始進行深度優(yōu)先遍歷，并輸出遍歷結果。

運行這個程序，可以看到從頂點0開始的深度優(yōu)先遍歷結果。由于圖的結構和遍歷順序可能因實現(xiàn)細節(jié)和編譯器行為的不同而略有差異，因此輸出可能不是唯一的。

3 實現(xiàn)一個簡單的 std::stack 容器

下面是一個簡單的 MyStack 類的實現(xiàn)，它使用 std::vector 作為底層容器。

#include <iostream>  
#include <vector>  template <typename T>
class MyStack {
public:// 構造函數(shù)  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 方法來實現(xiàn)棧的基本操作。