stack(c++)

<stack> 是 C++ 标准库中的一个容器适配器，提供了一个后进先出 (LIFO) 栈的实现。

1. 引入头文件

#include <stack>

2. 声明与初始化

stack<int> s;          // 创建一个存储 int 类型的栈
stack<string> ss; // 创建一个存储 string 类型的栈

3. 常用方法

方法/成员	作用	复杂度	示例代码
push(val)	将元素 val 添加到栈顶	O(1)	s.push(10);
pop()	移除栈顶元素	O(1)	s.pop();
top()	返回栈顶元素的引用，但不移除	O(1)	int topElem = s.top();
empty()	判断栈是否为空，返回 true 或 false	O(1)	if (s.empty()) { /* do something */ }
size()	返回栈中元素的个数	O(1)	cout << s.size();
swap(s)	交换当前栈与另一个栈 s 的内容	O(1)	s1.swap(s2);
c	返回底层容器的引用，可以访问栈内元素（不推荐常用）	O(1)	auto& container = s._Get_container();
emplace()	在栈顶直接构造一个元素，避免复制开销	O(1)	s.emplace(1, 2);

4. 示例代码

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    // 添加元素
    s.push(1);
    s.push(2);
    s.push(3);
    // 访问栈顶元素
    cout << "栈顶元素: " << s.top() << endl; // 输出 3
    // 移除栈顶元素
    s.pop();
    cout << "移除栈顶后，新的栈顶: " << s.top() << endl; // 输出 2
    // 检查栈是否为空
    cout << "栈是否为空: " << (s.empty() ? "是" : "否") << endl;
    // 获取栈的大小
    cout << "栈的大小: " << s.size() << endl;
    return 0;
}

5. 注意事项

• stack 是基于底层容器（默认为 deque）实现的，只能通过提供的接口操作。
• 如果调用 top() 或 pop() 时栈为空，行为未定义，应在操作前检查栈是否为空。

6. 自定义底层容器

可以指定 vector 或 list 作为底层容器：

stack<int, vector<int>> s; // 使用 vector 作为底层容器

7. 自定义栈的底层容器

stack 是一个容器适配器，它的底层容器可以是 deque（默认）或 vector、list。你可以指定底层容器来优化性能或内存使用。

stack<int, vector<int>> s; // 使用 vector 作为底层容器
stack<int, list<int>> s;   // 使用 list 作为底层容器

8. 迭代器

stack 不支持直接访问栈内的元素，它不提供 begin() 和 end() 这样的迭代器。不过，你可以通过更改底层容器来使用迭代器。例如：

stack<int, deque<int>> s;
s.push(10);
s.push(20);

// 访问底层容器
for (auto it = s._Get_container().begin(); it != s._Get_container().end(); ++it) {
    cout << *it << endl; // 输出 10, 20
}

这里 s._Get_container() 获取栈的底层容器，然后通过迭代器访问。

9. 栈的常见应用场景

• 撤销操作：实现如文本编辑器中的撤销功能。
• 表达式求值：后缀表达式或中缀表达式的求值。
• 深度优先搜索（DFS）：可以用栈来模拟递归调用，遍历树或图结构。

10. 栈的性能

由于 stack 通常基于 deque 实现，因此大部分操作（push, pop, top, empty, size）的时间复杂度为 **O(1)**。