栈和队列这两兄弟在很多人眼里只是课本上的一个概念一个是后进先出一个是先进先出背完定义就完事了。但真到了刷题的时候你会发现它们的作用远不止于此。就拿《代码随想录》Day 11 这三道题来说——150. 逆波兰表达式求值、239. 滑动窗口最大值、347. 前 K 个高频元素——一道把“栈”用在表达式求值上一道用“单调队列”解决滑动窗口的极值问题一道用“堆”来维护 TopK。三题做完你对“栈和队列的变种”基本就有感觉了。这篇文章我会按刷题笔记的方式把每道题的思路、代码、边界坑都讲一遍也会说说为什么这个解法能过、那个解法会超时。适合正在准备面试、或者刚学到栈与队列想加深理解的同学。如果你已经能独立 AC 这三道题可以跳到最后的“坑位复盘”部分有些细节估计你也中过招。1. 三道题放在一起到底在考什么1.1 从“后进先出”到“队列的变种”栈和队列在教科书里的定义都很简单栈是后进先出队列是先进先出。但真实工程和算法题里我们几乎不会只用“最朴素”的栈和队列。函数调用栈回收、浏览器前进后退、编译器表达式求值、线程池的阻塞队列、业务系统里的消息队列……这些场景都在用栈和队列的变种。Day 11 这三道题特别典型的地方在于它们没有一道是直接让你“用栈模拟括号匹配”或者“用队列模拟排队”而是把数据结构嵌到了具体的计算场景里。逆波兰表达式要求你在无括号的情况下完成表达式求值本质是“后进先出”在计算顺序上的体现滑动窗口最大值要求你在窗口不断移动时快速取极值本质是“先进先出”加“单调性约束”前 K 个高频元素则更进一步队列不再按先进先出排队而是按“优先级”排队这就是堆优先队列的雏形。所以我的建议是把这三道题当作一条学习链路先用最原始的栈解决计算问题再把队列升级成“双端”和“单调”最后把队列升级成“按权值排序的优先级队列”。一条链学下来你对数据结构“为什么需要这些变形”会有非常直观的理解。1.2 每道题对应的知识点定位先给一个全局对照表方便你回顾时快速找到重点。题目核心数据结构主要考点时间复杂度150. 逆波兰表达式求值栈后缀表达式、运算符优先级处理、除法取整O(n)239. 滑动窗口最大值双端队列单调队列、窗口滑动时元素的过期淘汰O(n)347. 前 K 个高频元素哈希表 堆频率统计、小顶堆维护 TopK、堆的调整O(n log k)三道题对应三种抽象层级栈是“后进先出”的直接应用双端队列允许同时操作头和尾开阔了设计空间堆则是对“队列”的一种彻底重构——谁优先级高谁先出。真正吃透它们比死记“栈适合做括号匹配、队列适合做 BFS”这种模板要更有收获。2. 150 题逆波兰表达式求值2.1 后缀表达式为什么这么“方便”逆波兰表达式也叫后缀表达式核心特点是运算符放在两个操作数后面比如2, 1, , 3, *对应我们平时写的中缀表达式(2 1) * 3。人类习惯中缀是因为有运算符优先级和括号但计算机处理中缀非常痛苦需要反复扫描、比较优先级。而后缀表达式只有一个规则从左往右扫遇到数字就压栈遇到运算符就把栈顶两个数字弹出做运算结果再压回去。全程不需要判断优先级也不需要括号。这就像你手工算(2 1) * 3时正常人不会先去算2 1再去乘 3 吗其实只是人脑天然带优先级判断。编译器为了统一处理会把中缀转成后缀然后交给一个简单的栈机器去执行。很多面试官也会追着问“中缀怎么转后缀”其实就是扫一遍表达式用栈临时保存运算符等括号或优先级触发时再弹出。2.2 求值流程与代码实现这道题的输入tokens是一个字符串数组里面既有数字也有 - * /四种运算符。用一个栈就能完成全部操作流程很简单遇到字符串形式的数字转成Number后压栈。遇到运算符弹出栈顶两个元素a是后弹出的那个b是先弹出的那个。计算a 运算符 b把结果压回栈。全部处理完后栈里唯一的元素就是答案。JS 实现如下function evalRPN(tokens) { const stack []; const ops new Set([, -, *, /]); for (const token of tokens) { if (!ops.has(token)) { stack.push(Number(token)); continue; } const b stack.pop(); const a stack.pop(); let result; switch (token) { case : result a b; break; case -: result a - b; break; case *: result a * b; break; case /: result Math.trunc(a / b); break; } stack.push(result); } return stack.pop(); }这里最容易被忽略的就是减法和除法中a和b的顺序。因为栈是后进先出2 1 -的意思是2 - 1不是1 - 2。第一次写这道题十有八九会把a b写成b a加法和乘法无伤大雅但减法和除法会直接导致答案错误。2.3 除法取整和边界处理这个题在 C 或 Java 里整型除法本来就是向零取整直接a / b就行。但在 JavaScript 里a / b得到的是浮点数比如-3 / 2是-1.5。题目要求结果向零截断也就是-1所以必须用Math.trunc(a / b)。还有一个隐藏坑parseInt看起来也能实现“截断”但它对负数的处理方式并不理想。比如parseInt(-1.5)会先被转成字符串-1.5再解析出整数-1结果恰好一样但parseInt(0.0000001)这类场景会有意外Math.trunc才是真正的“向零取整”语义更干净。所以刷题时我建议统一用Math.trunc。时间复杂度是 O(n)因为每个 token 最多进出栈一次。空间复杂度也是 O(n)极端情况下表达式全是数字。题目约束说表达式一定是合法的所以不用判空但如果你要扩展成“计算器”功能合法性和除零检查都不能少。顺便说一句这个题做对了后面做“基本计算器”系列会轻松不少因为核心的“栈机器”你已经搭过一遍了。3. 239 题滑动窗口最大值3.1 暴力解法的问题在哪里这道题描述很直白给一个数组nums和一个窗口大小k窗口每次往右移一格返回每个窗口里的最大值。最朴素的想法是两层循环外层遍历所有窗口内层扫一遍当前k个元素找最大值时间复杂度是 O(nk)。数据量小没事但 LeetCode 的测试数据直接把长度拉到10^5左右O(nk) 直接超时。有人可能说那我用一个大顶堆不就行了窗口移动时往堆里塞新元素、弹出旧元素堆顶就是最大值。思路对了一部分但问题在于堆本身不支持“按值删除任意元素”——你得知道旧元素的下标并且在堆里精确删除这会让堆的调整逻辑变得非常复杂时间复杂度也会退化。所以这道题的标准解法不是“优先队列”而是一个很巧妙的数据结构单调队列。单调队列本质上仍然是双端队列但它在入队时做了一件关键的事情把没资格当队头的元素提前弹掉。这样队列里的元素从队头到队尾保持“单调递减”或“单调不减”队头永远是当前窗口的最大值。3.2 单调队列的两个动作去尾和去头我刷这道题的时候最直观的感觉就是“窗口里留着那些较小的数字没有意义”。举例窗口[3, 1, 2]最大值是 3那 1 和 2 暂时有没用当窗口往后移3 离开窗口后2 有可能成为新窗口最大值但 1 除非前面所有元素都走了否则永远不可能排在 2 前面成为更大值。也就是说只要后面存在更大的数前面较小的数就可以被淘汰。这就是“去尾”动作每次新元素进队前从队尾开始弹出所有比它小的元素。这样维护出来的队列从队头到队尾一定是递减的队头就是当前窗口最大值。然后是“去头”动作窗口滑动时要判断队头元素是否已经滑出窗口。如果滑出了就从队头弹出。这两个动作一前一后配合得天衣无缝。生活类比就是一个班级的队列如果有新同学个子更高那么排在他前面的所有“矮个子”都不用再管了但如果队列最前面的同学已经毕业离校就要把队头清掉。代码里最核心的思路就是把“比新元素小的旧元素”在入队时提前干掉避免窗口滑动后还要重重比较。3.3 代码实现与复杂度分析我统一用“存下标”的方式实现因为存下标才能准确判断元素是否过期。如果只存值窗口滑到一半你根本不知道这个值还在不在窗口里这是很多初学者最容易掉进去的坑。function maxSlidingWindow(nums, k) { const queue []; // 双端队列存放元素下标对应的值从大到小 const result []; for (let i 0; i nums.length; i) { // 去头队头已经滑出窗口 while (queue.length queue[0] i - k) { queue.shift(); } // 去尾所有比当前元素小的元素都没有存在价值 while (queue.length nums[queue[queue.length - 1]] nums[i]) { queue.pop(); } // 当前元素入队 queue.push(i); // 窗口形成后每次移动都记录队头对应的值 if (i k - 1) { result.push(nums[queue[0]]); } } return result; }注意去尾的判断条件是还是。如果数组里有重复值比如[5, 5, 3]用会把旧的 5 留在队尾但旧 5 的贡献其实已经被新 5 覆盖区别不大用会让新元素把旧元素弹掉代码更简洁也不影响正确性。实际面试时我习惯写因为在解释“相等时为什么保留旧元素”时理由更充分——旧元素会在更早的时间过期如果它的值和新元素相同保留它会更快被淘汰不会影响正确性。每个元素最多入队一次、出队一次所以整体复杂度是 O(n)空间复杂度 O(k)。这个“去尾”操作可能会让你觉得内层 while 是 O(n) 的但仔细想想每个元素只会被 pop 一次均摊下来就是 O(1)。这也是单调队列最经典的地方用均摊代价换来了每个窗口最大值 O(1) 的查询。4. 347 题前 K 个高频元素4.1 先统计频率再考虑怎么选出前 K这道题的要求是返回数组中出现频率最高的 K 个元素。第一步没有悬念先扫一遍数组用哈希表统计每个数的频率复杂度 O(n)。难点在第二步怎么从一堆频率里找出最大的 K 个。最简单的办法是把所有(元素, 频率)按频率排序然后取前 K 个时间复杂度 O(n log n)。这在数据量小的时候没问题但 LeetCode 测试数据一大O(n log n) 就有风险而且面试官大概率会追问一句“能不能更快”。标准答案是维护一个大小为 K 的小顶堆堆里只放“当前频率最高的 K 个元素”。每来一个新元素如果它比堆顶元素当前第 K 大频率还高就把堆顶弹掉把它塞进去。这样遍历完所有频率后堆里留下的就是前 K 个高频元素。这里有一个特别反直觉的选择为什么不用大顶堆大顶堆每次弹出的都是最大值那最后堆里留下的反而是“频率最低的那批”方向完全反了。小顶堆的堆顶是整个堆里最小的高频元素但它恰好是“进入 TopK 的门槛”——新元素只有跨过这个门槛才有资格入堆。这就是“筛选”和“排序”的区别大顶堆适合求最小值小顶堆适合求最大值。4.2 手写一个小顶堆而不是调现成的库第二道题我们用了双端队列这道题的重点是优先级队列。Java 和 C 的面试者可以直接用PriorityQueue或priority_queue但用 JavaScript 刷题就得手写堆了。手写堆其实不复杂关键在于吃透两个操作向上调整上浮和向下调整下沉。我用一个最小堆来存[元素, 频率]比较时只看频率。class MinHeap { constructor() { this.heap []; } size() { return this.heap.length; } peek() { return this.heap[0]; } push(item) { this.heap.push(item); this._bubbleUp(this.heap.length - 1); } pop() { if (this.size() 1) return this.heap.pop(); const top this.heap[0]; this.heap[0] this.heap.pop(); this._bubbleDown(0); return top; } _bubbleUp(index) { while (index 0) { const parent Math.floor((index - 1) / 2); // 比较频率当前节点小于父节点就交换 if (this.heap[parent][1] this.heap[index][1]) break; [this.heap[parent], this.heap[index]] [this.heap[index], this.heap[parent]]; index parent; } } _bubbleDown(index) { const n this.size(); while (true) { const left index * 2 1; const right index * 2 2; let smallest index; if (left n this.heap[left][1] this.heap[smallest][1]) { smallest left; } if (right n this.heap[right][1] this.heap[smallest][1]) { smallest right; } if (smallest index) break; [this.heap[smallest], this.heap[index]] [this.heap[index], this.heap[smallest]]; index smallest; } } }然后主函数就很简单function topKFrequent(nums, k) { const freq new Map(); for (const num of nums) { freq.set(num, (freq.get(num) || 0) 1); } const heap new MinHeap(); for (const [num, count] of freq.entries()) { heap.push([num, count]); if (heap.size() k) { heap.pop(); } } return heap.heap.map(item item[0]).reverse(); }为什么最后要reverse()因为堆结构并不保证数组完全有序但堆顶是当前最小频率元素而我们要返回“前 K 个高频元素”顺序在 LeetCode 里通常不重要。如果希望返回数组里越靠前频率越高可以先把数组按照频率排一下也可以直接从堆里逐个pop()弹出的顺序是频率从小到大再reverse一下就是从大到小。上面的.map(...).reverse()实际上取的是heap.heap数组的原始顺序不保证频率严格递减但结果一定是合法 TopK。4.3 时间复杂度分析和桶排序的加分思路小顶堆做 TopK 的时间复杂度是 O(n log k)其中 n 是原数组长度k 是堆的大小。因为堆中始终只保留 K 个元素每次插入和删除都是 O(log k)。如果 K 远小于 n这个优势非常明显。如果 K 接近 n那直接用全排序反而省事所以面试时可以主动讨论“K 的大小对方案选择的影响”这会让面试官觉得你不是在背模板。如果还想进一步优化可以聊聊“桶排序”变体既然频率的取值天然落在[0, n]区间内可以开一个长度为n 1的数组把相同频率的元素放在同一个桶里然后从高频率桶往低频率桶遍历收集满 K 个就停。时间复杂度是 O(n) 的但因为需要额外维护“频率 → 元素列表”的映射空间开销更大。这个思路在“求出现次数最多的元素”这类题里非常通用笔试写出来是加分项。不过我的建议是先稳稳写出小顶堆版本再口头补充桶排序思路。不要一上来就写桶排序万一频率映射处理不好反而容易出 bug。5. 坑位复盘与实战建议5.1 三道题里我踩过、也见过别人踩的坑刷题刷多了你会发现真正让人卡住的往往不是“没思路”而是“边界细节”。我把三道题里最容易踩的坑整理成一个速查表建议收藏下次二刷前先扫一眼。题目经典坑位正确做法150. 逆波兰表达式求值减法和除法中 a、b 顺序颠倒先弹出的叫b后弹出的叫a结果是a - b150. 逆波兰表达式求值JS 中除法结果是浮点数使用Math.trunc(a / b)向零取整239. 滑动窗口最大值队列只存值无法判断是否过期队列必须存下标239. 滑动窗口最大值用shift()模拟队头弹出导致 O(n)在 JS 里可用数组模拟理解“均摊 O(1)”即可追求极端性能可自建 head 指针347. 前 K 个高频元素用大顶堆维护 TopK必须用小顶堆堆顶是“进入 TopK 的门槛”347. 前 K 个高频元素堆里塞了全部 n 个元素每插入一个就检查并弹掉超出 K 的元素还有一个非常容易忽略的坑150 题里的tokens是字符串数组3是字符串也是字符串。判断一个 token 是不是数字不要用typeof token number而要看它是不是运算符。我在第一次实现时用isNaN(token)判断结果把-11这种负数也当成了数字其实误打误撞还算顺利但这种“隐式转换”容易埋雷不如直接维护一个运算符集合判断逻辑更清晰。5.2 从这三道题延伸到工程和面试栈和队列的题目范围其实很广。150 题的思路可以延伸到“基本计算器”“表达式求值”“编译原理里的语法分析”239 题的单调队列则是“滑动窗口极值”这一类题目的核心武器后面做“最长重复字符替换”“最大连续 1 的个数”都能用上类似的双指针加窗口思想347 题更是面试高频因为 TopK 问题在各行各业都会出现比如推荐系统的热门物品、搜索引擎的热搜词、日志系统里的错误统计排名。另外我想多说一句工程方面的联想一说到“队列”不少人会想到“消息队列”“阻塞队列”“线程池的阻塞队列”这些确实是分布式系统和并发编程里的重要概念。但算法题里的队列更“底层”它是一种结构约束消息队列则是生产者消费者模型下的“数据管道”两者并不是一回事。理解了算法里的队列和优先队列再去看“阻塞队列的实现”“DelayedQueue 延迟队列”这些工程概念时你会比只背八股文的人快很多因为你知道底层原理是环形数组、链表还是堆。5.3 刷题节奏的建议Day 11 能做到这里说明前面的数组、链表、哈希表应该都练得差不多了。这三道题放到这个阶段很有讲究150 题考察基础编码规范239 题考察数据结构变形能力347 题考察综合设计能力。我的建议是第一遍先自己做哪怕超时也没关系重要的是能写出一个“能跑”的版本。第二遍再对照正确思路优化。第三遍可以尝试在纸上画出单调队列的入队出队过程能把每一步数组状态写出来这个知识点基本就焊死在脑子里了。如果时间紧至少把 239 和 347 的思路复述一遍因为你不知道面试官会不会突然追问“滑动窗口最大值有没有 O(n) 解法”。我个人的经验是刷题不要一味追求数量这三道题只要做透比囫囵吞枣刷十道题都值。尤其是 239 的单调队列初见可能觉得“这个思路好妙”但你如果能自己推导出“去尾”这一步背后的淘汰逻辑以后再遇到类似问题就不是背诵而是真正的算法思维了。