4. stack与queue容器：基本概念与常用接口
说实话，stack和queue这两个容器，是我日常开发中使用频率最高的数据结构之一。它们不像vector那样"万能"，但恰恰因为功能单一，反而在某些场景下特别顺手。今天我就带你彻底搞懂这两个"专一"的容器。
4.1 stack基本概念
stack，中文叫栈，是一种后进先出（LIFO，Last In First Out）的数据结构。什么叫后进先出？说白了就是：你最后放进去的东西，反而最先被拿出来。
我打个比方你就明白了——就像一摞盘子。你洗完一个盘子就叠在上面，要用的时候呢，肯定先拿最上面的那个。这就是典型的栈结构。
核心特点：
- 只能从栈顶操作元素（不能从中间插入或删除）
- 没有迭代器（不能遍历，只能看栈顶）
- 底层默认用deque实现（但也可以指定vector或list）
嗯，这里要注意：stack其实是一个容器适配器，不是独立的容器。它只是对底层容器做了封装，只暴露了有限的接口。我个人觉得这种设计很巧妙——限制操作反而减少了出错的可能。
4.2 stack常用接口
stack的接口非常少，我数了数，核心的就那么几个。你花5分钟就能记住。
| 接口 | 作用 | 时间复杂度 |
|---|---|---|
push() |
将元素压入栈顶 | O(1) |
pop() |
弹出栈顶元素（无返回值） | O(1) |
top() |
返回栈顶元素的引用 | O(1) |
empty() |
判断栈是否为空 | O(1) |
size() |
返回栈中元素个数 | O(1) |
你看，就这么几个。我刚开始学的时候觉得这也太简单了吧？但后来发现，越简单的接口，用起来反而越不容易出错。
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
// 压入元素
s.push(10);
s.push(20);
s.push(30);
std::cout << "栈顶元素: " << s.top() << std::endl; // 输出30
// 弹出栈顶
s.pop();
std::cout << "弹出后栈顶: " << s.top() << std::endl; // 输出20
std::cout << "栈大小: " << s.size() << std::endl; // 输出2
// 清空栈（没有clear接口，只能循环pop）
while (!s.empty()) {
s.pop();
}
return 0;
}我曾经踩过的坑：
调用top()或pop()之前，一定要先检查栈是否为空！否则程序会直接崩溃。我在项目里见过有人写while(s.pop())这种代码——pop没有返回值，这么写是错的。正确的做法是先检查!s.empty()再pop。
4.3 queue基本概念
queue，队列，和stack正好相反——它是先进先出（FIFO，First In First Out）的。你想想看，就像排队买奶茶，先来的人先买到，后来的人排后面。
queue也是容器适配器，底层默认用deque。它有两个口：队尾用来入队，队头用来出队。数据从队尾进来，从队头出去。
核心特点：
- 只能在队尾插入，队头删除
- 同样没有迭代器
- 常用于任务调度、消息队列等场景
4.4 queue常用接口
queue的接口和stack几乎一样对称，只是名字不同。
| 接口 | 作用 | 时间复杂度 |
|---|---|---|
push() |
在队尾插入元素 | O(1) |
pop() |
弹出队头元素（无返回值） | O(1) |
front() |
返回队头元素的引用 | O(1) |
back() |
返回队尾元素的引用 | O(1) |
empty() |
判断队列是否为空 | O(1) |
size() |
返回队列中元素个数 | O(1) |
#include <iostream>
#include <queue>
int main() {
std::queue<std::string> q;
// 入队
q.push("任务A");
q.push("任务B");
q.push("任务C");
std::cout << "队头: " << q.front() << std::endl; // 任务A
std::cout << "队尾: " << q.back() << std::endl; // 任务C
// 出队
q.pop();
std::cout << "出队后队头: " << q.front() << std::endl; // 任务B
// 遍历队列（注意：queue不支持迭代器，只能这样遍历）
while (!q.empty()) {
std::cout << "处理: " << q.front() << std::endl;
q.pop();
}
return 0;
}小技巧：
如果你需要遍历queue但不破坏数据，可以先把元素拷贝到另一个容器里。我在项目中处理消息队列时经常这么干——先备份再处理，防止处理失败后数据丢失。
4.5 stack与queue对比总结
为了让你看得更清楚，我画了一张对比图。
从图上你能直观地看到：stack是"一头操作"，queue是"两头操作"。stack只有一个出入口，queue有两个——一个进一个出。
4.6 实际应用场景
我在项目中用过不少stack和queue的场景，给你举几个例子：
- stack应用：括号匹配检查、表达式求值、撤销操作（Ctrl+Z）、函数调用栈
- queue应用：消息队列、任务调度、BFS广度优先搜索、打印机任务排队
我个人习惯：
如果只是需要"先进后出"或"先进先出"的功能，优先用stack/queue而不是vector。为什么？因为接口少，代码意图更清晰。别人一看你用stack，就知道你是后进先出的逻辑，不用猜。
好了，stack和queue的基本内容就这些。它们虽然简单，但用好了能解决很多实际问题。你写代码的时候，遇到"排队"或者"后进先出"的场景，第一时间想到它们就对了。
公众号:蓝海资料掘金营，微信deep3321