栈（Stack）是计算机科学中一种非常重要的数据结构，它是一种遵循 后进先出（LIFO, Last In First Out）原则的数据结构，即最后放入栈中的元素最先被取出。

基本操作

• push: 将元素压入栈顶。

• pop: 从栈顶弹出元素。

• top 或 peek: 获取栈顶元素，但不弹出。

• isEmpty: 检查栈是否为空。

• size: 获取栈的大小。

栈的操作通常是基于数组或链表实现的。大多数编程语言都提供了栈的实现（如 C++ STL 中的 std::stack 类）。

栈的实现

使用数组实现一个栈

#include <iostream>
#include <stdexcept>class Stack {
private:int* arr;         // 存储栈元素的数组int capacity;     // 栈的最大容量int topIndex;     // 栈顶索引public:Stack(int cap) : capacity(cap), topIndex(-1) {arr = new int[capacity];}~Stack() {delete[] arr;}// 栈是否为空bool isEmpty() {return topIndex == -1;}// 栈是否已满bool isFull() {return topIndex == capacity - 1;}// 获取栈顶元素int top() {if (isEmpty()) {throw std::out_of_range("Stack is empty");}return arr[topIndex];}// 入栈操作void push(int value) {if (isFull()) {throw std::overflow_error("Stack overflow");}arr[++topIndex] = value;}// 出栈操作void pop() {if (isEmpty()) {throw std::underflow_error("Stack underflow");}--topIndex;}// 获取栈大小int size() {return topIndex + 1;}
};int main() {Stack s(5);s.push(10);s.push(20);s.push(30);std::cout << "Top element: " << s.top() << std::endl;s.pop();std::cout << "Top element after pop: " << s.top() << std::endl;std::cout << "Stack size: " << s.size() << std::endl;return 0;
}

常见应用

括号匹配问题

给定一个包含括号（(), {}, []）的字符串，判断括号是否匹配。

算法思想

遇到左括号时入栈，遇到右括号时出栈，匹配时继续，如果匹配失败或者栈为空，则不匹配。

代码实现（c++）

#include <iostream>
#include <stack>
#include <string>bool isValid(const std::string& s) {std::stack<char> stack;for (auto c : s) {if (c == '(' || c == '{' || c == '[') {stack.push(c);} else {if (stack.empty()) return false;char top = stack.top();stack.pop();if (c == ')' && top != '(') return false;if (c == '}' && top != '{') return false;if (c == ']' && top != '[') return false;}}return stack.empty();
}int main() {std::string s = "{[()]}";if (isValid(s)) {std::cout << "Valid" << std::endl;} else {std::cout << "Invalid" << std::endl;}return 0;
}

逆波兰表达式求值

逆波兰表达式是一种后缀表达式，运算符位于操作数后面，利用栈来计算结果。

算法思想

通过扫描逆波兰表达式，将数字压入栈中，遇到运算符时从栈中弹出操作数，进行运算后再将结果压回栈中。

代码实现（c++）

#include <iostream>
#include <stack>
#include <sstream>
#include <string>
#include <cctype>int evalRPN(const std::vector<std::string>& tokens) {std::stack<int> stack;for (const auto& token : tokens) {if (isdigit(token[0]) || (token[0] == '-' && token.size() > 1 && isdigit(token[1]))) {stack.push(std::stoi(token));} else {int b = stack.top(); stack.pop();int a = stack.top(); stack.pop();if (token == "+") stack.push(a + b);else if (token == "-") stack.push(a - b);else if (token == "*") stack.push(a * b);else if (token == "/") stack.push(a / b);}}return stack.top();
}int main() {std::vector<std::string> tokens = {"2", "1", "+", "3", "*"};std::cout << "Result: " << evalRPN(tokens) << std::endl;return 0;
}

DFS（深度优先搜索）

在图或树的遍历中，DFS 使用栈来保存节点，以便后续访问。

算法思想

将起始节点入栈，访问节点并标记，然后将未访问的邻接节点入栈，直到没有未访问的节点。

代码实现（c++）

#include <iostream>
#include <vector>
#include <stack>void DFS(int start, const std::vector<std::vector<int>>& graph) {std::vector<bool> visited(graph.size(), false);std::stack<int> stack;stack.push(start);while (!stack.empty()) {int node = stack.top();stack.pop();if (!visited[node]) {std::cout << node << " ";visited[node] = true;}for (int neighbor : graph[node]) {if (!visited[neighbor]) {stack.push(neighbor);}}}
}int main() {std::vector<std::vector<int>> graph = {{1, 2},      // Node 0 connected to nodes 1 and 2{0, 3, 4},   // Node 1 connected to nodes 0, 3, 4{0, 5},      // Node 2 connected to nodes 0, 5{1},         // Node 3 connected to node 1{1},         // Node 4 connected to node 1{2}          // Node 5 connected to node 2};DFS(0, graph);  // Starting from node 0return 0;
}

求括号表达式的结果

计算一个包含括号的表达式值，可以通过使用栈来辅助计算。

算法思想

使用栈保存操作数和运算符，在遇到括号时，处理内部表达式。

代码实现（c++）

#include <iostream>
#include <stack>
#include <string>int calculate(const std::string& s) {std::stack<int> stack;int num = 0, result = 0, sign = 1;  // sign: 1 表示正，-1 表示负for (char c : s) {if (isdigit(c)) {num = num * 10 + (c - '0');} else if (c == '+') {result += sign * num;sign = 1;num = 0;} else if (c == '-') {result += sign * num;sign = -1;num = 0;} else if (c == '(') {stack.push(result);stack.push(sign);result = 0;sign = 1;} else if (c == ')') {result += sign * num;num = 0;result *= stack.top(); stack.pop();  // Apply previous signresult += stack.top(); stack.pop();  // Add previous result}}result += sign * num;return result;
}int main() {std::string expr = "1 + (2 - (3 + 4))";std::cout << "Result: " << calculate(expr) << std::endl;return 0;
}