栈和队列是算法训练里最容易被轻视的两个数据结构。Day10这天我重新把它们梳理了一遍从基本实现到高频题再到工程里的阻塞队列和消息队列突然发现它们原来是同一套思维在不同尺度下的变体。这篇内容不是我讲课而是把我踩过的坑和梳理过的逻辑完整记录一遍希望能给正在刷题或者准备面试的朋友一点参考。1. 后进先出不是规则是一种天然的回溯方式1.1 数组实现栈栈顶指针为什么是灵魂我们一开始学栈总喜欢背“后进先出、先进后出”。背完就忘因为没理解为什么需要这个结构。直到我刷题时遇到递归回溯、括号匹配、表达式求值才意识到栈的本质是“记录历史然后有序地撤销历史”。它像一个只允许从顶端进出的弹夹压进去的子弹最后才发射出去。用数组实现栈非常简单一个一维数组加一个栈顶指针top就够了。初始化top -1push就是arr[top] xpop就是top--取栈顶就是arr[top]。这三个操作都是O(1)。但真正关键的是top指针永远指向“最后一个有效元素”它天然记录了我们操作的顺序。很多同学写栈的题容易错不是因为不了解操作而是写循环时搞错了top的边界。比如括号匹配里if (top -1) return false和if (top 0) return false是等价的但有人用top -1去匹配“空栈”却在pop后忘了top--导致越界。还有一个容易混淆的点算法里说的“栈”和内存里的“堆栈”。内存中的调用栈就是栈帧的集合而“堆”是动态分配内存的区域和数据结构里的堆优先队列完全是两回事。我在学习时也踩过这个坑面试被问“栈和堆的区别”结果我答成了数据结构里的栈和堆面试官一脸问号。实际上他问的是内存布局。所以建议把“数据结构栈”和“内存栈区”分清楚避免答非所问。1.2 栈帧形成过程与backtrace栈回溯说到内存栈区Day10我重新回顾了函数调用的过程。每次调用函数系统会在栈上压入一个“栈帧”stack frame里面保存了局部变量、参数、返回地址等信息。栈帧的形成有固定的步骤先压入返回地址再压入局部变量空间函数返回时栈帧被弹出。这就是为什么递归层级太深会导致栈溢出——栈帧一个个叠上去内存栈区的空间是有限的。C语言里局部变量越少所占栈空间越小这句话是对的。因为局部变量就存在当前函数的栈帧里每多一个变量栈帧就大一点。但要注意现代编译器可能优化不一定严格按照代码顺序留内存但总体趋势没错。工程里经常用“backtrace栈回溯”来排查问题。当程序崩溃时backtrace会打印出一串调用链看起来就像栈帧的“时间轴”。我一直觉得背不住递归不要紧只要你理解栈帧的压入和弹出递归其实就是同一种函数的栈帧反复堆叠而已。1.3 经典错题pop两次还是peek一次配合栈的操作有一道很经典的错题实现MinStack最小栈要求O(1)取最小值。很多人上来就开一个辅助栈虽然也对但容易在处理同步弹出时出错。我见过最典型的错误是取最小值时peek了辅助栈顶但主栈pop之后忘了检查辅助栈也要pop。或者反过来在辅助栈里只存最小值但如果有重复元素pop时会把唯一的最小值也弹没。所以正确做法是辅助栈每次入栈时存入“当前全局最小值”主栈pop时辅助栈也必须pop这样就保持了同步。这个题不算难但特别适合检验对栈“历史记录”的理解。2. 用栈解题括号、表达式、单调栈2.1 括号匹配为什么用栈而不是计数器括号匹配是栈的入门题也是面试高频。题目很简单给一个只包含()[]{}的字符串判断括号是否合法。我看到有人用三个计数器分别统计三种括号的数量然后发现([)]这种交叉嵌套的情况过不了。计数器只能记录数量无法记录“顺序”而括号合法性恰恰依赖顺序。用栈来表达顺序再自然不过遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配就弹出不匹配就失败。我还试过另一种写法遇到右括号时栈顶必须是对应的左括号否则直接返回。循环结束后栈必须是空的。这个流程很清晰但有几个陷阱。比如{[]}这种入栈顺序是{ [遇到]弹出[遇到}弹出{完全没问题。但有人为了简化代码会在入栈时压入对应的右括号遇到右括号时直接pop比较是否相等。这种写法更直观我更推荐。2.2 逆波兰表达式求值操作数顺序是魔鬼逆波兰表达式后缀表达式是一道很好的栈应用题。题目给一个表达式如[2,1,,3,*]求值。规则是遇到数字就入栈遇到运算符就弹出两个数先弹出的是右操作数后弹出的是左操作数算完再入栈。这里最容易出错的就是操作数顺序。比如3-2先弹出2右再弹出3左然后3-2算出1如果写反了就会得到-1。为什么顺序重要因为减法和除法不是交换运算先入栈的数字实际上是左边的操作数但栈顶其实是右边的所以要先把栈顶弹出作为right再弹出作为left。我在LeetCode上提交了一次错误正是写成了a - b而不是b - a而且加法乘法不影响因为是交换的所以这类bug特别隐蔽。建议写一个辅助函数明确标注“先弹出的是b后弹出的是a运算时用a op b”。2.3 单调栈从“下一个更大元素”到“每日温度”讲完基础的栈必须提单调栈因为它是栈算法里的“天花板”之一。核心思想是维护一个栈内元素单调递增或递减的栈用来解决“左右两边第一个比当前元素大/小”的问题。经典题是“下一个更大元素”和“每日温度”。例如nums [73, 74, 75, 71, 69, 72, 76, 73]要求输出每个温度之后需要等几天才能等到更高的温度。暴力解法是双重循环O(n^2)数据多就会超时。单调栈的做法是遍历数组栈里存下标保证栈里的元素对应的温度是单调递减的。当前温度如果大于栈顶对应的温度说明栈顶遇到了“下一个更高温度”此时可以出栈并计算结果否则把当前下标入栈。整个过程每个元素最多入栈出栈一次总共O(n)。单调栈的精髓在于“延迟结算”。在暴力解法中我们聚焦“当前元素往右看”而单调栈让我们想一想“谁在做左边界”。先入栈的元素在等待一个更大的值一旦等到就可以从栈里弹出。这就像一个排队机制后来的人如果更强前面的人就可以走了。理解了这个单调栈就不难写。我自己的记忆口诀是找右边更大栈内递减找右边更小栈内递增。除了解题单调栈还能优化DP。比如“最大子矩阵”、“直方图最大矩形”本质都是找“左右第一个小于/大于自己的位置”用单调栈可以把O(n^2)降到O(n)。这也是算法训练里“一题多解”的乐趣。3. 用队列解题BFS、循环队列与滑动窗口3.1 队列的朴素实现与循环队列front和rear怎么转圈说完成本再说队列。队列的思想更简单先进先出。但实现上比栈多一个“环”的问题。用数组实现队列时如果直接push和popfront一直后移很快前面的空间就浪费了。解决办法是循环队列让数组逻辑上首尾相接rear在队尾入队front在队头出队当rear到达数组末尾时跳回开头。循环队列有两个注意点一是判空和判满的条件容易混淆。常见做法是浪费一个数组位置当(rear 1) % capacity front时队满front rear时队空。二是下标移动要用取模运算例如入队后rear (rear 1) % capacity。很多新手会写rear然后数组越界。我刷题时看到很多版本的循环队列其中一个高频题是设计MyCircularQueue要求实现enQueue、deQueue、Front、Rear、isEmpty、isFull。这种题其实就是在考边界条件。链式队列就好理解多了。入队就是在链表尾部插入出队就是删除链表头节点。时间复杂度都是O(1)但每个节点有额外的指针开销。一般刷题时用数组模拟更快但在C STL里直接用queue即可而Java中用LinkedList实现队列。链式队列的图解很容易搜到明白“队首出队尾入”即可。3.2 BFS层级遍历为什么必须用队列队列最经典的应用是广度优先搜索BFS。比如二叉树的层序遍历需要按层打印节点。为什么用队列因为BFS的访问顺序就是逐层扩散先访问到的节点要先被扩展这恰好是先进先出的逻辑。用栈替代行不行不行栈会改变遍历顺序变成深度优先。实现时有几个细节。一是要提前把根节点入队然后循环内先记录当前队列大小size因为在遍历当前层的节点时子节点会不断入队如果不先记录size就会把下一层的节点也当成当前层处理。二是size要在进入循环前取不能每次动态查。这是层序遍历最容易错的点。如果题目要求“之字形打印”或者“分层统计”只需要在size那一层里做特殊处理。我曾经在一次面试里被问“不用队列能否实现BFS”我说可以用vector存每一层的节点但其实那还是隐式队列。本质上只要你需要“保持待访问节点按时间顺序”就必须用队列或能模拟队列的数据结构。3.3 单调队列滑动窗口最大值的O(n)解法和栈有单调栈对应队列也有高级用法单调队列。最经典的是滑动窗口最大值题目给数组和窗口大小k要求输出每个窗口内的最大值。暴力法是每个窗口扫一遍O(nk)窗口大了就超时。单调队列的思路是维护一个双端队列deque队列里存下标且对应的值在窗口内单调递减。每次滑动窗口时先移除队头已经不在窗口内的下标下标小于i-k1的然后从队尾开始把所有小于等于当前值的元素弹出因为它们在当前以及未来窗口中都不可能成为最大值最后把当前下标入队。这样队头永远是当前窗口最大值的下标。每个元素入队出队各一次总复杂度O(n)。这个算法很考验“虽然当前元素小但可能未来被留下”的思考。举个例子[1, 3, -1]窗口k3。当处理-1时虽然它比3小但窗口还没满它还有机会成为最大其实在窗口内它永远比不过3所以可以弹但是单调队列的做法是保留它因为当3被滑出窗口后它可能成为最大值。所以弹出条件应当是“队尾元素小于等于当前元素”而不是小于。如果写成小于等于会丢掉相等值的顺序。这里“等于”的问题也是常见坑我踩过。单调队列还能优化DP比如解决“跳石头问题”或“多重背包优化”。理解了单调队列本质是“维护一个动态集合的最值”就抓住了要害。4. 队列思想出圈线程池阻塞队列与消息队列避坑4.1 线程池为什么选阻塞队列以及怎么选当队列思想进入并发编程就变成了阻塞队列。线程池的核心就是一堆线程从一个共享队列里取任务执行。这个队列不简单因为当队列满时提交任务的线程必须被阻塞等待有空位当队列空时工作线程要阻塞等待新任务。所以Java里提供了一组BlockingQueue实现。怎么选ArrayBlockingQueue底层是数组有界适合控制并发数LinkedBlockingQueue底层是链表默认无界但如果初始化指定容量可以变为有界SynchronousQueue不存储元素每个插入必须等待另一个线程取走直接传递任务PriorityBlockingQueue支持优先级。我在做线程池配置时踩过坑刚开始用无界队列LinkedBlockingQueue当任务大量涌入时线程数到达最大值后新任务不会继续创建线程而是全堆在队列里结果内存被撑爆而且响应延迟越来越大。后来改成有界队列ArrayBlockingQueue配合CallerRunsPolicy拒绝策略才稳定下来。所以选型关键是看拒绝策略和队列容量。有界队列能限制积压但太快被填满又会导致大量任务被拒绝无界队列会导致任务无限排队失去“削峰填谷”的意义。建议根据实际提交速率和消费能力来设计队列长度并监控队列积压量。4.2 Kafka、RabbitMQ、RocketMQ选型实战对比以及我踩过的坑再往分布式走一步消息队列其实就是“分布式系统里的队列”。我在项目选型时对比过Kafka、RabbitMQ和RocketMQ。这里简单分享一下我的看法仅供参考。Kafka吞吐量最高适合大数据流、日志采集。它是基于追加日志的存储模型消费后不删除消息靠offset维护进度。我一次线上排查发现Kafka重复消费很常见因为消费者处理完消息后还没提交offset就挂了恢复后会重新消费旧数据。RabbitMQ是消息中间件里的“老好人”胜在路由灵活支持多种交换机类型适合复杂路由和低延迟场景。但它默认不适合堆积海量消息如果积压太多性能下降明显。RocketMQ是阿里开源介于两者之间吞吐量比RabbitMQ高事务消息、定时消息等支持较好适合电商等业务场景。我们当时选RocketMQ主要是因为事务消息做得比较完善。选择上没有绝对的好坏关键看你的业务场景。如果追求极致的吞吐和顺序性选Kafka如果要求灵活路由和快速响应选RabbitMQ如果既要吞吐又要事务等高级特性RocketMQ是不错的选择。4.3 重复消费队列的at-least-once特性与幂等设计提到消息队列绕不开重复消费问题。几乎所有主流的消息队列都提供at-least-once投递保证消息不会丢失但可能重复。解决办法就是消费端做幂等。我常用的方案有几种唯一ID去重消息携带唯一业务ID消费端先查数据库有没有这个ID存在就跳过。数据库唯一索引插入时利用唯一索引重复插入会报错catch住即可。状态机依赖业务状态只有“待支付”才能变为“已支付”重复消息进来后状态不匹配直接被忽略。这些思路本质上都是“让重复消息的处理结果与第一次一样”。我在一个订单项目里用唯一索引去重实测可以挡住绝大多数重复消息但要注意数据库性能瓶颈必要时加分布式锁。从数据结构的角度看消息队列的重复消费问题是什么它源于队列的“至少一次”投递语义而不是“队列只能被读一次”。我们在算法题里操作队列时默认出队就是删除但在分布式环境里出队和确认是分离的这才是重复的根源。明白这个差异再去设计幂等就会很有方向感。