c++ 栈
栈（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 0
return 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 sign
result += 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;
}
原文地址：https://blog.csdn.net/www_dong/article/details/143926954
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！