刷完了代码随想录day11栈与队列part2整个人松快了不少。说实话栈和队列这两兄弟刚开始学的时候都以为就是“先进后出、先进先出”两个口诀背完就以为会了。可真正开始用栈实现队列、用队列实现栈的时候才发现自己离“理解”还差着十万八千里。day11当天的题量不大核心就三题有效的括号、删除字符串中的所有相邻重复项、逆波兰表达式求值全是栈和队列在字符串处理和表达式计算里的经典应用。如果你正在追代码随想录或者单纯想把数据结构的地基打牢固这篇可以当伴读笔记看我会把每道题的思路、代码、踩坑点全部摊开再顺着栈帧、backtrace、阻塞队列、消息队列这些工程里的“亲戚”一并聊透。1. 先把栈和队列的“底”摸清楚栈帧、回溯与排队模型1.1 函数调用是怎么用栈的栈帧与backtrace的秘密在程序设计的世界里栈最经典的骨架就是函数调用栈。你在IDE里打断点、打开Call Stack窗口或者用gdb敲一个btbacktrace命令看到的每一层调用记录本质上都是栈帧的串联。所谓栈帧stack frame就是一次函数调用的完整上下文参数、返回地址、局部变量、保存的寄存器状态统统被系统压在栈内存里。当函数A调用函数B的时候程序会先把B需要的参数按调用约定压栈再把当前指令的返回地址压栈然后跳转到B的入口继续执行。B运行的时候再把自己的局部变量压进去形成一个新的栈帧。这个“压栈—执行—弹栈”的动作完完整整对应数据结构教科书里栈的push和pop。函数B一旦return系统就把当初保存的返回地址读出来跳回A接着干活同时把B的栈帧整体弹掉。backtrace栈回溯的原理就是基于此栈帧里存着返回到哪去的信息调试器沿着这些返回地址一路往上找整条调用链就全都捞出来了。理解了这一层再看“递归为什么会爆栈”就特别清晰每递归一层系统都要新建一个栈帧。栈空间是有限的Linux主线程默认8MB可以用ulimit -s查看递归深度一大栈帧一层层叠上去直接把栈底撑穿程序就抛stack overflow。所以工程里常用循环加显式栈来替代深递归本质是把系统栈的活揽到自己手里可控性反而更高。顺带提一句“局部变量越少所占栈空间越小”这个说法基本成立。栈帧的大小主要由局部变量、参数和返回地址撑起来尤其是嵌入式环境里例如用pico-sdk做开发时主栈默认很小函数里少放几个大数组、把大对象挪到堆上都是非常实在的优化手段。1.2 队列的“排队”模型和阻塞队列队列就更好理解了——排队。你在食堂打饭、在银行叫号都是队尾入、队头出先来先服务。计算机里的队列就是给数据排队入队enqueue把元素放到队尾出队dequeue从队头取走。用数组实现队列有一个初学者经常翻车的细节如果单纯用数组尾部追加、头部弹出每次弹出都要把后面所有元素往前搬复杂度瞬间变为O(n)。所以实际实现里普遍用循环队列——头尾指针在数组里转圈队尾满了就回绕到开头继续用。判空判满也是经典考点初始时head tail表示空而“满了”的判断有几种实现方式最常见的是牺牲一个格子用(tail 1) % size head表示队满也有人额外用一个size变量做计数。队列在实际工程里最典型的形态就是阻塞队列放不进去就等着取不到也等着。这不就是生产者-消费者模型吗生产者往队列里塞任务消费者从队列里取任务队列天然承担了异步缓冲和削峰的作用。秒杀场景、异步订单处理、线程池的任务队列底下全是阻塞队列在兜底。所以这一节可以先建立一个直觉栈是“操作的现场记录”队列是“任务的排队缓冲”。带着这两个直觉去刷后面的题会顺很多。1.3 “栈”在不同工程语境下的含义多说一句栈这个名词在工程里不止一种用法。除了数据结构里的栈还有网络协议栈TCP/IP协议栈、安卓的网络请求栈比如OkHttp、Retrofit处理HTTP请求的那套管线甚至iOS Safari里用uniapp的canvas时如果导出白图本质也是绘制操作和异步队列之间没协调好。凡是“先进后出”或“先进先出”的任务组织方式都可以拿栈和队列的思维去理解。这也是为什么算法题刷到后面你会发现栈和队列无处不在。2. part2核心三题逐题复盘2.1 part1先复盘栈和队列互相模拟的底层逻辑进入当天题目之前先把part1的两道题快速过一遍因为后面会反复用到它们的思维。232 用栈实现队列的核心是“两次后进先出等于先进先出”。维护一个输入栈in和一个输出栈outpush直接进inpop的时候先检查out是不是空的空就把in里所有元素全部倒进out再取out的栈顶。为什么可以倒因为倒一次之后压在栈底的元素到了栈顶顺序正好被纠正过来。最关键的是均摊复杂度一个元素最多进栈两次、出栈两次均摊O(1)实际跑起来非常快。225 用队列实现栈更好玩。队列的先进先出不会自然翻转顺序所以pop时需要把前size-1个元素重新塞到队尾让队首变成最后一个进来的元素充当栈顶。优化之后甚至只需要一个队列每次pop把除了最后一个以外的所有元素重新入队队首就是要弹出的元素。top操作同理只是把队首取出来后再放回队尾保持队列原状。这两道题本质上是考你“两种数据结构能否互相模拟”面试出现频率很高建议多手写几遍直到闭着眼能写出为止。2.2 20. 有效的括号最经典的栈匹配应用题目给定一个只包含()[]{}的字符串判断括号是否有效。为什么这道题必须想到栈因为括号匹配天然是“最近优先”的最内层的左括号一定匹配它后面的第一个右括号。你手动判断的时候也是从中间往两边消这就是后进先出。代码可以写得很简洁bool isValid(string s) { stackchar st; for (char c : s) { if (c () st.push()); else if (c [) st.push(]); else if (c {) st.push(}); else { if (st.empty() || st.top() ! c) return false; st.pop(); } } return st.empty(); }这版代码是代码随想录里很常用的写法遇到左括号把对应的右括号压栈遇到右括号就看栈顶是不是自己。这种“反向压栈”的好处是不用额外记左右怎么对应代码分支最少。但是有三种不匹配的情况必须想全。一是右括号多了遍历过程中栈已经为空直接false二是左右括号类型对不上栈顶不等于当前字符三是左括号多了遍历完了栈还不为空。我见过不少提交挂掉就挂在第三种——循环结束直接return true忘了检查st.empty()。多写一行判断稳得很。2.3 1047. 删除字符串中的所有相邻重复项把字符串当栈用题目给出一个小写字母字符串反复删除两个相邻且相同的字母直到没有相邻重复项返回最终字符串。这题直观解法就是“遍历加消消乐”。新来的字符如果和“已保留字符串”的最后一个相同就把那个字符废掉否则保留当前的字符。仔细一看“已保留字符串的最后一个”这不就是标准的栈顶访问吗于是可以直接拿一个字符串模拟栈string removeDuplicates(string s) { string st; for (char c : s) { if (!st.empty() st.back() c) st.pop_back(); else st.push_back(c); } return st; }为什么一定要用栈因为消除相邻重复项是一个动态过程消掉一对之后新露出来的相邻关系只可能发生在栈顶和下一个待处理字符之间之前的字符不会“复燃”参与新的匹配。所以用一个栈维护“还没被消掉的字符序列”每一步只需要比较栈顶和当前字符就够了。这里有个小技巧值得记如果题目要求输出处理后的字符串用string当栈比用std::stack舒服得多。省掉最后把栈元素倒出来再反转的一次遍历时间和空间都更省。这个思路在很多字符串处理题里都能复用比如一些“保留最后一个出现字符”的变体。2.4 150. 逆波兰表达式求值计算机天生爱后缀表达式题目给你一个逆波兰表达式后缀表达式求它的值例如[2,1,,3,*] 9。逆波兰表达式就是运算符写在两个操作数之后的表达式中缀“2 1”写成后缀“2 1 ”。人类看中缀顺眼但计算机处理中缀要考虑优先级、括号麻烦得很后缀表达式只需要一个栈从左到右扫一遍遇到数字就压栈遇到运算符就弹出两个数做运算结果再压回去。等表达式全部扫描完栈顶就是最终答案。这就是为什么编译器的表达式求值阶段往往先把中缀表达式转成后缀再顺序计算。代码实现int evalRPN(vectorstring tokens) { stackint st; for (const string t : tokens) { if (t || t - || t * || t /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (t ) st.push(a b); else if (t -) st.push(a - b); else if (t *) st.push(a * b); else st.push(a / b); } else { st.push(stoi(t)); } } return st.top(); }这题有一个让人印象极其深刻的坑运算顺序。先弹出栈顶的是后一个操作数也就是表达式里靠右的那个数。做减法时先出栈的是b右操作数后出栈的是a左操作数正确结果是a - b除法同理是a / b。如果把顺序写成b - a测试用例里但凡出现减法必然翻车。这事我自己丢过分后来给自己定了个规矩碰到二元运算先默念“先弹右、后弹左”再动手写。第二个坑是负数。tokens里可能出现“-11”这种字符串如果单纯用t[0] -来判断当前字符是否是减号很容易把数字“-11”当成运算符。正确的做法是判断整个字符串是不是四则运算符用完整字符串比较而不是只看首字符。LeetCode这题保证表达式合法有效但工程里谁都不敢保证输入一定干净所以这个习惯还是要养成。3. 别急着收工单调队列和优先级队列同类题的长尾3.1 239. 滑动窗口最大值单调队列的淘汰逻辑day11当天没有安排这两道题它们一般在后面才出现但我强烈建议跟着一起刷。239 滑动窗口最大值题义给定一个数组和窗口大小k每次窗口右移一格输出当前窗口内的最大值。暴力做法很简单每滑一格就在窗口里扫一遍找最大值复杂度O(nk)数组一长直接超时。优化思路是我们不需要维护窗口里所有元素只需要维护“有机会成为窗口最大值的候选集”。这就是单调队列的核心思想。维护一个双端队列deque让队列从队首到队尾保持严格递减。新元素入队时先把队尾所有小于等于它的元素全部弹出再把新元素从队尾塞进去。为什么可以弹因为新元素既比它们大又在窗口里“活”得更久一个“更大且更新”的元素出现了旧元素永远没机会当窗口最大值。窗口滑动时还要检查一下队首元素的下标是不是刚好是移出窗口的那个如果是说明它过期了从队首弹出。代码骨架大致是这样dequeint dq; // 存下标方便判断是否过期 for (int i 0; i nums.size(); i) { while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); if (dq.front() i - k) dq.pop_front(); // 队首下标离开窗口 if (i k - 1) ans.push_back(nums[dq.front()]); // 收集答案 }提示队列里存下标而不是存值是这道题不超时的关键。如果只存值窗口滑动时你根本判断不了“队首元素是否已移出窗口”。存下标之后一个if就能解决过期问题。整体复杂度O(n)每个元素最多进队一次、出队一次比暴力快了一个数量级。3.2 单调队列优化DP识别套路更重要除了滑窗最值单调队列还能优化一类区间DP。典型形式长这样dp[i] max(dp[j]) cost其中j的取值范围落在[i-k, i-1]这个滑动窗口内。这类题如果对每个i都去扫一遍窗口复杂度O(nk)但如果维护一个针对dp数组的单调队列窗口内最大值在O(1)时间就能拿到总复杂度直接降到O(n)。识别特征也很简单转移方程里出现“前面连续k个位置的某种最值”基本就是单调队列优化的味道。做题的顺序建议是先写出朴素DP再看有没有滑窗最值窗口最后替换成单调队列。这条递进路径在LeetCode里很多“线性DP加滑窗限制”的题都能用学一次收益很高。3.3 347. 前K个高频元素优先级队列的正确姿势347 前K个高频元素给定一个整数数组返回出现频率最高的前K个元素。常规思路先统计每个元素的频次再按频次排序取前K个复杂度O(n log n)。但排序会把全部元素都排一遍我们只需要最大的K个完全可以用最小堆只维护K个元素priority_queuepairint,int, vectorpairint,int, greater pq; // 小顶堆 for (auto [num, freq] : mp) { pq.push({freq, num}); if (pq.size() k) pq.pop(); // 丢掉当前最小的 }这里为什么不用大顶堆因为要的是前K个最大频次的元素只有堆顶是当前K个里最小的时候遇到新的更高频元素才能弹掉旧的、换上新的。如果建大顶堆堆顶永远是最大的根本不知道该淘汰谁。优先级队列堆的“优先级”由比较器决定这道题正好把概念顺带理清了。4. 从算法题到工程现场工程里的栈与队列远比题目复杂4.1 线程池的阻塞队列怎么选回到第1部分提过的阻塞队列。在Java的线程池里任务队列本质上就是生产者-消费者之间的缓冲。选择不同的阻塞队列直接决定了线程池的行为ArrayBlockingQueue有界数组阻塞队列容量固定满了就让提交线程阻塞或走拒绝策略适合需要控制任务积压量的场景LinkedBlockingQueue有界或无界链表阻塞队列默认无界时可能导致任务无限积压内存被拖垮这个坑在大型系统里真实发生过SynchronousQueue不存任务的队列每一个put必须等到一个take线程池一有任务马上创建线程执行适合对延迟敏感的短任务PriorityBlockingQueue按优先级出队的阻塞队列适合需要任务分级处理的场景。选型本质上是“缓冲能力、内存风险、业务需求”三者的权衡。无界队列看起来很省心其实是把风险藏到了内存里有界队列配合饱和策略抛异常、丢弃、调用者自己跑才是生产环境的常规操作。4.2 消息队列选型实战对比kafka、rabbitmq、rocketmq把阻塞队列再放大一个层级就到了跨服务的消息队列。很多团队一开始选型很随意后面踩坑才回头补课。这里把三个主流MQ的差异摊开看维度KafkaRabbitMQRocketMQ核心定位分布式流处理平台通用消息中间件AMQP金融级消息中间件吞吐量百万级/秒极高万级/秒十万级/秒消息延迟毫秒级微秒到毫秒级毫秒级可靠性副本机制可配置acks镜像队列防止节点故障支持同步刷盘和事务消息路由能力弱基于分区强topicexchange绑定中等支持tag过滤顺序消息分区内有序单一队列有序分区队列有序事务消息官方不支持部分场景可模拟原生支持大数据生态和Flink/Spark无缝集成一般部分支持选型建议基本就是“三看”看吞吐大数据采集、日志管道、流计算场景Kafka最稳看路由复杂度业务消息需要灵活的绑定关系RabbitMQ的AMQP模型天然合适看交易级别可靠性事务消息、顺序消息、金融风控这类场景RocketMQ的Java生态最省心。如果你所在团队已经深度绑定某个框架选型还要考虑运维成本和团队熟悉度技术指标只是其中一环。4.3 重复消费问题幂等是唯一的出路聊消息队列绕不开的痛点就是重复消费。分布式系统为了不丢消息普遍采用“至少一次”投递语义生产者重试投递、消费者消费成功但还没来得及提交offset就宕机消息都会被再次投递。换句话说重复消费不是“会不会发生”的问题而是“什么时候发生”的问题。想在重复消息下不让系统产生脏数据核心是幂等设计。常见做法靠消息唯一ID去重消费端把已处理的ID存到Redis或数据库消费前先检查再写入注意“检查后写”最好是原子操作否则仍有竞态靠业务唯一键兜底比如订单表里订单号建唯一索引重复插入被数据库直接拒绝靠状态机处理结果里带上订单状态只有前置状态匹配才继续流转天然幂等。我在项目里的体会是前两种方案最常用第三种适合有明确状态流转的业务。消息队列本身不背幂等的锅真正决定正确性的永远是消费者的业务逻辑。5. 常见问题与避坑实录5.1 栈相关爆栈、越界与大数组存放日常开发里栈的高频问题集中在爆栈。Linux默认主线程栈8MB递归不设节制、函数里声明超大局部数组都是常见的翻车原因。某个递归函数每层吃几KB栈帧来个几万层递归8MB说没就没。排查时先看backtrace能不能正常打出如果连bt都输出不全大概率是栈被写穿或者栈帧指针损坏。常见处置方案把深递归改成循环加显式栈把大数组改为new或vector放到堆上嵌入式环境里如果用的是pico-sdk这类开发可以自己调大任务栈或主栈大小前提是确认整体内存够用。另外模拟栈的写法有个小细节用数组模拟时top到底指向“栈顶元素”还是“下一个空位”很多人会搞混。C的STL中stack基于deque实现不需要自己管理内存但手写题里把top初始化为-1还是0直接影响后面的压栈代码是st.top还是st[top]x。建议专门写一页笔记固定住自己习惯的那套写法。5.2 队列实现环形缓冲、判空判满和底层容器循环队列是面试爱考的实现题核心是判空判满队空head tail队满牺牲一个存储单元让(tail 1) % size head成立时视为满出队入队head (head 1) % sizetail (tail 1) % size。注意这里的“满”不等于数组最后一个格子被占了而是“再放一个就会和head撞上”。实际使用STL的queue时不需要关心这些但知道它底层是deque双端队列而不是连续数组能帮你理解为什么queue的push和pop复杂度都是O(1)均摊——它内部是由分段的连续块拼接而成扩容时不会像vector那样整体搬移。5.3 刷题高频错误速查表把这几天常见的错误整理成一张速查表刷到相关题目时可以先对一遍题目高频错误正确姿势20. 有效括号遍历完直接return true漏掉栈非空检查结尾用return st.empty()1047. 删除相邻重复项用stack存字符最后忘了反转直接用string当栈或最后reverse150. 逆波兰表达式减法除法操作数顺序写反先弹右操作数b再弹左操作数a150. 逆波兰表达式把“-11”这类负数当运算符用完整字符串判断运算符232. 用栈实现队列peek忘记transferpop后状态不同步peek复用transfer逻辑225. 用队列实现栈top弹出元素后没还原队列取到栈顶后重新放回队尾239. 滑动窗口最大值队列存值不存下标无法判断过期存下标用front() i-k判断这些错误大多不是“不会”而是“写太快”。我的习惯是每道题提交前用几个刁钻例子在脑内跑一遍。括号题试一下“([)]”和“(((”RPN题试一下“3 -4 ”滑动窗口试一下窗口大小等于数组长度。先把边界情况跑顺了再提交正确率会明显高很多。我个人在实际刷题中的体会是栈和队列难的不是定义而是建立“什么时候该用它们”的直觉。括号匹配天然是栈的活因为匹配规则是最近优先相邻重复项消除是栈的活因为你只关心“上一个还剩下的字符”表达式求值是栈的活因为后缀表达式用栈扫一遍就能完成。而队列那边削峰、排队、异步解耦从阻塞队列到消息队列全是“先进先出”这一条规则在不同规模下的演绎。后来我在线上排查问题打开backtrace看到一层层调用帧时脑子里浮现的就是栈帧在栈上一个一个叠起来的样子那种感觉特别奇妙——原来刷题时建立的心智模型真的会在工程现场冒出来。希望你也能一边刷题一边往真实场景里联想这样记下的东西才不容易忘。