最近复习数据结构翻出以前刷过的一道老题——堆盘子。这题最早是我刚学完栈的时候写的当时憋了两百多行还自以为封装得很优雅。前几天重新拿起来做发现思路完全打开了写的代码不到原来一半还把 C 的模板、移动语义、容器适配器、迭代器失效这些坑重新捋了一遍收获比当年大得多。这篇文章就当一份学习记录把两次做题的对比、设计取舍和踩过的坑都摊开来讲。堆盘子这题本身不算难但考的东西很综合。它要求你实现一个由多个栈组合而成的复合结构对外暴露的接口和单个栈保持一致。题目常见版本来自某本流传很广的算法面试准备书实现一个 SetOfStacks 数据结构内部包含若干个栈每个栈有容量上限push 时如果当前栈满了就新建一个栈pop 时如果最后一个栈空了就销毁它。除了常规 push/pop还会要求实现一个 popAt(index)指定从第几个栈弹出元素。这个接口看着简单其实把边界情况全搅在一起了。这篇记录适合正在学 C、准备算法面、或者想回头打磨基础的人看尤其是和我一样刷过一遍就以为自己会了的那类人。1. 题目拆解堆盘子到底在考什么1.1 先把题目还原清楚先给一个具体的运行场景。假设每个栈的容量是 2依次 push 1、2、3、4、5结构内部会变成三摞栈01 2 栈13 4 栈25这时候如果调用 pop应该弹掉 5然后栈2变成空栈整个结构只剩两摞。如果调用 popAt(0)弹掉的是 1结构变成栈02 栈13 4 栈25如果继续 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::stackint()); } 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::vectorstd::stackint 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 的 SetOfStackspush 时条件总是成立每次都新建一个栈然后马上放元素结果每个栈大小是 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_rangepopAt 的 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。把它改成模板类templatetypename T, typename Container std::vectorT 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 templatetypename T, typename Container std::vectorT 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::stackT, Container; templatetypename U void push_impl(U x) { if (stacks_.empty() || stacks_.back().size() capacity_) { stacks_.emplace_back(); } stacks_.back().push(std::forwardU(x)); } void removeBackIfEmpty() { if (!stacks_.empty() stacks_.back().empty()) { stacks_.pop_back(); } } std::listStackType 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() { SetOfStacksint 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 是常数时间。popO(1)。只看最后一个栈的 top 和 pop如果这个栈空了就销毁list 的 pop_back 也是常数时间。popAtO(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 版本更不容易犯错。如果你也想拿这道题练手我建议按这个顺序来先不写代码把如果删除中间空栈索引会怎样变化想清楚列出所有接口在空、满、中间删除三种状态下的行为最后动手实现。能把这个过程给自己讲明白这道题才算真的会了而不是又增加了一道刷过但没懂的题。