最近复习数据结构，翻出以前刷过的一道老题——"堆盘子"。这题最早是我刚学完栈的时候写的，当时憋了两百多行，还自以为封装得很优雅。前几天重新拿起来做，发现思路完全打开了，写的代码不到原来一半，还把 C++ 的模板、移动语义、容器适配器、迭代器失效这些坑重新捋了一遍，收获比当年大得多。这篇文章就当一份学习记录，把两次做题的对比、设计取舍和踩过的坑都摊开来讲。
堆盘子这题本身不算难，但考的东西很综合。它要求你实现一个由多个栈组合而成的复合结构，对外暴露的接口和单个栈保持一致。题目常见版本来自某本流传很广的算法面试准备书：实现一个 SetOfStacks 数据结构，内部包含若干个栈，每个栈有容量上限；push 时如果当前栈满了就新建一个栈，pop 时如果最后一个栈空了就销毁它。除了常规 push/pop，还会要求实现一个 popAt(index)，指定从第几个栈弹出元素。这个接口看着简单，其实把边界情况全搅在一起了。这篇记录适合正在学 C++、准备算法面、或者想回头打磨基础的人看，尤其是和我一样"刷过一遍就以为自己会了"的那类人。
1. 题目拆解：堆盘子到底在考什么
1.1 先把题目还原清楚
先给一个具体的运行场景。假设每个栈的容量是 2，依次 push 1、2、3、4、5，结构内部会变成三摞：
栈0：1 2 栈1：3 4 栈2：5这时候如果调用 pop，应该弹掉 5，然后栈2变成空栈，整个结构只剩两摞。如果调用 popAt(0)，弹掉的是 1，结构变成：
栈0：2 栈1：3 4 栈2：5如果继续 popAt(0)，弹掉 2，栈0空了，究竟要不要删除栈0？删除之后原来"栈0、栈1、栈2"的编号全部前移，变成"栈0、栈1"，那么之前拿到的索引就全失效了。这是整个题里最容易扯不清的地方。
题目的名字叫堆盘子，直观类比就是餐厅后厨的盘子：台面上摞盘子，摞太高容易倒，所以要换一摞新的。这个类比帮助理解"每个栈有上限"这个约束，但实际做题时真正的难点和盘子本身没关系，而是"多个栈怎么管理"这件事。
1.2 第一个考点：多份数据的生命周期怎么管
这是整套题最核心的问题。你可以让内部所有栈放在一个固定数组里，也可以动态扩容地追加删除。不管用哪种结构，都必须保证：
- push 时能找到正确的那个栈，并且当栈满时知道该新建一个；
- pop 时能找到最后一个非空栈，并且弹空后知道该删除；
- popAt 时能找到第 index 个栈，并且处理弹出的栈变空后的状态。
这道题很多人在第一次做的时候都会栽在"删除空栈"上。因为你会发现在 vector 中间 erase 一个元素，后续所有元素的索引都在变。如果调用方先记住了"栈1"这个索引，某个中间栈被删掉之后，他手里的索引指向的内容已经不是原来的了。这是设计层面的问题，不是 C++ 语法层面的问题，所以很多人都没意识到。
1.3 第二个考点：对外接口的一致性
题目要求 push/pop 的表现“和单个栈一样”。也就是说用户不需要知道内部拆成了几个栈，只要照着普通栈的用法调用就行。这个要求听起来简单，其实包含了两个含义：第一，push 永远要往最后一个有效位置放，不能因为中间有空栈就把新元素塞进洞里；第二，pop 永远要弹出最后放入的元素，也就是最靠后的栈的栈顶。
这个一致性非常容易被 "popAt 删掉了中间空栈" 破坏。比如删掉栈0之后，原来栈1变成新的栈0，那么下一次 push 应该进入新的栈0，还是保持和旧索引的对应关系？标准答案是前者，因为用户眼里只有一个栈。但很多第一版实现会把事情搞复杂，甚至维护一个"当前最后一个栈"的指针，最后发现这个指针在中间删除后指向了错误的对象。
1.4 第三个考点：性能与存储布局的权衡
最后一个隐藏考点是性能意识。不同的人会给完全不同的实现方案：
- 用 vector 存多个栈，好处是随机访问 O(1)、缓存局部性好；
- 用 list 存多个栈，好处是中间删除 O(1)，迭代器稳定；
- 用 deque 存多个栈，介于两者之间，但没有特别突出的点。
普通的面试讨论不会严格到逐字节分析，但你得说得出每种方案的代价。比如 vector 在中间删除时会把整个后半段往前搬，如果每个栈里已经有几百个元素，这个搬移成本就不容忽视。而 list 虽然中间删除便宜，但缓存不友好，而且每个节点都要单独分配内存。这种"为什么这样选"的思考，恰恰是旧题新做和第一遍刷题的最大区别。
2. 旧做法：凭直觉写出来的版本
2.1 第一版的核心思路
当年我第一版用的是最简单的方案：vector 套 stack。代码大概长这样：
#include <stack> #include <vector> class SetOfStacks { public: explicit SetOfStacks(size_t cap) : capacity_(cap) {} void push(int x) { if (stacks_.empty() || stacks_.back().size() == capacity_) { stacks_.push_back(std::stack<int>()); } stacks_.back().push(x); } int pop() { int x = stacks_.back().top(); stacks_.back().pop(); if (stacks_.back().empty()) { stacks_.pop_back(); } return x; } int popAt(size_t index) { int x = stacks_[index].top(); stacks_[index].pop(); if (stacks_[index].empty()) { stacks_.erase(stacks_.begin() + index); } return x; } private: std::vector<std::stack<int>> stacks_; size_t capacity_; };写完自己跑了一遍基本流程，push、pop 都好使，甚至 popAt 弹掉中间某个栈看起来也正常。当时我还挺得意，觉得几百朴素代码就能完成一个复合结构，已经不错了。
2.2 第一版里藏着的四个问题
问题其实不少，但当时的我根本看不出来。
第一，popAt 中间的删除会让索引错位。假如有三个栈，调用 popAt(0) 把栈0删了，原来的栈1变成新的栈0，原来的栈2变成新的栈1。下次再调用 popAt(1)，实际弹掉的已经不是用户心中那个"第二个栈"了。如果这只是单次调用还没问题，一旦混合 push、pop、popAt 连续操作，整个结构的语义就彻底乱了。题目要求的"对外像单个栈"，被这个错误直接破坏。
第二，没有处理空结构。pop() 里直接调 stacks_.back().top()，如果整个结构是空的，这是未定义行为，可能返回垃圾值，可能崩溃，完全靠运气。真正的产品代码里，空容器检查应该在访问之前，而不是依赖容器自己好心。
第三，没有考虑 capacity_ 为 0 的情况。如果你构造一个容量为 0 的 SetOfStacks，push 时条件总是成立，每次都新建一个栈，然后马上放元素，结果每个栈大小是 1，和容量 0 矛盾。正确的做法应该是构造时校验，容量必须大于 0。
第四，popAt 里直接 erase 除了索引问题，还有性能问题。vector 中间删除会把后面的元素整体前移，每个元素都是 std::stack，搬移成本可比搬一个 int 高多了。如果只在最后一个栈弹出，erase 的"后面没有元素"，成本低；但中间删除尤其最坏情况删第一个栈，后面所有栈都要被复制或移动一遍。
这四点是我后来重新做的时候才逐条意识到的。第一遍刷题的人，真的只会盯着"用例能不能跑通"，完全顾不上语义一致性和复杂度。
3. 重构计划：从接口设计倒推实现
3.1 先把接口定清楚，再谈内部怎么写
第二遍做这题，我换了个顺序：先不想内部用 vector 还是 list，而是把对外接口和错误处理策略先定下来。
接口只需要四个操作：
- void push(const T& / T&&)：往结构里放一个元素；
- T pop()：从最后一个栈弹出一个元素；
- T popAt(size_t index)：从第 index 个栈弹出一个元素；
- bool empty()：判断整个结构是否为空。
关于错误处理，我在 C++ 里倾向抛异常。pop 一个空结构抛 std::out_of_range，popAt 的 index 越界抛 std::out_of_range。也可以用 std::optional 作为返回值，让调用方自己决定怎么处理，但对这道题来说，异常更直接，也更符合"栈操作失败就是严重错误"的语义。
接口定下之后，内部的实现选择就有了判断标准：用户只关心弹出的值对不对，不关心内部是几个栈、栈在哪个位置。那么内部结构怎么折腾都行，只要保证操作后仍满足"普通栈的外在表现"。
3.2 这次为什么选 std::list 而不是 vector
这是这次重构最关键的取舍。我上一版用 vector 的主要理由是随机访问 O(1)，可以像 stacks_[index] 一样直接用下标。但题目又要求 popAt，这就会频繁出现"中间删除"。
用 list 的收益在这里刚好踩中痛点：
- 删除任意位置的空栈是 O(1)；
- 插入新栈不涉及元素搬移；
- 迭代器在被删除之前一直有效。
代价是随机访问只能靠 std::advance 一步步走，popAt 的时间复杂度就从 O(1) 降到了 O(index)。但仔细想，在大多数场景下，弹中间栈是一个低频操作，而背后节省的"删除时所有后续栈整体前移"成本，在栈元素多的时候非常可观。
更重要的是，list 改变了我的思考方式：我不能再靠下标来维持状态，必须用迭代器来定位。这迫使我把"索引"这个容易出错的抽象扔掉，转而直接操作容器里的元素位置。你会发现，迭代器才是 C++ 容器操作的正统语言，下标是 vector 特有的福利，不是所有容器都该有的默认思维。
3.3 顺手把它泛型化
既然重做，就没理由继续只支持 int。把它改成模板类：
template<typename T, typename Container = std::vector<T>> class SetOfStacks { ... };第二个模板参数是给内部每个栈选的底层容器。默认用 vector，意味着每个内部栈的存储是一段连续内存，缓存友好；如果你需要更快的头部插入，可以改成 deque，只要它满足 std::stack 对底层容器的要求即可。
模板化之后我还补了右值引用和完美转发的入口：
void push(const T& x) { push_impl(x); } void push(T&& x) { push_impl(std::move(x)); }这样临时对象进栈就不用多拷贝一次。对 int 这种平凡类型来说无所谓，但一旦 T 变成 string、vector 或者其他重对象，这个设计就能省下一整次深拷贝。
4. C++ 层面那些容易忽略的细节
4.1 std::stack 没有 clear()
这个细节我第一次是完全不知道的。想清空一个 std::stack，你只能循环调用 pop 直到 empty，因为标准库没有给它提供 clear()。原因也很简单：std::stack 是一个容器适配器，它故意把底层容器（deque、vector 或 list）的接口裁剪成最精简的"栈"操作，只保留 push、pop、top、size、empty 这些。clear 这种"批量破坏"的操作，被设计者认为不属于栈的语义范围。
这道题里，新增一个空栈是用 push_back 往外部容器里塞一个默认构造好的 std::stack，而"空栈"本身是合法的。所以很多人在写"判断栈空就销毁"逻辑时，会试图写 stacks_.back().clear()，结果编译报错。实际上应该 pop 掉元素直到 empty，然后由外部容器负责销毁栈这个对象。
4.2 top() 和 pop() 的正确顺序
std::stack 的 pop() 返回 void，不会把弹出的元素交给你。想拿到栈顶元素，必须先调用 top()，再调用 pop()。我见过很多新手写：
int x = stacks_.back().pop(); // 错误，编译都不通过正确的写法是：
int x = stacks_.back().top(); stacks_.back().pop();在这个基础上还要注意，top() 在空栈上是未定义行为。所以正确顺序永远是：先检查空、再 top、再 pop。这个顺序在 popAt 里同样成立：pop 掉一个栈的最后一个元素之后，那个内部栈立刻变成空栈，需要马上决定是保留还是销毁。
4.3 内部栈的底层容器：vector 还是 deque 有讲究
std::stack 的默认底层容器是 std::deque，不是 vector。deque 的优势是两端操作都 O(1)，劣势是元素不是连续存储，缓存命中率不如 vector。大多数算法题里，内部栈的访问模式非常规律，用 vector 做底层容器往往更快，因为 vector 的连续内存让 CPU 预取命中更高。
所以我在示例代码里把默认底层容器写成 std::vector ，而不是直接写 std::stack 。这不只是炫技，而是真实性能优化。测试容量较小的整数栈时，你可能感觉不到差异；当每个栈塞几百个复杂对象，并且 popAt 频繁触发跨栈操作时，局部性的差距就会放大。
另外，底层容器还决定了 stack 的移动成本。vector 作为底层容器时，整个 stack 的移动就是一次指针交换，非常廉价；deque 内部是分块结构，移动时需要搬移的控制信息更多一点。在 list 里创建新栈、删除旧栈频繁发生时，这个差距也会累计。
4.4 容器适配器的白名单心态
std::stack 是一个适配器，它的全部接口就那几个，你不能遍历它，不能按位置访问它，不能直接清空它。这种"最小可用接口"的设计，好处是误用很难，坏处是你常常得绕过它去做额外操作。
在这个题目里，我需要判断"最后一个栈是否满了"，用的是 stacks_.back().size() == capacity_。std::stack 提供了 size()，所以没问题。但如果我想"看看某个栈的第二个元素是什么"，std::stack 就完全做不到了，只能把上层元素全 pop 出来再放回去。这既是限制，也是提醒：当你发现自己在频繁想办法绕过适配器时，就该考虑是不是容器选错了。
5. 完整实现与测试：直接可用的版本
5.1 这次重构后的完整代码
基于前面所有讨论，我最终给出的实现如下：
#include <list> #include <stack> #include <stdexcept> #include <utility> template<typename T, typename Container = std::vector<T>> class SetOfStacks { public: explicit SetOfStacks(size_t per_stack_cap) : capacity_(per_stack_cap > 0 ? per_stack_cap : throw std::invalid_argument("capacity must be positive")) {} void push(const T& x) { push_impl(x); } void push(T&& x) { push_impl(std::move(x)); } bool empty() const noexcept { return stacks_.empty(); } size_t stackCount() const noexcept { return stacks_.size(); } T pop() { if (stacks_.empty()) { throw std::out_of_range("pop on empty SetOfStacks"); } T value = std::move(stacks_.back().top()); stacks_.back().pop(); removeBackIfEmpty(); return value; } T popAt(size_t index) { if (index >= stacks_.size()) { throw std::out_of_range("popAt index out of range"); } auto it = stacks_.begin(); std::advance(it, index); if (it->empty()) { throw std::logic_error("internal stack is unexpectedly empty"); } T value = std::move(it->top()); it->pop(); if (it->empty()) { stacks_.erase(it); } return value; } private: using StackType = std::stack<T, Container>; template<typename U> void push_impl(U&& x) { if (stacks_.empty() || stacks_.back().size() == capacity_) { stacks_.emplace_back(); } stacks_.back().push(std::forward<U>(x)); } void removeBackIfEmpty() { if (!stacks_.empty() && stacks_.back().empty()) { stacks_.pop_back(); } } std::list<StackType> stacks_; size_t capacity_; };几个值得说明的地方：
第一，构造函数里用了个小技巧。三目运算符的第二个分支是 throw 表达式，因为 throw 表达式的类型可以和第一个分支一致。这样写可以把"容量为0直接拒绝构造"压缩到一行，而且不会让 capacity_ 处于未初始化状态。
第二，push_impl 用了模板折叠加 std::forward。这是常见的完美转发写法，确保 T 是 int、string 或 unique_ptr 时都能正确处理。注意我用的是 emplace_back() 而不是 push_back(StackType())，前者直接构造，省了一次临时对象的移动。
第三，pop 和 popAt 都先把栈顶元素 move 出来，再调用 pop。这里有一个微妙但安全的行为：move 之后被弹出的元素在标准库容器看来是"合法但未指定"的状态，但 pop 会把它从容器中移除，所以不会有悬垂引用或重复释放的问题。
5.2 我跑过的测试用例
这里放一个可以直接编译运行的测试：
#include <iostream> int main() { SetOfStacks<int> ss(2); for (int i = 1; i <= 5; ++i) { ss.push(i); } std::cout << "stackCount = " << ss.stackCount() << "\n"; // 3 std::cout << "popAt(2) = " << ss.popAt(2) << "\n"; // 5 std::cout << "stackCount = " << ss.stackCount() << "\n"; // 2 std::cout << "pop() = " << ss.pop() << "\n"; // 4 std::cout << "pop() = " << ss.pop() << "\n"; // 3 std::cout << "popAt(0) = " << ss.popAt(0) << "\n"; // 1 std::cout << "popAt(0) = " << ss.popAt(0) << "\n"; // 2 try { ss.pop(); } catch (const std::out_of_range& e) { std::cout << "caught: " << e.what() << "\n"; } ss.push(100); ss.push(200); ss.push(300); std::cout << "stackCount = " << ss.stackCount() << "\n"; // 1 return 0; }预期输出：
stackCount = 3 popAt(2) = 5 stackCount = 2 pop() = 4 pop() = 3 popAt(0) = 1 popAt(0) = 2 caught: pop on empty SetOfStacks stackCount = 1这个测试逻辑覆盖了以下几种常见场景：
- 容量为 2 时 5 个元素会形成 3 个内部栈；
- popAt(2) 弹掉最后一个栈的唯一元素，栈自动销毁，栈数减到 2；
- 连续 pop 依次走过每个内部栈栈顶；
- popAt(0) 连续两次，第一次弹 1 留下 2，第二次弹 2 后栈0销毁；
- 空结构 pop 抛异常；
- 清空后再 push 能重新开始，容量逻辑不受影响。
我实际跑下来输出和上面预期完全一致，没有越界、没有崩。
5.3 复杂度分析要会算
很多人写代码时不计算复杂度，但这道题恰恰需要。
- push：平均 O(1)。如果当前栈没满，就是一次栈 push；满了就新建栈再 push。list 的 emplace_back 是常数时间。
- pop：O(1)。只看最后一个栈的 top 和 pop；如果这个栈空了就销毁，list 的 pop_back 也是常数时间。
- popAt：O(index + 1)。用 std::advance 在 list 里走到第 index 个栈，然后执行栈顶弹出。如果栈空，list 的 erase O(1)。所以最坏情况是 index 接近栈总数的时候，退化成 O(n)，n 是内部栈个数。
对比 vector 版本，popAt 在中间删除时的成本是 O(n * m)，n 是后续栈数，m 是每个栈的元素搬移成本。在栈元素很多时，list 版本的行为更可控。这也是我选择 list 的根本原因：这个题目里"删除中间空栈"是必经之路，让这个操作便宜下来，整个结构的维护成本就大幅下降。
6. 旧题新做：比多刷一道题更值的地方
这题重做一遍，我个人最深的体会不是"我终于会写 list 了"，而是"第一遍刷题和真正理解题之间的距离，比想象中大得多"。
第一遍我在乎的是跑通用例，第二遍在乎的是接口是否自洽、删除操作是否会让索引失效、空栈该删还是该留、底层容器该怎么选。这些问题在第一遍时全都看不见，因为代码能跑就满足了。回头看，当时那段代码在连续混合操作下根本稳不住，只是我根本没测到那个程度。
还有一个很实际的经验：做容器类设计时，先把操作频率排序。push、pop 是高频操作，popAt 是低频操作，那么优化方向就应该是保证 push、pop 干净利落，而不是为了 popAt 的 O(1) 牺牲太多。这次选择 list 并不是因为 list 什么都好，而是它让每个操作的成本都可控，而且代码写起来比 vector 版本更不容易犯错。
如果你也想拿这道题练手，我建议按这个顺序来：先不写代码，把"如果删除中间空栈，索引会怎样变化"想清楚，列出所有接口在空、满、中间删除三种状态下的行为，最后动手实现。能把这个过程给自己讲明白，这道题才算真的会了，而不是又增加了一道"刷过但没懂"的题。
