核心记忆锚点栈 叠盘子后放的先拿队列 排大队先来的先办一、先抓本质两个生活模型一眼懂1. 栈Stack 餐厅叠盘子模型规则后进先出 LIFO就像后厨叠餐盘新盘子永远摞在最上面取的时候也只能先拿最顶上那一个 —— 最后放进去的最先被取出来。底下的盘子会被暂时压住等上面的都拿走才能碰到。2. 队列Queue 食堂打饭排队模型规则先进先出 FIFO就像食堂窗口排队新人永远站在队尾打饭永远从队头开始 —— 最先来的人最先吃上饭。先来先服务绝不插队。二、栈叠盘子高频场景 12 个经典例子场景共性优先处理最新加入的元素需要回溯、原路返回、就近匹配、逆序操作往深处走走到头再回头。分类举例基础入门类有效括号匹配遇到右括号时只和「最近的左括号」配对配对成功就弹出 → 栈字符串逆序输出字符挨个压栈再依次弹出天然得到反转结果 → 栈CtrlZ 撤销操作最后一步操作最先被撤销每一步操作压栈撤销就弹栈 → 栈算法笔试高频题每日温度 / 下一个更大元素找数组中每个元素右边第一个比它大的数用单调栈就近匹配 → 栈接雨水用单调栈记录凹槽边界按层计算每个位置能接的雨水量 → 栈简化 Unix 文件路径遇到../就回溯到上一级目录相当于撤销上一步路径 → 栈删除字符串相邻重复项比如 abbaca 消除成 ca新字符只和「栈顶最近的字符」比对消除 → 栈逆波兰表达式求值后缀表达式如[2,1,,3,*]遇到运算符就取最近两个数计算 → 栈二叉树前 / 中 / 后序迭代遍历一路向左走到叶子节点走不通了再回溯父节点 → 栈迷宫深度优先搜索DFS一条岔路走到黑撞墙了就退回上一个路口换方向 → 栈系统 / 工程场景函数调用栈程序中函数嵌套调用最后调用的函数最先执行完返回 → 栈浏览器前进后退用两个栈实现后退时当前页压入前进栈前进时从前进栈弹出 → 栈三、队列排大队高频场景 12 个经典例子场景共性按到达顺序依次处理逐层扩散、一圈一圈向外拓展求无权最短路径任务排队、先来先服务。分类举例基础入门类银行叫号系统先取号的人先办理业务按排队顺序叫号 → 队列消息队列MQ生产者先发的消息消费者最先消费处理 → 队列打印任务排队先发送的打印任务最先被打印机执行 → 队列算法笔试高频题二叉树层序遍历从上到下、一层一层打印节点本层节点全部处理完再处理下一层 → 队列二叉树右视图 / 层平均值 / 最大层内元素和层序遍历的变种按层统计信息 → 队列腐烂的橘子多源 BFS每分钟所有烂橘子同时感染周围一圈按层扩散 → 队列打开转盘锁求从起点到目标密码的最少转动次数无权最短路径天然用 BFS → 队列岛屿数量BFS 版遇到陆地就一圈一圈向外标记把同一片岛屿全部遍历完 → 队列滑动窗口最大值用单调队列维护窗口内的元素窗口滑动时队头始终是最大值 → 队列约瑟夫环n 个人围成圈报数数到 m 的人出圈用队列模拟循环排队出圈 → 队列01 矩阵最短距离求每个格子到最近 0 的距离所有 0 同时作为起点多源扩散 → 队列完全二叉树合法性判断层序遍历节点遇到空节点后不能再出现非空节点 → 队列系统 / 工程场景线程池任务队列提交的任务按先后顺序分配线程执行漏桶限流算法请求按排队速率匀速处理削峰填谷广度优先爬虫先爬完一级页面所有链接再爬二级页面链接四、最容易搞混的 6 组场景一句话掰明白二叉树遍历一路扎到叶子再回头访问 → 栈前 / 中 / 后序整层扫完再进下一层 → 队列层序遍历迷宫 / 图的搜索只判断能不能到达、想省内存 → 栈 DFS必须求最少步数 / 最短路径→ 队列 BFS字符串消除类问题只和「最近一个元素」匹配、消除 → 栈从左到右按顺序挨个处理、不回溯 → 队列单调进阶变种单调栈找左右第一个更大 / 更小元素 → 本质是栈的「就近匹配」特性单调队列维护滑动窗口最值 → 本质是队列的「按序出队」特性递归与迭代改写递归代码 → 底层靠操作系统的函数调用栈实现把递归改成非递归迭代版 → 必须手动写一个栈来模拟扩散类问题从一个点一路深入、走到底再换路 → 栈从一个 / 多个起点同时向外、一圈圈扩大范围 → 队列五、万能判断三步法考场直接套遇到拿不准的题按顺序问自己三个问题取数顺序我需要优先拿「最晚放进去的」还是「最早放进去的」最晚放的先处理 → 栈最早放的先处理 → 队列遍历方式搜索类题目是「一路走到黑再折返」还是「一层一层向外扩散」深度探索、回溯折返 → DFS → 栈分层扩散、按层推进 → BFS → 队列业务语义需求是「撤销 / 回溯 / 就近配对」还是「排队 / 按序执行 / 公平处理」回溯、就近、撤销 → 栈排队、顺序、公平 → 队列六、实战小测10 道题秒判答案附后试试用上面的方法快速判断下面题目该用栈还是队列实现编辑器的撤销、重做功能求二叉树的最小深度层序实现判断大括号、中括号、小括号是否合法嵌套求柱状图中最大的矩形无向图中两个节点的最短路径长度秒杀系统的请求排队削峰去除字符串中所有相邻且相同的字符洪水填充算法油漆桶工具后缀表达式逆波兰式计算结果固定大小窗口内的最大值details summary点击查看答案/summary 栈1、3、4、7、9 队列2、5、6、8、10 /details最终速记口诀深搜用栈广搜用队回溯就近用栈分层排队用队。后进先出选栈先进先出选队。谢谢
