c++ std::stack总结
概念
std::stack 是 C++ 标准库中的一个容器适配器（Container Adapter）。它通常是基于其他容器（如 std::deque 或 std::vector）实现的，提供了一个后进先出（LIFO，Last In First Out）的元素访问顺序。栈只能在栈顶（top）进行插入和删除操作，因此它只暴露了有限的接口，操作简单高效。
特点
-
后进先出（LIFO）：栈总是从栈顶访问元素，栈顶的元素总是最新的。
-
动态大小：栈的大小可以动态增长和缩小，当有元素压入或弹出时栈的大小会相应改变。
-
封装性强：
std::stack不允许直接访问底层容器的数据（除了栈顶元素），保证了栈操作的封装性。
成员函数
push(): 向栈顶插入元素。
stack.push(value); // 将元素 value 压入栈顶
pop(): 弹出栈顶元素。
stack.pop(); // 移除栈顶元素
top(): 获取栈顶元素，但不移除它。
stack.top(); // 返回栈顶元素
empty(): 检查栈是否为空。
stack.empty(); // 如果栈为空返回 true，否则返回 false
size(): 返回栈中的元素数量。
stack.size(); // 返回栈的元素数量
底层容器
std::stack 是一个容器适配器，意味着它依赖于底层容器来存储数据。默认情况下，std::stack 使用 std::deque 作为底层容器，也可以显式选择使用 std::vector 或 std::list。
std::stack 是一个模板类，它可以接受两个模板参数：
- 元素类型（
T）：栈中存储的元素类型。 - 底层容器类型（
Container）：用于存储元素的底层容器类型，默认是std::deque<T>。
第二个参数允许我们指定底层容器，如 std::vector 或 std::list。底层容器必须支持以下操作：
push_back()pop_back()back()empty()- size()
示例一：常规用法
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
// 向栈中压入元素
s.push(10);
s.push(20);
s.push(30);
// 输出栈顶元素
std::cout << "Top element: " << s.top() << std::endl; // 输出 30
// 弹出栈顶元素
s.pop();
// 输出新的栈顶元素
std::cout << "New top element: " << s.top() << std::endl; // 输出 20
// 检查栈是否为空
if (s.empty()) {
std::cout << "The stack is empty" << std::endl;
} else {
std::cout << "The stack is not empty" << std::endl; // 输出栈不为空
}
// 输出栈的大小
std::cout << "Stack size: " << s.size() << std::endl; // 输出 2
return 0;
}
示例二：使用 std::vector作为底层容器
#include <iostream>
#include <stack>
#include <vector>
int main() {
// 使用 std::vector 作为底层容器
std::stack<int, std::vector<int>> s;
s.push(10);
s.push(20);
s.push(30);
// 输出栈顶元素
std::cout << "Top element: " << s.top() << std::endl; // 输出 30
s.pop();
std::cout << "New top element: " << s.top() << std::endl; // 输出 20
std::cout << "Stack size: " << s.size() << std::endl; // 输出 2
return 0;
}
示例三：使用 std::list作为底层容器
#include <iostream>
#include <stack>
#include <list>
int main() {
// 使用 std::list 作为底层容器
std::stack<int, std::list<int>> s;
s.push(100);
s.push(200);
s.push(300);
// 输出栈顶元素
std::cout << "Top element: " << s.top() << std::endl; // 输出 300
s.pop();
std::cout << "New top element: " << s.top() << std::endl; // 输出 200
std::cout << "Stack size: " << s.size() << std::endl; // 输出 2
return 0;
}
示例四：自定义容器
#include <iostream>
#include <stack>
#include <deque>
// 自定义容器（必须支持 push_back, pop_back, back, size, empty）
template<typename T>
class CustomContainer {
private:
std::deque<T> data; // 使用 deque 存储数据
public:
void push_back(const T& value) { data.push_back(value); }
void pop_back() { data.pop_back(); }
T& back() { return data.back(); }
const T& back() const { return data.back(); }
bool empty() const { return data.empty(); }
size_t size() const { return data.size(); }
};
int main() {
// 使用自定义容器作为底层容器
std::stack<int, CustomContainer<int>> s;
s.push(42);
s.push(84);
s.push(126);
std::cout << "Top element: " << s.top() << std::endl; // 输出 126
s.pop();
std::cout << "New top element: " << s.top() << std::endl; // 输出 84
std::cout << "Stack size: " << s.size() << std::endl; // 输出 2
return 0;
}
适用场景
-
表达式求值（后缀表达式，逆波兰表示法）：栈常用于计算后缀表达式或中缀表达式的转换。
-
括号匹配：栈常用于检查表达式中的括号是否匹配。
-
深度优先搜索（DFS）：在图的遍历中，栈用于模拟递归的调用栈。
-
回溯算法：栈可以用于回溯算法的状态追踪。
-
撤销操作：栈可用于实现撤销操作的功能，在需要回退到上一步的场景中非常有用。
性能
-
时间复杂度：
push()、pop()、top()、empty()、size()操作都是常数时间 O(1)。 -
空间复杂度：
std::stack使用底层容器存储数据，因此其空间复杂度取决于底层容器的实现（std::deque或std::vector）。
总结
std::stack 是一个非常简单且高效的容器适配器，适合处理需要后进先出（LIFO）顺序的场景。它提供了基本的栈操作：压栈、弹栈、查看栈顶元素、检查栈是否为空等。它常用于表达式求值、图的遍历、括号匹配等实际问题。
原文地址：https://blog.csdn.net/www_dong/article/details/143982683
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！