stack(c++)

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

1. 引入头文件

1
#include <stack>

2. 声明与初始化

1
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()判断栈是否为空,返回 truefalseO(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. 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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. 自定义底层容器

可以指定 vectorlist 作为底层容器:

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

7. 自定义栈的底层容器

stack 是一个容器适配器,它的底层容器可以是 deque(默认)或 vectorlist。你可以指定底层容器来优化性能或内存使用。

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

8. 迭代器

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

1
2
3
4
5
6
7
8
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)**。