C++ stack 容器使用教程
一、简介
在 C++ 中，stack 是一个容器适配器，它遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后插入的元素将首先被移除。stack 只允许在一端（称为栈顶）进行元素的插入和移除操作，提供了一个简单而高效的栈数据结构。它可以使用不同的底层容器实现，默认情况下使用 deque 作为底层容器，但也可以使用 vector 或 list 等。
二、头文件
使用 stack 容器需要包含 <bits/stdc++.h> 头文件，并使用 using namespace std; 语句，这样可以方便地使用 STL 中的各种组件，包括 stack。
#include<bits/stdc++.h>
using namespace std;
三、创建 stack 对象
以下是几种创建 stack 对象的方式：
#include<bits/stdc++.h>
using namespace std;
int main() {
// 使用默认的底层容器（deque）创建一个存储整数的 stack
stack<int> s1;
// 显式指定底层容器为 vector 来创建存储浮点数的 stack
stack<float, vector<float>> s2;
// 显式指定底层容器为 list 来创建存储字符的 stack
stack<char, list<char>> s3;
return 0;
}
在上述代码中：
s1是一个存储int类型元素的stack，使用默认的底层容器deque。s2是一个存储float类型元素的stack，使用vector作为底层容器。s3是一个存储char类型元素的stack，使用list作为底层容器。
四、基本操作
1. 元素插入（push）
使用 push 操作将元素添加到栈顶。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
s.push(1); // 将元素 1 压入栈顶
s.push(2); // 将元素 2 压入栈顶
s.push(3); // 将元素 3 压入栈顶
// 此时栈中的元素顺序为：[3, 2, 1]，其中 3 是栈顶元素
return 0;
}
2. 元素删除（pop）
使用 pop 操作移除栈顶元素。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop(); // 移除栈顶元素 3
// 此时栈中的元素顺序为：[2, 1]，其中 2 是栈顶元素
return 0;
}
注意：pop 操作只是移除栈顶元素，不会返回该元素的值。
3. 访问栈顶元素（top）
使用 top 操作可以查看栈顶元素的值。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
int top_element = s.top(); // 获取栈顶元素的值，此时 top_element 的值为 3
cout << "Top element: " << top_element << endl;
return 0;
}
4. 检查栈是否为空（empty）
使用 empty 操作检查栈是否为空。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
cout << "Is stack empty? " << (s.empty()? "Yes" : "No") << endl; // 输出 "Yes"，因为栈为空
s.push(1);
cout << "Is stack empty? " << (s.empty()? "Yes" : "No") << endl; // 输出 "No"，因为栈不为空
return 0;
}
5. 获取栈的大小（size）
使用 size 操作获取栈中元素的数量。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << "Stack size: " << s.size() << endl; // 输出 3，因为栈中有 3 个元素
return 0;
}
五、示例代码
以下是一个完整的示例代码，展示了 stack 的基本操作。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
// 检查栈是否为空
if (s.empty()) {
cout << "Stack is empty." << endl;
}
// 向栈中添加元素
s.push(5);
s.push(10);
s.push(15);
// 输出栈的大小
cout << "Stack size: " << s.size() << endl;
// 访问栈顶元素
cout << "Top element: " << s.top() << endl;
// 移除栈顶元素
s.pop();
cout << "After pop, top element: " << s.top() << endl;
// 清空栈
while (!s.empty()) {
s.pop();
}
cout << "Stack size after clear: " << s.size() << endl;
return 0;
}
六、应用场景
1. 表达式求值
stack 常用于表达式求值，例如后缀表达式求值。
#include<bits/stdc++.h>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> s;
for (int i = 0; i < exp.length(); ++i) {
if (isdigit(exp[i])) {
s.push(exp[i] - '0');
} else {
int val1 = s.top(); s.pop();
int val2 = s.top(); s.pop();
switch (exp[i]) {
case '+': s.push(val2 + val1); break;
case '-': s.push(val2 - val1); break;
case '*': s.push(val2 * val1); break;
case '/': s.push(val2 / val1); break;
}
}
}
return s.top();
}
int main() {
string exp = "231*+9-";
cout << "Result: " << evaluatePostfix(exp); // 输出 -4
return 0;
}
2. 深度优先搜索 (DFS)
在图的深度优先搜索中，stack 可用于存储待访问的节点。
#include<bits/stdc++.h>
using namespace std;
// 假设图使用邻接表表示
vector<vector<int>> graph = {
{},
{2, 3},
{1, 4},
{1, 4, 5},
{2, 3, 5},
{3, 4}
};
void dfs(int start) {
stack<int> s;
vector<bool> visited(graph.size(), false);
s.push(start);
while (!s.empty()) {
int node = s.top(); s.pop();
if (!visited[node]) {
visited[node] = true;
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
int main() {
dfs(1); // 输出 1 3 5 4 2
return 0;
}
七、注意事项
- 在使用
pop操作前，最好先使用empty操作检查栈是否为空，以避免对空栈进行pop操作，否则会导致未定义行为。 top操作只能在非空栈上使用，否则会导致未定义行为。
通过本教程，你应该对 C++ 的 stack 容器有了较好的理解，并能熟练使用其基本操作。stack 是一个非常有用的数据结构，在很多算法和应用场景中都有广泛的应用，如表达式求值、函数调用栈、深度优先搜索等。希望这些示例和解释能帮助你更好地掌握 stack 的使用，在实际编程中灵活运用。如果你在使用过程中遇到任何问题，欢迎随时向我咨询。
请将上述内容保存为一个 .md 文件，使用支持 Markdown 格式的编辑器（如 Typora）打开，以便更好地查看代码和文档的格式。希望你在 C++ 编程学习中取得进步，如有更多疑问，可继续向我询问。
0 条评论
目前还没有评论...
