stack / queue 容器适配器

priority_queue 已单开一页（见 priority_queue.md），本页补齐 stack 与 queue。它们都属于容器适配器（container adaptor）——理解「适配器」这个抽象本身，比背接口更重要。

一、什么是容器适配器

适配器不是一个容器，而是「用另一个容器 + 限制接口」实现的抽象：

• 底层仍是一个真正的容器（默认 std::deque，也可指定 std::vector/std::list）。
• 但它屏蔽掉底层容器的大部分接口，只暴露符合某种数据结构语义的几个操作。
• 没有迭代器、不能遍历——这正是它和普通容器的本质区别。

std::stack<int> s1;                          // 默认底层 std::deque<int>
std::stack<int, std::vector<int>> s2;        // 指定底层 std::vector<int>
std::queue<int, std::list<int>> q;           // queue 也可用 list 做底层

一句话：适配器把「通用容器」包装成「特定行为的数据结构」。你只能 push/pop/top，不能 [i] 也不能遍历——接口越窄，越不容易用错。

二、std::stack（栈，LIFO）

头文件 <stack>。

std::stack<int> s;
s.push(1);        // 入栈
s.push(2);
s.top();          // 2，取栈顶（不弹出）
s.pop();          // 弹出栈顶（无返回值！）
s.size(); s.empty();

接口与复杂度（底层 deque，均为 O(1)）：

操作	作用
push(x) / emplace(args...)	入栈
top()	返回栈顶引用（不删除）
pop()	删除栈顶（无返回值）
size() / empty()	大小/判空

坑：pop() 不返回元素。想「取栈顶并弹出」必须两步：

int x = s.top();   // 先取
s.pop();           // 再弹

设计原因：若 pop() 返回元素，返回时发生拷贝，若拷贝抛异常，元素已从栈里弹出——破坏了强异常安全（这也是 C++ 标准库把「取值」和「删除」拆成两个函数的一贯理由）。

三、std::queue（队列，FIFO）

头文件 <queue>。

std::queue<int> q;
q.push(1); q.push(2);
q.front();   // 1，队首（最早入队）
q.back();    // 2，队尾（最晚入队）
q.pop();     // 弹出队首（无返回值）

操作	作用
push(x) / emplace(args...)	入队（加到队尾）
front()	队首（即将出队）
back()	队尾（刚入队）
pop()	弹出队首（无返回值）
size() / empty()	大小/判空

四、为什么默认底层是 deque？（高频追问）

std::stack / std::queue 默认用 std::deque 而非 vector 或 list，原因：

1. stack 只需尾插尾删：vector 也能做，但 deque 的尾部操作同样是 O(1)，且 deque 内存分段、不要求整块连续，扩容不会像 vector 那样整块搬移。
2. queue 需要头删尾插：vector 头删是 O(n)（要整体前移），直接淘汰；deque 两端都是 O(1)，完美匹配。
3. 相比 list：deque 随机访问 O(1)、缓存局部性更好、无每个节点的指针开销（list 每个节点 2 个指针）。

所以 deque 是「头尾都 O(1) + 无指针冗余 + 不必连续」的折中最优解。

追问点：std::stack 用 std::vector 做底层也合法且常见（连续内存、缓存更好），但 std::queue 用 vector 会退化（头删 O(n)）——所以 queue 千万别配 vector。

五、手写 stack / queue（思路）

面试手写一般不要求完整，讲清「用一个容器封装 + 限制接口」即可：

template <typename T>
class Stack {
    std::vector<T> c_;   // 或 deque / list，任选
public:
    void push(const T& x)      { c_.push_back(x); }
    void pop()                 { c_.pop_back(); }
    T& top()                   { return c_.back(); }
    bool empty() const         { return c_.empty(); }
    size_t size() const        { return c_.size(); }
};

要点：适配器就是组合（has-a）而非继承（is-a）——内部持有一个容器，把它的 push_back/back/pop_back 重命名为 push/top/pop。

六、高频问答

1. stack/queue 和 vector/list 是什么关系？ —— 不是继承关系，是「组合 + 接口裁剪」。适配器内部持有容器，暴露受限接口。
2. 为什么适配器没有迭代器？ —— 迭代器会暴露底层容器、允许任意遍历和修改，破坏「栈/队列」的语义约束。接口收窄正是适配器的目的。
3. std::stack::pop() 为什么返回 void？ —— 异常安全：若返回时拷贝构造抛异常，栈状态已被破坏。拆成 top() + pop() 保证安全。
4. 栈和递归的关系？ —— 函数调用栈本身是 LIFO；std::stack 常用来把「递归」改写成「迭代」（如树的非递归遍历、DFS）。
5. 单调栈 / 单调队列是什么？ —— 算法题高频：栈/队列内元素保持单调（如「下一个更大元素」「滑动窗口最大值」）。本质是利用 LIFO/FIFO + 弹出不满足单调性的元素，均摊 O(n)。

七、自测

1. std::stack 和 std::queue 的默认底层容器各是什么？为什么？
2. std::queue 能用 std::vector 做底层吗？会有什么后果？
3. 适配器与普通容器最本质的区别是什么？
4. 为什么 pop() 不返回被弹出的元素？