说实话在 C 里写业务代码写了几年之后我一度觉得自己和 STL 已经熟得不能再熟了。vector、map、unordered_map 天天用stack 和 queue 也顺手就来。但直到有一次准备面试被问到一个很基础的问题——std::stack 的底层到底是什么容器为什么默认是 deque 而不是 vector——我发现自己其实一直在用它却从没真正懂它。这个项目就是冲着这个懂字去的不借助标准库的现成实现从零手写一个与 STL 行为对齐的 stack 和 queue再把它们丢进几个典型算法场景里跑一遍看看适配器模式在实际工程里到底怎么发挥作用。做完之后最大的感受是这两个容器看似简单但背后涉及的容器适配器设计、底层结构选型、迭代器失效规则、以及在不同算法中的性能差异足够写出一篇有分量的总结。这篇文章就是完整的复盘记录适合正在学数据结构与算法的同学也适合那些天天用 STL 但想补一补底层功课的工程师。1. 项目概述为什么要手写一遍 stack 和 queue1.1 看似简单却很少有人真正答对的容器适配器先做个小测试。你可以在心里默答这三个问题std::stack 默认基于哪个容器实现std::queue 支持随机访问吗支持下标操作吗把 stack 的底层容器换成 vector会有任何功能差异吗第一题大部分人能答出 deque但第二题和第三题能立刻准确说清楚的人不多。原因在于我们平时用 stack 和 queue 的时候习惯性地把它们当成数据结构来理解而忘了它们在 STL 里其实是一层适配器——底层真正干活的是另一个容器。stack 和 queue 本身并不持有任何数据它们只是对外暴露一组受限的接口stack 只允许在一端操作queue 只允许一端进一端出。这种限制接口的设计思想在工程上叫适配器模式。它做的事情很简单把底层容器的丰富接口包装成一组更精简、更符合特定语义的接口。比如 deque 本身有 push_back、push_front、pop_back、pop_front、operator[] 等等一大堆接口但经过 adaptor 包装之后stack 只露出 push、pop、top 三个核心操作queue 只露出 push、pop、front、back。这一点理解透了后面所有的实现细节都会变得顺理成章。1.2 这个项目能带来什么适合谁读手写一遍 stack 和 queue表面上是在重复造轮子但实际收获有三层。第一层是最直白的你会彻底搞懂适配器模式的 C 实现手法包括模板模板参数、类型别名、委托调用这些平时写业务代码不太会主动用的语法。第二层是容器选型的工程直觉为什么默认是 deque换成 vector 和 list 各自会付出什么代价这些问题只有当你自己动手写过一遍之后才会有体感。第三层是算法层面的栈和队列在算法题里的出场率极高括号匹配、表达式求值、BFS 层序遍历、单调栈、单调队列全是它们的主场把这些场景一次性练完数据结构和算法的地图基本上就点亮了一大块。所以这篇文章的阅读对象很明确正在啃数据结构与算法的学生准备面试的候选人以及想补底层功课的 C 工程师。如果你是刚接触 STL 的新手跟着代码走一遍也能有收获我会把每个设计决策背后的原因都讲清楚不只是贴代码。2. 底层容器选型为什么默认是 deque 而不是 vector2.1 三种候选容器的对比动手实现之前最核心的问题就是选底层容器。stack 需要在一端插入删除queue 需要在一端插入、另一端删除。理论上 vector、list、deque 都能胜任但工程表现差异很大。先看 vector。它在尾部插入删除是 O(1) 均摊这对 stack 来说堪称完美。但是对 queue 来说就麻烦了如果直接用 vector 做 queuepop 是 pop_front 语义意味着每次都要把整个数组向前搬移复杂度变成 O(n)。如果退而求其次用 pop_back 加一个头指针来模拟循环队列接口又变得不再直观而且这个头指针的维护很容易出错。再看 list。它是一个双向链表头尾操作都是 O(1)做 stack 和 queue 都没有功能问题。但链表的节点是单独分配的每一个元素都有额外的指针开销会导致缓存命中率很差。数据量小的时候感觉不出来数据量一上去性能差距会非常明显。最后是 deque。它本质上是一段一段连续存储的分段数组维护一个中控器map来管理各段缓冲区。它同时支持头尾两端的 O(1) 插入删除还支持随机访问。这简直是给 stack 和 queue 量身定做的。而且它不像 list 那样每个元素都带指针空间局部性比 list 好得多。这就是为什么 STL 把 deque 作为 stack 和 queue 的默认底层容器。2.2 deque 的结构原理与工程优势deque 的内部结构值得多讲两句因为理解了它你才能真正明白为什么默认选它。deque 的逻辑视图是一段连续空间但物理上是一块一块固定大小的缓冲区分开存放的。中间有一个叫 map 的映射表本质上是一个指针数组每个指针指向一块缓冲区。当需要在头部插入元素时如果第一块缓冲区满了就在 map 前面再挂一块新的缓冲区尾部同理。这种结构的直接好处是不需要像 vector 那样整体搬移数据所以头尾插入都是 O(1)同时它又保持了某种连续感支持随机访问虽然随机访问的常数比 vector 大一点要多一次间接寻址但在绝大多数场景下可以忽略。相比 list 的逐节点分配deque 一个缓冲区能装多个元素分配次数少得多缓存命中率自然也更好。所以结论很清晰stack 用 deque 是因为它尾插尾删 O(1) 且缓存友好vector 其实也能胜任 stack 但 STL 为了统一选择了 dequequeue 用 deque 是因为它需要头部删除也是 O(1)vector 做不到这一点。这个选型逻辑是写进标准库的工程决策不是拍脑袋定的。2.3 适配器模式接口隔离与灵活替换真正动手写代码之前还有一个设计层面的关键点要说清楚就是适配器模式带来的可替换性。stack 和 queue 的模板签名是template class T, class Container dequeT第二个模板参数就是底层容器。这意味着使用者可以显式传入自己想要的容器。正因为接口被隔离了替换底层容器才不会影响上层逻辑。你可以在 stack 里传std::vectorT在 queue 里传std::listT只要这个容器提供了 push_back、pop_backstack或 push_back、pop_frontqueue这些操作就行。这个约束在 C 里是通过表达式合法性来体现的模板实例化的时候编译器会在 Stack 类里生成c.push_back(...)这样的调用如果你传入的容器不支持这个操作编译直接报错。这其实就是 C 静态多态的一种形态没有虚函数没有继承完全靠模板在编译期完成接口匹配。理解了这个点你就明白为什么标准库把对象成员命名为ccontainer并且对它的要求是提供某些成员函数而不是继承自某个抽象基类。这是 STL 一贯的哲学通过概念约束而不是类继承来组织代码。这种设计让适配器变得极其灵活也是我在实现中刻意模仿的核心。3. 核心代码模拟实现从零手写 stack 和 queue3.1 stack 的模拟实现与代码拆解直接上代码。我定义了一个命名空间my_stl避免和标准库的std::stack混淆。namespace my_stl { 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 cont) : c(cont) {} explicit stack(Container cont) : c(std::move(cont)) {} 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)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(stack other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }代码很短但每个细节都有讲究。类型别名的作用是让使用者可以通过stackT, Container::value_type拿到元素的类型这在泛型编程里很常用也是标准库的习惯。push我写了两份重载一个接收左值引用一个接收右值引用。右值版本里直接std::move(value)转给底层容器避免了一次拷贝。很多手写实现只写一份push(const T)数据量大时性能会差很多这里值得多写几行。emplace是另一个容易被忽略的点。它接受可变参数包然后完美转发给底层容器的emplace_back。这样你可以直接在容器里构造对象连临时对象都不用创建。比如st.emplace(1, 2)可以直接构造一个 pair而push则需要先构建 pair 再拷贝进去。构造函数的写法也有讲究。我提供了接受底层容器的构造方式这在需要拿现有数据初始化栈的场景非常有用。注意第二个构造函数用了explicit防止临时容器被隐式转换成 stack避免发生让人意想不到的隐式类型转换。3.2 queue 的模拟实现与代码拆解接着写 queue核心逻辑和 stack 几乎一样只有操作方向不同。namespace my_stl { 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 cont) : c(cont) {} explicit queue(Container cont) : c(std::move(cont)) {} 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)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(queue other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }queue 和 stack 的区别一眼就能看出来它多了front和back两个访问接口push走push_backpop走pop_front。这正是先进先出语义的物理体现——进队从尾部进出队从头部出。这里我要特别提醒一个入门时经常犯的错误front()和back()在队列为空的时候调用是未定义行为。很多新人喜欢先取再判或者干脆不判空程序在小数据量时跑得好好的一上大数据就随机崩溃。防这个问题的习惯要尽早养成任何pop、top、front操作之前先想清楚这个容器是不是可能为空。3.3 几个值得注意的实现细节写到这里有几个细节值得展开好好讲因为它们决定了这个实现能不能真正对齐 STL 的行为。第一swap的异常说明。我在swap后面加了noexcept(noexcept(c.swap(other.c)))这是条件 noexcept 的写法。意思很简单如果底层容器的 swap 不会抛异常那我的 swap 也就是 noexcept。写库代码时这种细节很加分因为标准库容器之间的交换是强异常安全保证的使用者如果依赖了 swap 不抛异常的特性比如在std::swap泛型版本里用到它条件 noexcept 能保证你不会因为一个本该稳的操作遇到意外的 try-catch。第二top()返回的是引用而不是值。这一点和很多人直觉不同。reference top() { return c.back(); }意味着你可以直接修改栈顶元素st.top() 42;。返回引用避免了拷贝也暴露了修改能力这正是标准库的行为。同理queue 的front()和back()也是引用。写模拟实现时如果只图省事返回了值会让使用者误以为栈顶是只读的行为和标准库就不一致了。第三pop和top在标准库中是分离的操作。栈顶元素不会因为 pop 而返回给你想拿到栈顶值必须T x st.top(); st.pop();。这是标准库十几年前就定下的设计——返回值和修改容器状态分开可以避免异常安全问题。如果top返回栈顶的同时把元素移除万一在拷贝返回值的过程中抛异常元素就凭空消失了。分离之后即使拷贝失败栈的状态也原封不动。第四关于受保护成员c。我故意把底层容器设为protected而不是private和标准库保持一致。这给派生类留了一条后路你可以从 stack 派生一个子类直接访问c来扩展功能。比如你想给 stack 加一个print_all()方法或者加一个peek_from_bottom()没有protected这些就做不到了。不过要提醒一句标准库从 C11 开始明确不保证容器适配器的继承安全性日常工程里还是优先用组合而非继承protected只当作一个兼容性的保留选项。4. 典型算法场景实践栈与队列真正发力的地方4.1 栈的经典场景括号匹配与表达式求值实现了容器就该把东西扔进真实战场里检验了。栈在算法中最经典的一类场景就是匹配和回溯。先看括号匹配。这个题目在所有算法入门教程里都会出现原因很简单它完美展示了栈的最近匹配特性——后遇到的左括号要先闭合这正是后进先出的语义。bool isValidBrackets(const std::string s) { std::stackchar st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.empty()) return false; // 没有可匹配的左括号 char top st.top(); if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; // 类型不匹配 } st.pop(); } } return st.empty(); // 栈不空说明有未闭合括号 }这段代码短小但包含两个容易漏的判空点遇到右括号时先检查栈空不空这是处理]这种以右括号开头的输入遍历结束后还要再检查一次栈是否为空这是处理(((这种只有左括号的输入。这两个边界必须都覆盖否则就是典型的本地跑通了一提交就 WA的情况。表达式求值则是栈的另一个战场。经典的双栈法操作数栈 运算符栈处理中缀表达式时核心思想是保证运算符的优先级正确。遇到数字就压操作数栈遇到运算符就先把栈顶那些优先级不低于当前运算符的先算掉再压栈。这里面大量依赖取栈顶但不急着弹出的操作正好验证了我前面说过的top()和pop()分离设计的合理性——你经常需要看一眼栈顶才能决定下一步动作。我这里把完整的表达式求值代码省略了因为展开会很长但思路值得记住表达式求值本质上就是延迟计算遇到低优先级运算符时被迫结算之前的高优先级部分这个过程和栈的天然行为严丝合缝。4.2 队列的经典场景BFS 与树的层序遍历队列的最强场景就是广度优先搜索。BFS 的特点是按层推进每一层先入队的节点先被访问这和队列先进先出的特性完全吻合。以二叉树的层序遍历为例这是 BFS 思想在树结构上的最直观体现struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint result; if (root nullptr) return result; std::queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 当前层的节点数关键 std::vectorint level; level.reserve(levelSize); for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(std::move(level)); } return result; }这里最关键的技巧是int levelSize q.size();。因为队列在遍历过程中会不断有新节点入队如果你在循环条件里直接写i q.size()循环次数会随着队列增长而失控所有节点被当作同一层输出。先把当前层节点数存下来循环次数就锁定在这一层了新入队的节点留给下一次外层循环处理。这个快照 size的写法是层序遍历和网格 BFS比如岛屿数量问题中反复使用的模式。另外一个值得记住的经验是当 BFS 的访问顺序要求不够用时比如最短路径问题你经常需要把路径长度也放进队列里。常见的做法是队列元素存(节点, 步数)的 pair或者建两个队列分别同步维护。第一种写法更稳就是内存多一点第二种写法省空间但代码容易出错。我建议初学者优先用 pair把正确性先保住优化留给需求明确之后再做。4.3 单调栈与单调队列两个进阶但非常实用的技巧如果前面的都是基础那单调栈和单调队列就是栈和队列在算法竞赛与面试里真正拉开差距的地方。它们的共同思想是让栈或队列中的元素保持单调性递增或递减从而在 O(n) 时间内解决原本需要 O(n^2) 的问题。先说单调栈。经典题目下一个更大元素给一个数组对每个元素找到右边第一个比它大的元素找不到就用 -1。暴力的做法是双重循环O(n^2)。单调栈的做法是维护一个从栈底到栈顶递减的栈std::vectorint nextGreaterElement(const std::vectorint nums) { int n nums.size(); std::vectorint result(n, -1); std::stackint st; // 栈里存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { result[st.top()] nums[i]; // 当前元素就是栈顶的下一个更大元素 st.pop(); } st.push(i); } return result; }核心逻辑在这个 while 循环里所有被当前nums[i]弹出的栈顶元素它们的下一个更大元素就是nums[i]。单调栈能成立的前提是——每个元素最多进栈一次、出栈一次所以总复杂度 O(n)。理解单调栈的要诀是谁被弹出了谁就得到了答案。栈里存下标而不是元素值是因为我们需要用下标去回填结果数组比较大小的时候通过nums[st.top()]间接访问。再说单调队列。经典题目滑动窗口最大值求所有长度为 k 的滑动窗口里的最大值。如果用优先队列做每次要处理过期元素代码绕如果每次都暴力扫窗口复杂度 O(nk)。单调队列的做法是让队列中的元素从队头到队尾递减队头永远是当前窗口的最大值std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::vectorint result; std::dequeint dq; // 存下标从队头到队尾递减 for (int i 0; i (int)nums.size(); i) { // 1. 入队前弹出队尾所有比当前元素小的 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 2. 弹出已经滑出窗口的队头 if (dq.front() i - k) { dq.pop_front(); } // 3. 窗口形成后记录队头 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; }这里的运行原理很有意思当新元素比队尾大时不管这个队尾元素还能在窗口里活多久它都不可能成为窗口最大值了——因为新元素既比它大又比它年轻。所以果断弹出这就是淘汰无用候选的贪心思想。我自己第一次写单调队列时卡了很久原因是搞混了两条队列的用途。如果只是用一个普通 queue 保存窗口元素那你只能知道先进先出的顺序没法快速淘汰中间那些又小又老的元素。单调队列用的实际上是我模拟实现的 deque 提供的双端操作能力。所以这里要强调一点前面花了大篇幅讲的deque双端 O(1) 操作在这里真刀真枪地派上了用场。你完全可以用我实现的那个my_stl::queue来跑 BFS但是滑动窗口最大值这种场景必须用 deque 的双端特性这也是为什么单调队列在有些资料里直接叫双端队列优化。5. 常见问题与性能陷阱实录5.1 我踩过的那些坑自己手写容器适配器最容易在几个地方翻车我都踩过一遍整理出来给大家避雷。第一个坑是忘判空。有人觉得栈和队列有别于数组天然安全。实际上恰恰相反容器的空状态就是它的边界区。我在第一次用自写的stack跑括号匹配时就遇到过程序崩溃原因就是输入以右括号开头st.top()访问了空栈。从那以后我养成一个习惯对任何容器适配器执行top()、front()、pop()之前先检查empty()即便有时候感觉不会空。空栈访问 top 是未定义行为它不会给你返回一个奇怪的默认值而是可能直接段错误——而且不是每次都崩溃是看心情这种 bug 极难排查。第二个坑是迭代器失效。stack 和 queue 刻意没有暴露迭代器所以这个问题主要出现在直接用底层容器操作时。我用 deque 做单调队列时在pop_back弹出的过程中还持有一个指向被弹出元素的引用然后回头再访问它读到的是完全无效的数据。经验是凡是调用了可能改变容器结构的操作push、pop、resize之前拿到的引用和迭代器一律视为失效需要重新获取。第三个坑是编译错误信息特别绕。当我把 queue 的底层容器显式指定为 vector 时报的错误乍看完全看不懂因为 vector 没有pop_front成员。编译器只是在一堆模板实例化深处默默报了一句class std::vectorint has no member named pop_front。这个报错的含义其实很简单你的容器不满足适配器的接口要求。排查思路是顺着报错信息里的模板参数链往回找找到底是哪个容器类型、哪一行调用出问题。现在 C 概念concept的编译器提示已经友好很多了但老编译器上这种报错依然能把人整懵。5.2 性能对比与容器替换建议我实际跑过一组小实验数据量在 100 万级别的 push/pop 场景下stack 的两种底层容器表现差异不大vector 甚至略快于 deque——因为 vector 尾部连续内存缓存极友好。但 queue 场景就完全不同了。直接用 vector 模拟队列头删因为元素搬移复杂度直接退化到 O(n)100 万数据量下耗时高到无法接受用 list 做 100 万级 push_pop 交替耗时大约是 deque 的两到三倍原因是节点分配和指针跳跃带来的缓存开销。这个实验结果其实和 STL 的设计逻辑完全一致stack 用 vector 替代是可选优化queue 用 list 替代是能跑但慢deque 在两边都是均衡最优。日常开发里如果你能确定某个 stack 只做尾部操作且性能关键显式传 vector 是合理的但 queue 场景不必折腾deque 就是正解。另外 C11 之后还有一个选择如果对空间极度敏感可以用std::vector加头指针手写环形队列作为 queue 的底层但这已经属于你自己实现了容器的范畴复杂度不小普通项目不值得。5.3 面试高频追问整理把这次实践沉淀的考点列一下不管是准备面试还是自测都很有用。为什么 stack 默认用 deque 而不用 vector答vector 尾部操作虽然更快但 deque 头尾都是 O(1)STL 为了统一 stack 和 queue 的默认容器选择并且保证 stack 在真正需要时也能在两段操作选了 deque。重点是先说明适配器模式再谈性能权衡。vector 能作为 queue 的底层容器吗答能模板实例化但几乎所有操作都是 O(n)因为 pop 需要搬移元素。stack 和 queue 有什么区别除了接口它们的底层容器可以互换吗答功能接口不同但只要容器满足各自接口要求stack 需要 back/push_back/pop_backqueue 需要 front/back/push_back/pop_front就可以互换。为什么 stack 不提供迭代器答因为适配器的存在意义就是限制访问方式提供迭代器会破坏栈的只能在一端操作语义。std::queue 支持q[i]吗答不支持queue 没有 operator[]这就是接口被适配器隔离的直接体现。如果想随机访问用原始容器。这些问题如果都能流利答上来说明你真的把容器适配器这个概念吃透了。我当初栽在第一个问题上就是因为在用的层面停留太久没有上升到设计的层面去理解它。5.4 关于自写容器的一点额外建议最后想多说一句关于造轮子这件事。很多人觉得模拟实现 STL 容器在实际工作中没意义毕竟标准库又稳又快。但我自己的体会是手写一遍最大的价值不是替代标准库而是让你获得一种底层直觉。当你遇到为什么这里用 queue 会超时、为什么换成 deque 就快了这种问题的时候你能立刻定位到问题本质而不是在网上翻半天帖子。这种直觉是纯看书很难获得的。我在实际开发中虽然很少真的用自写的 stack 和 queue 去替代标准库但我会在本地用它们做实验验证自己的性能猜想。比如想确认 list 做队列真的慢多少、vector 做栈是否真的更快就分别用自写版本跑一遍一目了然。这个习惯帮我避过不少盲目优化的坑——很多所谓优化跑完数据之后发现根本没必要反而增加了代码复杂度。我的建议是自写容器永远只当教学工具和性能实验工具生产代码里还是老老实实用标准库。标准库的实现在异常安全、版本演进、边界行为上都经过了极端测试这些隐性成本是自写版本很难追平的。