搞C的朋友很多都有类似的体验vector、list这些真正“装数据”的容器学完之后一碰到stack和queue反而有点懵。因为它们在STL里并不是新型存储结构而是站在现有容器肩膀上、只对外露出几个受限操作的“容器适配器”。这篇笔记我不打算复读文档而是想从“为什么存在”“怎么用最顺手”“底层怎么工作”“有哪些坑”四个角度把stack和queue彻底讲明白。如果你正在学STL或者刷题时老看到“用栈模拟递归”“用队列做层序遍历”的说法这篇文章应该能给你一份真正能落地的参考。1. 先弄明白stack和queue在C里到底是什么角色1.1 容器适配器不是“新容器”而是“新接口”我第一次看C标准库的目录时有个疑问stack和queue都没有迭代器也没有sort、find这些算法能用的接口。它们跟vector、list比起来像是“功能被阉割过的容器”。后来才意识到我理解反了。stack和queue的本质是“容器适配器container adapter”。它们自己不管理内存、不存储元素而是默认把deque双端队列包装了一层只暴露符合栈或队列语义的操作。就像自动售货机你看到的是一个个货道出口但实际上后面的货架、弹簧、滑动机构都是现成的。自动售货机本身并不生产货它只是把散装商品放进了固定的取货规则里。这个设计的直接后果是stack和queue的底层容器是可以替换的。你可以用vector当栈的底座也可以用list当队列的底座。只要这个底层容器支持适配器所需的操作接口就行。这一点非常像面向对象里的“接口隔离”思想也给使用者留了很大的弹性空间。1.2 LIFO和FIFO两套截然不同的“游戏规则”stack的核心规则是LIFOLast In First Out后进先出。它只允许在一端进行插入和删除这一端被称为栈顶。就像叠盘子最后一个放上去的盘子总是最先被拿下来。如果你往栈里依次放入1、2、3弹出的顺序一定是3、2、1。queue的核心规则则是FIFOFirst In First Out先进先出。它允许在一端插入、另一端删除。插入的一端叫队尾删除的一端叫队头。就像排队买票先来的人先进入窗口后来的人只能排在末尾。如果依次入队1、2、3出队顺序也一定是1、2、3。这两种规则看似简单但恰恰是很多算法的基础。函数调用栈用的是LIFO操作系统里的任务调度、打印机任务队列用的是FIFO。面试题里随处可见的括号匹配、表达式求值、层序遍历、滑动窗口最大值背后也都是这两种结构在支撑。1.3 适用人群与典型应用场景这篇笔记适合三类读者刚学完STL基础容器、想进一步弄懂stack和queue的初学者正在准备算法面试、需要快速复习底部原理和常见用法的求职者想优化代码结构、在合适场景选择合适容器类型的进阶开发者。在真实项目中stack最常见的应用是“需要回退”的场景比如编辑器里的Undo操作、浏览器里的后退功能、编译器的语法分析栈。queue最常见的应用是“需要排队”的场景比如线程池的任务队列、消息中间件里的缓冲队列、树的层序遍历。理解这些场景比死记硬背函数签名有用得多。2. 核心接口拆解把每个函数用透问清楚“为什么”2.1 stack接口就那么几个但细节不少stack对外暴露的接口其实很少我整理成了一张表接口作用复杂度备注push(const T val)在栈顶插入元素O(1)也可以传右值触发移动语义pop()删除栈顶元素O(1)不返回被删除的元素top()返回栈顶元素的引用O(1)分为const和非const版本empty()判断栈是否为空O(1)空栈调用top或pop是未定义行为size()返回栈中元素个数O(1)注意返回类型是size_t很多人第一次用stack时会写这样的代码int value st.pop(); // 错误pop不返回任何值这个用法是错的。标准设计上pop只管删除top负责获取值。所以要取栈顶元素再删除必须两步走int value st.top(); st.pop();那为什么不直接把两个操作合并成一个“弹出并返回”呢最直接的原因是异常安全。如果pop既要返回值又要删除元素那么返回值时需要拷贝或移动元素。一旦移动过程中抛出异常栈的状态已经改变了数据就丢了。拆成top和pop后你可以先安全地读取再手动删除给了程序员更大的控制权。C11之后emplace系列接口也加进来了。st.emplace(args...)可以直接在栈顶上就地构造元素避免一次额外的拷贝构造。对一个存放复杂对象的stack来说性能提升是可感知的。比如st.emplace(hello, 3)它会调用容器元素的构造函数而不是先构造一个临时对象再拷贝进去。2.2 queue接口front和back要分清楚queue的接口比stack稍微多了一个维度因为它有两端概念接口作用复杂度备注push(const T val)在队尾插入元素O(1)一般称入队pop()删除队头元素O(1)不返回被删除的元素front()返回队头元素的引用O(1)最早放入的元素back()返回队尾元素的引用O(1)最近放入的元素empty()判断队列是否为空O(1)空队列调用front/back是未定义行为size()返回队列中元素个数O(1)注意遍历时的动态变化第一次接触queue时我总把front理解成“前面的元素”把back理解成“后面的元素”但这容易踩坑。queue的front是队头也就是最早入队的那个元素back是队尾是最晚入队的那个元素。入队永远发生在back那一端出队永远发生在front那一端。如果你需要遍历一个queue不能拿迭代器因为它根本没有迭代器。常规做法是边弹出边访问while (!q.empty()) { int cur q.front(); q.pop(); // 处理cur }这个代码非常经典但有一个隐含信息遍历完这个queue它也就空了。如果之后还需要原来的数据就必须提前复制一份或者把弹出的元素再压回另一个容器。我在实际开发中因为没注意这一点吃过一次小亏某个模块里用queue暂存了任务处理一轮之后以为数据还在结果后续二次处理时队列已经空了日志查了很久才发现是遍历方式导致的数据丢失。2.3 底层容器的选型逻辑为什么默认是dequestack和queue的模板定义长这样templateclass T, class Container std::dequeT class stack; templateclass T, class Container std::dequeT class queue;默认底层容器都是deque而不是vector或list。原因很直接stack需要在一端做插入和删除。vector支持push_back和pop_back理论上是可行的所以std::stackT, std::vectorT也是合法的queue需要在两端操作一端插入、一端删除。vector没有高效的pop_front在头部删除元素需要移动后面所有元素时间复杂度会退化成O(n)显然不合适list两头操作都支持但list的节点在内存里不是连续的访问各个元素时缓存命中率较差空间开销也更大deque正好兼顾了“两端操作都是O(1)”和“内存相对连续、缓存友好”。deque的内存结构可以理解为多个连续缓冲区拼接起来的“伪连续”结构。它在中间插入元素仍然是低效的但在两端扩容时不会像vector那样频繁搬移整个数组而是按需申请新的缓冲区。这就让它成为stack和queue的默认底座。你也可以显式指定底层容器。比如希望queue的底层用list以支持中间插入虽然这违背了队列的语义但接口上允许或者希望stack底层用vector来提高缓存局部性。这种可替换性是适配器模式带给我们的自由度但绝大多数场景下让默认配置工作得够好。3. 实操演示三道典型问题 一个轻量级模拟实现3.1 括号匹配栈应用第一课括号匹配是学习stack最经典的练习。给你一个只包含()[]{}的字符串判断括号是否合法闭合。核心思想是遇到左括号就压栈遇到右括号就检查栈顶是否匹配匹配则弹出不匹配或者栈已经空了就返回false。#include stack #include string bool isMatch(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { return false; // 右括号来了但栈为空一定非法 } char topChar st.top(); if (!isMatch(topChar, c)) { return false; // 栈顶和当前右括号不配对 } st.pop(); } } return st.empty(); // 结束后栈为空才说明全部配对 }这段代码有几个细节值得展开左括号入栈后最近的左括号一定在栈顶刚好对应“最后遇到的未匹配左括号”天然匹配右括号的闭合顺序右括号出现时优先判断st.empty()避免对空栈调用top()产生未定义行为遍历结束后还要再查一次st.empty()因为可能存在“左括号多了”的情况比如((()。我在实际调试时发现很多人会漏掉“结束后检查栈是否为空”这一步。如果只检查匹配过程而不校验最终状态那)(或(()这种非法字符串就会被误判为合法。3.2 层序遍历队列在二叉树里的经典用法二叉树层序遍历是queue最直观的应用。每一层按从左到右的顺序入队处理当前节点后把它的左右子树节点依次入队从而实现了一层一层往下走的效果。#include iostream #include queue struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void levelOrder(TreeNode* root) { if (!root) return; std::queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }这里有几个小细节容易忽略入队的是指针不是节点本身。如果直接存节点对象每次push都会发生一次拷贝二叉树较大时性能损耗不小每次循环先q.front()取出队头节点再q.pop()弹出它两步缺一不可判断左右子树是否为nullptr后再入队避免空指针在后续处理中成为隐患。如果你还想知道“每一层各有哪些节点”可以借用queue.size()在循环开始时锁定当前层的节点数while (!q.empty()) { int layerSize q.size(); for (int i 0; i layerSize; i) { TreeNode* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } std::cout \n; // 一层结束 }layerSize必须在进入内层循环前取好因为循环里q.size()会随着入队操作不断变化。如果写成for (int i 0; i q.size(); i)每轮i加1的同时q.size()也可能在变循环次数就不可控了。这个bug在初学队列层序遍历时极其常见。3.3 手写一个简易stack看清适配器内部结构为了真正理解“适配器”的含义我建议你自己动手写一个迷你stack。底层就用vector把接口限制成只能从尾部操作template typename T, typename Container std::dequeT class MyStack { public: void push(const T value) { c.push_back(value); } void pop() { c.pop_back(); } T top() { return c.back(); } const T top() const { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } private: Container c; };这段代码只有十几行但已经复现了标准库stack的核心逻辑。它完全不负责元素存储存储工作全部交给底层Container。你换一个底层容器比如std::listT只要list支持push_back、pop_back、back、empty、size这些操作MyStack依然能正常工作。我自己写完这个模拟实现之后才真正理解为什么stack没有迭代器。因为适配器的设计意图就是“限制接口保持语义”。如果传给使用者一个迭代器他就可能在栈中间插入元素这就破坏栈的LIFO规则了。限制接口不是缺陷而是故意为之的边界。4. 常见问题与避坑心得这些坑我反复踩过4.1 空容器操作未定义行为的代名词空栈调用top()空队列调用front()或back()程序的行为是未定义的。所谓未定义就是“编译器想怎么处理就怎么处理”。可能崩溃可能返回垃圾值也可能碰巧正常工作但下一次运行却突然崩溃。我在一次模块联调时遇到过一个间歇性崩溃某段代码先从queue里取一个任务如果队列非空再处理但另一个线程同时也在向队列里塞任务导致判断和取值之间出现窗口期front()就访问到了空队列。排查了很久才发现问题不在并发锁上而在于对空队列操作的容忍度太低了。从那以后我给自己定了一条规矩所有top()、front()、back()调用前面要么显式判断empty()要么保证业务逻辑上有明确的不为空前提。4.2 pop不返回值的功能原因“取出并访问”必须写成两步前面提过pop()不返回值是为了异常安全。这里再展开一点假设接口设计成T pop()那么函数内部必须先把栈顶元素拷贝或移动出去再删除栈顶。如果第二步抛出异常那个已经被移动走的值就可能丢失。而且对移动操作本身如果移动构造抛异常容器内部的状态也不可预测。分拆成top()和pop()之后程序员可以自己决定访问和删除的顺序从而把控异常安全边界。这个设计也影响了日常代码风格。很多人习惯写int x q.front(); q.pop();看上去多了一行实际上这行“多余”的代码给了你最后检查值的机会。如果队列里放的是复杂对象你甚至可以先从front()拿到引用做一次合法性校验再决定是否弹出。这种灵活性是合并接口给不了的。4.3 遍历一次就空了queue和stack都无法“不改动地查看”由于stack和queue都没有迭代器你想查看内部元素只能通过反复top()/front()再pop()的方式破坏性遍历。这就带来两个问题栈或队列里原有数据被清空如果需要保留数据就必须用另一个容器接收弹出的元素遍历完后再写回去。这在使用std::queue做消息暂存时特别容易踩坑。比如某个异步处理模块先从网络收了一批消息放进queue处理到一半发现格式不对想“回看”前面几条消息结果因为遍历时已经弹出数据再也回不来了。解决方案通常有两个方向一是改用vector等可迭代容器配合头尾下标模拟队列二是给queue加一层封装比如定义一个小结构体内部同时维护queue和一份备份。但在设计阶段想清楚数据结构比事后补救更重要。4.4 性能对比与容器选型误区stack和queue本身的操作都是O(1)但“O(1)”背后也有常数差异。默认的deque底座在两端操作时通常很快但如果你的元素类型特别大频繁的拷贝仍然会成为瓶颈。我建议在以下场景考虑替换底层容器元素体积小且需要高缓存命中率的场景可以用std::stackT, std::vectorTvector连续内存访问更友好元素生命周期长、需要频繁两端插入弹出的场景默认deque已经非常合适元素数量动态变化剧烈、且需要稳定的尾部删除list可以作为备选方案但大多数情况下deque的分配策略更经济。另外要注意size()返回类型是size_t是unsigned类型。如果你拿它和负数比较或者直接做减法很容易因为隐式类型转换得到超大数值。比如if (q.size() - 1 0) // 当q.size()为0时变成size_t最大值的减法结果判断为真这类bug不会导致崩溃但会让人摸不着头脑而且很隐蔽。我建议所有涉及size的判断都显式转成int或先判断!empty()。5. 延伸思考从stack和queue看懂STL的适配器设计5.1 接口隔离与语义保护的价值看懂了stack和queue也就看懂了一种常见的设计思想不扩展接口而是限制接口。很多人写代码时总想给类添加越来越多的功能却忽略了过宽的接口会让误操作概率上升。stack如果给你迭代器你就可能写出“遍历栈内所有元素”的代码。这本身没有语法错误但在语义上站不住脚栈被设计出来就是为了防止你随意访问非栈顶元素。同样的道理queue不给你迭代器是为了防止你在队中间插入数据。接口变窄反而让容器的语义更明确、更安全。在软件工程中这种思想体现在很多地方。比如数据库的视图就是“限制接口”不让用户看到或修改底层表的全部字段操作系统的文件系统权限也是一种“接口过滤”。学习STL容器适配器不只是学API更是在学抽象思维。5.2 底层可替换带来的灵活性适配器最实际的好处是“换底座不影响使用”。你在业务代码里用的是stack.push、stack.pop底层是deque还是vector调用方并不感知。这种面向接口的编程方式让重构成本大幅降低。如果过了一段时间测试发现stack所在的模块出现了内存性能瓶颈你可以只改一行模板参数std::stackTask, std::vectorTask taskStack;其他代码完全不用动。只要Task满足相应的内存和拷贝要求替换即可完成。这就是封装和解耦的实践价值。5.3 扩展视野priority_queue和deque的特殊地位学完stack和queue之后可以自然往前再走一步看看std::priority_queue。它同样是一个容器适配器默认底层容器是vector堆顶元素“优先”被取出。它的接口里没有top()之外的元素访问接口没有迭代器但它的语义是“每次取出最大或最小元素”。理解了适配器的设计套路你再看priority_queue就不会觉得陌生它只是把“受限操作”换成了“堆操作”而已。另外别忘了deque本身也是个非常有意思的容器。它既能做stack的底座又能做queue的底座还能在两端快速增删。很多程序员学了stack和queue却忽略了deque这个真正的“幕后功臣”。如果想知道stack为什么默认用deque最好的方式是亲自写一个deque的简单模拟感受一下多缓冲区结构带来的分配策略差异。最后聊几句个人体会我刚开始学C时也纠结过“stack和queue这么简单为什么值得单独学”这个问题。后来刷题写项目被括号匹配、层序遍历、消息队列这些题目一遍遍“教育”之后才认识到简单接口背后的不简单一个能够限制操作的容器往往比一个功能大而全的容器更难被误用。你自己封装一个类时不妨也想想这个问题哪些操作不应该暴露给调用方哪些接口一旦放开就会让设计失去约束力想明白了这一点对stack和queue的理解才算真正深入了。