C STL 里的 stack 和 queue算是所有容器里最没存在感的两兄弟。用的时候就是一个 push、一个 pop、再取个头尾元素代码量少到惊人以至于很多初学者以为它们只是“数组配两个操作函数”的小把戏。但实际上这两兄弟背后藏着 STL 容器设计里非常值得玩味的一层结构——容器适配器。你往前翻翻 C 面试八股十次有八次会问你 stack 的底层是什么、queue 能不能用 vector 实现、为什么 pop 不直接返回被弹出的元素。今天我不打算空谈这些理论直接带着你用 C 模板从零把它们的关键操作全部写下来顺带把常见的坑和性能取舍一起捋清楚。这篇文章适合刚学完 C 基础、想搞懂 STL 内部逻辑的人也适合准备面试、想从原理层面把适配器讲明白的同学。1. 先从整体思路说起为什么这两个容器值得手写一遍1.1 stack 和 queue 到底是什么stack 是栈后进先出LIFO你往里面压数据取的时候永远先取到最后放进去的那一个。想象食堂里一摞餐盘保洁阿姨往上面放一个阿姨来拿的时候永远拿最上面的那个这就是栈的物理模型。queue 是队列先进先出FIFO奶茶店排队先到先点餐谁排得早谁先买走这就是队列的物理模型。这两个结构在 STL 里的地位很特殊。它们不是完整意义上独立的数据结构容器而是“容器适配器”。什么叫适配器你可以理解成一个转换插座底层已经有一个能干活的数据结构比如 deque、vector、list适配器把这层结构包装一下对外只暴露栈或队列的语义接口底层实现藏起来不给你看。所以 stack 内部并没有自己的一套内存管理逻辑它只是调用了底层容器的 push_back、pop_back、back 这些成员函数把接口重新组织成 push、pop、top 这样更贴合栈语义的方法。从零实现这两个类本质上就是在做“接口包装”这件事。1.2 容器适配器的设计思路以及为什么默认底层是 dequeSTL 里 stack 和 queue 的默认底层容器都是 deque双端队列。为什么选它不选 vector因为 deque 的头部插入和删除是常数复杂度vector 做不到。vector 的底层是连续内存的一段数组头部删除要搬动所有剩余元素复杂度是 O(n)deque 则是分段连续的结构每一段是一个连续缓冲区段之间通过映射指针连接因此头尾两端都能高效地插入和删除。这个特性刚好让 deque 同时满足 stack 和 queue 的需要stack 只需要尾部操作queue 需要尾部入队、头部出队。适配器模式的核心价值在于“底层容器可替换”。你写一个 stack传入的模板参数默认是 deque但也可以显式传入 vector 或 list接口完全不变。这就带来一个非常实际的好处如果你对性能有特殊要求比如栈里的元素数量固定、且连续内存的缓存命中率高更利于访问你完全可以std::stackint, std::vectorint这样实例化代码逻辑一行不改。手写实现的时候我也建议保留这个模板参数设计这是理解适配器模式的关键一步。2. 核心接口拆解stack 栈的所有关键操作逐个实现2.1 栈的接口语义与几个反直觉的设计stack 对外暴露的接口不算多但每个接口的设计都有讲究。核心接口是这几个push 入栈、pop 出栈、top 取栈顶元素、empty 判空、size 取元素个数。其中有两个反直觉的点。第一个top 返回的是“引用”不是“值”。这意味着你可以通过st.top() 42来直接修改栈顶元素。标准库的设计就是让用户拿到栈顶的引用自己去决定是只读还是修改。我在实现时必须同时提供top() const和top()两个重载前者给 const 对象用返回const_reference后者给普通对象用返回reference。第二个pop 不返回被弹出的元素返回值是 void。很多初学者第一次看到这个设计都懵了“我弹出一个元素连它是谁都不告诉我”这是 C98 时代 STL 就定下的规矩原因很简单返回元素值就需要构造一个临时对象再往外拷贝一次 pop 会多一次不必要的拷贝开销如果元素类型没有拷贝构造函数甚至直接编译失败。所以标准库的用法是两步走先用top()拿到元素处理再调用pop()删除元素。从零实现的时候如果你忍不住想做一个“能在一次调用里同时拿到并弹出元素”的 pop那你跟标准库的分歧就出现了建议先收住这个念头把标准接口老老实实还原出来。2.2 模板类设计思路与完整实现我直接用模板实现底层容器作为第二个模板参数默认给 deque。类内部只有一个成员变量Container c_所有操作都委托给它。为什么用组合而不是继承因为组合更安全能避免继承带来的虚函数开销也避免底层容器的所有接口被无差别暴露给外部。stack 只需要按栈的语义暴露接口不需要用户直接碰到底层容器的 insert、erase、sort 这些操作。完整实现如下#include deque #include utility template typename T, typename Container std::dequeT class Stack { public: using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; Stack() default; explicit Stack(const Container c) : c_(c) {} bool empty() const { return c_.empty(); } size_type size() const { return c_.size(); } reference top() { return c_.back(); } const_reference top() const { return c_.back(); } void push(const value_type value) { c_.push_back(value); } void push(value_type value) { c_.push_back(std::move(value)); } void pop() { c_.pop_back(); } void swap(Stack other) noexcept(noexcept(c_.swap(other.c_))) { c_.swap(other.c_); } bool operator(const Stack rhs) const { return c_ rhs.c_; } bool operator!(const Stack rhs) const { return !(*this rhs); } bool operator(const Stack rhs) const { return c_ rhs.c_; } bool operator(const Stack rhs) const { return rhs *this; } bool operator(const Stack rhs) const { return !(rhs *this); } bool operator(const Stack rhs) const { return !(*this rhs); } private: Container c_; };代码里的几个关键点我展开说一下。top()调的是c_.back()因为栈顶就是底层容器的最后一个元素push调push_back入栈就是把元素追加到尾部pop调pop_back把尾巴删掉。这个映射关系非常清晰你只要记住“栈顶等于容器尾部”整段代码就全部能推导出来。我加了右值引用的push(value_type value)重载这是 C11 之后的标准库形态。当你传入一个临时对象时不会发生拷贝而是直接把资源转移进容器。比如st.push(10)会走这个右值版本少一次拷贝构造对于 string 这种带动态内存的类型收益尤其明显。这也是“所有关键操作”里容易被忽略的一个细节。swap我用noexcept(noexcept(...))做条件异常规格表达底层容器的 swap 不抛异常那我的 swap 也不抛。这是给那些依赖强异常保证的代码用的算是进阶细节。2.3 实现细节里的三个隐藏坑第一个坑是top()的 const 版本。如果你只写了top()不写top() const那对一个const Stackint对象调用 top 会直接编译失败。因为 const 对象的所有非静态成员函数默认是 const 的只能调用 const 成员函数。STL 容器的习惯做法是“读操作都给 const 和 non-const 双版本”我也照做了别偷懒少写一个。第二个坑是空栈调用top()或pop()属于未定义行为。标准库不负责帮你检查你调用就是踩悬崖。所以实际使用时if (!st.empty()) { st.pop(); }这种判空代码是必须的。我自己实现的时候也故意不做检查跟标准库保持一致因为加检查意味着每次操作都有分支判断和潜在异常这对性能敏感场景是不可接受的。第三个坑是关于默认构造和移动构造。我这个类没有自定义拷贝构造函数和析构函数所以编译器会生成正确的默认拷贝构造、默认移动构造、默认拷贝赋值等。但如果你在后续扩展中手写了一个拷构函数编译器就不会再帮你生成移动构造了你会发现 push 右值的行为意外地退化成拷贝。这个属于 C 的“特殊成员函数生成规则”踩过一次就会长记性。3. queue 队列的关键操作与实现3.1 队列接口和 stack 的相似与不同queue 的接口跟 stack 非常像也是 push、pop、empty、size 这几个区别在于取元素的方式栈用top()取栈顶队列用front()取队首、用back()取队尾。这个区别直接反映了数据结构的本质差异栈只有一个可访问端点队列有两个端点可以读但只能在一端进、另一端出。push 对应入队往队尾放元素也就是底层容器的push_backpop 对应出队把队首元素移出去也就是底层容器的pop_front。因为要同时支持头部弹出和尾部追加底层容器必须是能高效做这两件事的类型。vector 没有pop_front成员函数所以如果你写std::queueint, std::vectorint编译时直接报错“vector 不提供 pop_front”。这也是面试里经常问到的点queue 为什么不能用 vector 做底层答案是接口不支持不是效率问题。3.2 queue 的完整实现queue 的实现与 stack 的结构完全对称只是底层操作换成 front、back、pop_front。#include deque #include utility template typename T, typename Container std::dequeT class Queue { public: using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; Queue() default; explicit Queue(const Container c) : c_(c) {} bool empty() const { return c_.empty(); } size_type size() const { return c_.size(); } reference front() { return c_.front(); } const_reference front() const { return c_.front(); } reference back() { return c_.back(); } const_reference back() const { return c_.back(); } void push(const value_type value) { c_.push_back(value); } void push(value_type value) { c_.push_back(std::move(value)); } void pop() { c_.pop_front(); } void swap(Queue other) noexcept(noexcept(c_.swap(other.c_))) { c_.swap(other.c_); } bool operator(const Queue rhs) const { return c_ rhs.c_; } bool operator!(const Queue rhs) const { return !(*this rhs); } bool operator(const Queue rhs) const { return c_ rhs.c_; } bool operator(const Queue rhs) const { return rhs *this; } bool operator(const Queue rhs) const { return !(rhs *this); } bool operator(const Queue rhs) const { return !(*this rhs); } private: Container c_; };接口映射关系仍然是直白的入队就是push_back出队就是pop_front队首是front队尾是back。注意front()和back()都返回引用所以你可以直接修改队首或队尾的元素。但这里有一个和 stack 不一样的地方queue 的两个端点都对外暴露这其实是比标准 queue 更强一点的能力。标准库也这么设计我没做额外限制。3.3 front/back 两个接口的边界情况先看front()和back()的判空问题。空队列调用它们同样是未定义行为这不是“返回一个默认值”的事你可能拿到一个被悬空的引用之后程序表现出各种诡异问题。实际项目里我见过不止一次某段代码在队列偶尔为空时崩溃定位半天发现是漏了判空。再看引用失效问题。front()返回的引用在后续 push 之后可能会失效这取决于底层容器的实现。deque 在两端插入元素不会使已有元素的引用失效但如果你用 list 做底层节点的引用则一直有效如果用 vector 做 stackpush 扩容时所有已有元素的引用全部失效。这些行为其实是底层容器决定的适配器底层换一个容器引用语义就全变了。最后一个边界是“修改队首元素的连锁影响”。因为front()返回非 const 引用q.front() 10会直接改变队首元素的值。如果你只想观察队首而不想改动它应该调用const对象上的front()或者把一个 const 引用绑定到q上再取 front。这个细节在写算法题时非常容易踩坑特别是想用引用绑定队列元素、回头又发现队列已经被修改了。4. 实操检查与常见问题排查实录4.1 写一个覆盖所有关键操作的测试用例手写代码之后必须跑测试否则你自己都不知道有没有写对。我习惯用一个临时测试文件把关键路径都走一遍包含入栈出栈顺序、判空、大小、引用修改等场景。比如 stack 的测试可以这样写#include iostream #include vector #include my_stack.h // 换成你自己的头文件 int main() { Stackint st; std::cout std::boolalpha; std::cout initial empty: st.empty() \n; st.push(1); st.push(2); st.push(3); std::cout size after push: st.size() , top: st.top() \n; st.top() 100; std::cout top after set: st.top() \n; while (!st.empty()) { std::cout pop: st.top() \n; st.pop(); } std::cout final empty: st.empty() \n; // 用 vector 做底层 Stackint, std::vectorint st_vec; st_vec.push(10); st_vec.push(20); std::cout vector-based stack top: st_vec.top() \n; return 0; }queue 的测试思路同理push 三个元素依次打印 front、pop验证顺序是 1、2、3再看 empty 和 size 的变化。记住测试不是走过场要把“top 修改引用”这种边界行为也测到不然你以为 top 只读实际拿到引用却一直没发现。4.2 常见编译错误与逻辑错误速查表把我在实际教学和调试中碰过的高频问题整理成一张表你对照着排错事半功倍错误现象原因解决方法pop后程序行为诡异空容器未判空就调用 pop/top/front/back调用前先判empty()top/front返回后修改无效容器对象是 const调用了 const 版本返回 const 引用去掉 const或使用 non-const 对象调用编译报错no member named pop_front in vector用 vector 作为 queue 的底层容器改用 deque 或 list模板实例化失败提示Container::value_type无法解析类模板内部使用嵌套类型时缺少typename关键字检查所有别名声明是否加了typename Container::xxx移动 push 没有被调用无法确认是否走了重载元素类型不可移动或容器没有右值重载给容器增加push(value_type)重载自定义了拷贝构造后移动构造神秘消失特殊成员函数生成规则导致移动构造被抑制显式声明Stack(Stack)或使用编译器默认规则其中第一个错误绝对是重灾区。很多人在用标准库容器时习惯性不判空那是因为数据规模小、运气好没出问题。一旦数据来自外部输入时序稍有变化空容器调用 pop 就成了炸弹。我在自己封装的小组件里甚至考虑过提供try_pop这样的安全版本但为了跟标准库行为保持一致最终没有加只是在调用处强制要求判空。4.3 不同底层容器的实测体感三个常见底层容器vector、deque、list适配到 stack 上表现差异明显。我用自己的压测程序跑了 100 万次 push 加 100 万次 pop结论虽然算不上严格基准但体感差距是稳定的。vector作为 stack 的底层速度最快连续内存、缓存命中率高push_back 均摊 O(1)。劣势是扩容时全部元素搬迁但如果提前reserve好容量扩容开销几乎为零。适合对性能极致敏感、且数据量可预估的场景。deque默认选择头尾操作都是均摊 O(1)分段结构让它在尾部插入时不一定触发大规模数据搬迁。实测比 vector 慢大概 10% 到 20%但换来了“可以支持 queue”的灵活性。如果你要在一个工程里同时使用 stack 和 queue又不想维护两套底层容器deque 是最省心的公共选择。list节点分散在堆上每次 push 都伴随一次节点内存分配性能最差缓存也不友好。但它的优势是“插入操作不会让已有迭代器失效”在需要长期持有元素引用、并且频繁增删的场景里反而更安全。不过作为适配器的默认底层它明显不合格只适合特殊需求。我还试过自己写一个固定容量的数组循环队列作为 queue 底层容器效果意外的好。因为它既不需要频繁分配内存也没有复杂的分段索引逻辑对于生产环境里数据量固定、追求稳定低延迟的场景这比直接用 deque 更好。这正体现了适配器模式的终极灵活性你可以为不同的场景换上最合适的底层容器而调用方看到的接口完全不变。5. 进阶思考与个人心得5.1 为什么 stack/queue 不提供迭代器一个经常被忽略的问题是标准库的 stack 和 queue 为什么不提供迭代器原因是语义不允许也不应该允许。迭代器代表“可以在容器内部随意移动遍历”但栈和队列的核心约束就是“只能访问端点元素”。如果给了迭代器你就能用循环遍历整个栈甚至可以修改中间元素那“栈”的抽象就名存实亡了你会写出违背数据结构的代码。STL 的严谨之处在于它宁可让这两个适配器的能力看起来“残缺”也要守住语义边界。但这不代表底层容器没有迭代器。我在实现时Container c_本身是 dequedeque 有完整的随机访问迭代器。只是这个迭代器藏在 private 成员里外部拿不到因为我没有把 c_ 暴露出去也没有提供任何返回迭代器的接口。这就是封装的意义数据结构的行为约束是靠接口裁剪达成的而不是靠程序员自律。5.2 从手写代码中收获的东西写完这两个类之后我最大的收获并不是背熟了接口映射而是彻底理解了 STL 容器分层设计的哲学。底层容器负责内存和数据的物理组织适配器负责语义和行为的抽象约束两者通过模板参数解耦。这比单纯地“学会使用 std::stack”要重要得多因为以后面对任何新的容器或者面试题你都能从一个更高的视角去分析它的内部结构和设计动机。有一次面试面试官问“给一个已有的 stack 类增加一个 getMin 操作你会怎么设计”我在脑子里迅速过了一遍自己写过的这个 Stack 类结构马上想到可以额外维护一个平行的最小值栈利用双栈结构把 getMin 压到 O(1)。这就是亲手实现过的底气。如果你只停留在 API 调用层面碰到这种题大概率只能在“用另一个 stack 存最小值”这个结论上绕来绕去说不出底层的数据变化关系。最后分享一个小技巧你可以在自己实现的 Stack 上做一个小扩展加一个emplace方法利用变参模板把参数直接转发给底层容器的emplace_back这样可以在栈顶原地构造元素。template typename... Args void emplace(Args... args) { c_.emplace_back(std::forwardArgs(args)...); }这个方法在性能上比“先构造再 push”少一次拷贝/移动也是 C11 之后标准库适配器的重要接口之一。我实际用下来在存储大量复杂对象时内存分配次数会明显下降。把这两兄弟从零写一遍之后再把 emplace、swap、移动语义这些扩展点补上你对 STL 的理解会比单纯刷题扎实得多。