stack 栈 & queue 队列（C++ STL）
前言
本文围绕 C++ STL 中的三种容器适配器展开：stack（栈）、queue（队列）。它们本身不是独立容器，而是对底层容器的封装与接口限制，因此理解它们的接口语义和底层容器选择，是正确使用它们的关键。
文章会逐一介绍三者的常用接口、元素进出规则，并说明为什么stack与queue默认使用deque作为底层容器，而priority_queue默认使用vector，帮助你在实际场景中做出合适的选择。
底层：stack、queue不是容器，是容器适配器，默认底层用 deque stack：LIFO 后进先出 queue：FIFO 先进先出
为什么默认用 deque 作为底层容器
deque是双端队列，在头部和尾部插入、删除元素都是常数时间复杂度，而且不需要像vector那样在扩容时整体搬移已有元素，因此stack的push/pop和queue的入队/出队都能稳定地保持高效。
从内存角度看，deque由多段固定大小的缓冲区拼接而成，扩容时只需新增一段缓冲区，不会一次性申请大块连续内存，也不会产生大量元素拷贝，内存增长更平滑。
相比之下，vector要求元素在内存中连续存放，尾部操作虽然也是均摊常数时间，但一旦容量不足就要重新申请更大的连续空间并搬移全部元素，而头部插入删除更是 O(n) 的整体移动，对queue的队首弹出很不友好。
结论：需要双端高效操作、又不要求随机访问和内存连续性时，deque是stack与queue更合适的默认底层容器；vector更适合只在尾部操作、且看重连续内存与缓存友好的场景（例如priority_queue）。
stack<int> s1| 接口 | 作用 |
|---|---|
push(val) | 入栈，压到栈顶 |
pop() | 弹出栈顶元素，不返回值 |
top() | 返回栈顶元素引用（不会删除） |
empty() | 判断是否为空，空返回 true |
size() | 返回栈中元素个数 |
stack没有迭代器，不能遍历！只能操作栈顶。
template< class T, class Container = deque<T> > class stack;stack<int> s1; s1.push(1); s1.push(2); cout << st.top(); // 2 s1.pop(); cout << st.top(); // 1栈不能遍历！
stack 没有迭代器，不能 for 循环遍历，只能不断 top+pop。
queue 队列
template< class T, class Container = deque<T> > class queue;底层默认容器：deque
queue<int> q;常用接口
表格
| 函数 | 作用 |
|---|---|
push(x) | 入队，加到队尾 |
pop() | 弹出队首（不返回元素） |
front() | 返回队首元素 |
back() | 返回队尾元素 |
empty() | 是否为空 |
size() | 元素数量 |
同样：pop () 只删除，不返回值
queue<int> q; q.push(1); q.push(2); cout << q.front(); // 1 q.pop(); cout << q.front(); // 2queue 也没有迭代器，不能直接遍历。
| 容器 | 规则 | 取元素位置 | 删除位置 | 底层默认 |
|---|---|---|---|---|
| stack | LIFO 后进先出 | top () 栈顶 | pop () 栈顶 | deque |
| queue | FIFO 先进先出 | front () 队首 | pop () 队首 | deque |
| priority_queue | 按优先级 | top () 最值 | pop () 最值 | vector |
stack 和 queue 叫容器适配器（container adapter）它们本身不是独立容器，只是封装了 deque/vector，限制接口，只留下栈 / 队列行为。
总结
- stack（栈）：规则为 LIFO 后进先出，取元素位置是
top()栈顶，删除位置是pop()栈顶，默认底层容器为deque。 - queue（队列）：规则为 FIFO 先进先出，取元素位置是
front()队首，删除位置是pop()队首，默认底层容器为deque。 - priority_queue（优先队列）：规则为按优先级出队，取元素位置是
top()最值，删除位置是pop()最值，默认底层容器为vector。 - 易错点一：
pop()只删除元素，不返回被删除的值，需要先通过top()或front()取值再pop()。 - 易错点二：三者都没有迭代器，不能直接遍历，只能通过各自的取元素接口逐个访问，或不断取值加
pop()的方式清空。
面试高频细节问答
Q1：为什么 stack 和 queue 默认用 deque？
deque 头尾增删 O (1)，连续分段内存，扩容开销优于 vector；stack 只用尾部，queue 头尾都要用。vector 头部删除不行，list 随机访问差、内存碎片多。
Q2：为什么 priority_queue 底层默认 vector？
堆是完全二叉树，适合用连续数组存储，下标计算父子节点很方便，vector 连续内存缓存友好。
Q3：可以用 stack 遍历全部元素吗？
只能 top+pop 依次拿，拿出来就删掉；如果想要保留数据，要全部 pop 出来存到别的容器再装回去。
Q4：为什么 stack、queue 不提供迭代器？
设计目的是限制访问，只暴露栈 / 队列接口，保证 LIFO/FIFO 语义；如果开放迭代器，就可以随意修改中间元素，破坏抽象。
Q5：空容器调用 top/front/back/pop 会抛异常吗？
不会抛异常！标准规定是 UB，这点和 Java 不一样，Java 会抛异常。必须手动 empty 判断。