刷算法题刷到代码随想录day11的栈与队列part2，也就是20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值这三道经典题时，我最大的感受是：栈终于开始干正事了。前面part1用栈实现队列、用队列实现栈，更多是结构层面的互相模拟，而这三道题直接让栈站到了第一线——括号配对的嵌套校验、字符串相邻字符的连锁消除、后缀表达式的求值计算，全都在考验同一个能力：如何高效地“回看最近的关键信息”。这篇文章就把我这天的完整刷题过程、踩过的坑和解题思路整理出来，如果你正在按代码随想录刷题，或者准备算法面试，这部分内容可以直接抄作业。
1. 栈与队列part2到底在练什么：三道题背后的共同规律
1.1 从part1到part2：先会互相模拟，再谈真正应用
代码随想录的题目顺序是有讲究的。part1里的232.用栈实现队列和225.用队列实现栈，本质上是让你先搞清楚两种数据结构的核心差异：栈是先进后出（LIFO），队列是先进先出（FIFO）。你只有在实现层面把这两个特性吃透了，到了part2面对“匹配、消除、计算”这类真实场景时，才会自然地想到用栈去解决。
我见过不少人刷题时跳过part1直接做part2，结果做到150.逆波兰表达式求值的时候，会纠结“为什么这里用栈而不用队列”，其实答案早在part1就埋下了：栈能保留最近的顺序，队列只能保留最老的顺序。而括号匹配、相邻消除、表达式求值，全都依赖于“最近的信息优先处理”这个规律，所以栈是唯一正确的选择。
1.2 匹配、消除、计算：栈的三个经典应用场景
把这天的三道题放在一起看，它们其实是同一种底层模式的不同变体：
- 有效的括号：本质上是一个嵌套结构的对称性校验，内层的括号必须比外层的先闭合，这是一个典型的“后进先出”过程。
- 删除字符串中的所有相邻重复项：当前字符和它“左边最近的那个未消除字符”做比较，相同就一起消失。这个“最近”二字，就是栈顶元素。
- 逆波兰表达式求值：操作数按顺序进来，遇到运算符就取最近的两个操作数做运算，结果再压回去。整个过程完全不依赖运算符优先级，因为顺序已经被后缀表达式固定好了。
三道题都离不开“记住最近状态”这个动作。栈顶操作是O(1)的，每次只需要看栈顶、压栈、弹栈，代价极低，所以这类题用栈解起来又自然又高效。
1.3 面试官视角：为什么这三道题值得反复刷
这三道题在面试里的出场率非常高，尤其是有效的括号，我可以说十个考栈的面试官里至少有七八个会问它或者它的变体。原因也很简单：这三道题的代码量都不大，但它们把边界情况藏在了细节里——空栈能不能访问、最后栈里还有没有残留、运算符弹出时谁先谁后。能把这些边界问题处理干净，说明候选人的代码严谨度是过关的。
更关键的是，这三道题是后面一系列进阶题目的地基。理解了“用栈做相邻匹配”，再去看单调栈、表达式解析、浏览器前进后退的实现，都会觉得顺理成章。所以别嫌它们简单，值得多刷几遍。
2. 有效的括号：一场逐层的对称性校验
2.1 题目理解与暴力解法的局限
题目要求是：给定一个只包含小括号、中括号、大括号的字符串，判断这个字符串中的括号是否合法。合法的意思有两个层面：左右括号数量对得上，而且嵌套顺序必须正确。像([)]这种，虽然三种括号数量都齐了，但因为交叉嵌套，是不合法的。
如果不考虑栈，直观的做法是递归：找到一对匹配的内层括号，消掉之后继续判断。比如[()]，先消掉中间的()，剩下[]，再消掉。但这个思路写起来非常啰嗦，每次都要扫描字符串找配对的括号，时间复杂度最坏能到O(n^2)。而且递归本身还会带来额外的栈空间消耗。所以面试中一旦你提出递归解法，面试官大概率会追问一句：“能不能用栈做一次遍历搞定？”
2.2 栈解法核心思路：遇到的右括号必须匹配最近未闭合的左括号
用一个栈保存“还没闭合的左括号”。遍历字符串的时候，遇到左括号就压栈，遇到右括号就判断它是否等于当前栈顶的那个左括号。如果相等，说明这个右括号恰好闭合了最近的那个左括号，把栈顶弹出；如果不相等，说明括号类型错位了，直接判定非法。
这里有一个小技巧值得记住：压栈的时候，与其压入左括号本身，不如直接压入它对应的右括号。这样遇到右括号时，只需要比较栈顶是否等于当前字符，连map都不用建。代码随想录的写法也是这个思路，测下来确实是最简洁的。
class Solution { public: bool isValid(string s) { // 奇数长度的括号串一定无法完全配对，先剪枝 if (s.size() % 2 == 1) return false; stack<char> 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; else st.pop(); } // 循环结束栈还不为空，说明有左括号没有被闭合 return st.empty(); } };2.3 三个必踩的坑：剪枝、哨兵和残留检查
第一个坑是奇数长度直接返回false。这个剪枝很简单，但很多新手会漏掉。虽然漏掉也能被后面的逻辑拦截，但加一个长度判断可以减少不必要的遍历，也让面试官觉得你考虑问题更全面。
第二个坑是遇到右括号时，必须先判断栈是否为空。如果字符串是"()]"，遍历到]的时候，栈里已经空了，此时访问栈顶就是一个未定义行为，程序直接崩。正确做法是把st.empty()放在st.top() != c的前面，利用短路求值避免越界访问。
第三个坑是最后忘了检查st.empty()。如果字符串是"(()"，前两个左括号都被压栈，但只有一个右括号来匹配，最后栈里还剩一个'('，这种情况同样不合法。很多人遍历完之后直接return true，结果样例"(()"过不去。这三处细节合在一起，就是这道题考察的重点。
2.4 逐行解读代码：为什么左括号压右括号更聪明
上面的代码里，我只写了三个左括号分支，然后一个else分支就处理了所有右括号，逻辑非常顺滑。原因是：左括号出现时，它期望的是将来有一个特定的右括号来闭合它，所以把期望值直接压入栈中；右括号出现时，它只需要回答一个问题——“栈顶是不是我这个字符”，是就配对，不是就失败。
如果压入的是左括号本身，那遇到右括号时就得再加一个反向映射判断，类似if (c == ')' && st.top() != '(')，等于多写三个分支，还要小心map的使用。压入对应右括号的做法，把三类括号统一成了同一个比较逻辑，代码量和出错率都降下来了，这个习惯在后续的“删除字符串中的所有相邻重复项”里也能复用。
2.5 变体与延展：从基础题到实际世界的括号匹配
只含一种括号的情况很好处理，比如"()()"直接用计数器，遇到(加一，遇到)减一，中途小于零或者最后不为零就是非法。但一旦括号种类多了，计数器就失效了，因为([)]的计数是平衡的，嵌套关系却是错的。这就是为什么要用栈，而不是用一个数字来记录状态。
再把视野放大一点：IDE里的代码缩进检查、编译器词法分析阶段的括号匹配、JSON和XML的标签闭合校验，本质上都是在做“最近配对”这件事。刷完这道题之后再去理解这些工具的实现，会觉得亲切很多。
3. 删除字符串中的所有相邻重复项：消消乐的栈版本
3.1 题目理解与为什么用栈天然契合
题目示例是"abbaca"，第一步看到两个相邻的b，消除后变成"aaca"，此时"aa"又相邻了，继续消除，最后剩下"ca"。这种连锁消除的难点在于：你删掉一对字符后，原本不相邻的字符可能重新变成相邻，然后引发新的消除，所以不能只简单遍历一次。
栈天然契合这个问题，因为它的栈顶就是“最近的还没被消除的字符”。遍历到当前字符时，如果它和栈顶相同，说明这两个字符是相邻重复的，直接把栈顶弹掉；如果不同，说明现在没有可消除的，先把当前字符压栈，等后面的字符来跟它配对。
3.2 核心实现逻辑：相同就弹栈，不同就入栈
我自己喜欢用string直接当成栈来用，省去最后拼接的麻烦。核心判断逻辑只有一行：当前字符等于栈顶字符的时候，弹栈；否则压栈。因为栈顶始终代表“字符串当前尾部还没被消除的那个字符”，所以这个比较天然就是相邻比较。
class Solution { public: string removeDuplicates(string s) { string res; // 直接当成栈使用 for (char c : s) { if (!res.empty() && res.back() == c) { res.pop_back(); // 相邻重复，消除 } else { res.push_back(c); // 暂时没得消除，进栈等待 } } return res; } };跑一遍示例：res从空开始，遍历第一个a压栈，此时res="a"；第二个b不等于栈顶a，压栈，res="ab"；第三个b等于栈顶b，弹栈，res="a"；第四个a等于栈顶a，弹栈，res=""；第五个c入栈，res="c"；第六个a入栈，res="ca"。整个过程就是消消乐，只是把消掉的逻辑搬到了栈里。
3.3 代码讲解与复杂度分析
res.empty()的判断不能省。如果你直接对空字符串调用back()，行为是未定义的，在LeetCode的测试环境里大概率直接报错。这就是栈题里最经典的“访问空栈”问题，和2.3节里提到的坑一脉相承。
时间复杂度是O(n)，因为每个字符最多入栈一次、出栈一次，完全线性；空间复杂度最坏是O(n)，比如字符串没有相邻重复项的时候，所有字符都留在栈里。如果直接用std::stack<char>，最后还需要把栈里的字符依次取出再反转，而用string当栈，返回值直接就是想要的答案，省了一步操作。
3.4 为什么用string当栈比stack 更舒服
std::string底层是动态数组，push_back和pop_back都是摊还O(1)的操作，拿它当栈完全没问题。它比std::stack<char>多出来的好处是：能直接返回字符串结果，而stack还得手动倒数据。很多讲解代码会忽略这个细节，我实测下来，面试场景里用string当栈会显得更熟练，代码也短。
当然，理解层面还是要明确string在这里就是栈的替身，别因为这个技巧就混淆了字符串和栈的区别。用std::stack走一遍标准流程，再用string优化，两层都吃透最好。
3.5 和真实开发场景的连接：撤销、历史记录与文本编辑器
栈的“回看最近状态”能力在开发工具里无处不在。最典型的是文本编辑器的撤销功能——每次编辑操作被压入一个操作栈，按Ctrl+Z就从栈顶弹出一个操作并还原。浏览器的后退按钮也是同一个模型，把访问过的页面压进栈，后退就是弹栈。
更贴近这道题的是编辑器里的“相邻字符处理”：比如你写了一篇Markdown，连续删掉两个同样的字符、或者自动配对引号变成双重引号，代码里处理这些逻辑时，背后往往就藏着一个栈。刷完这道题之后，再看这些工具的实现思路，会比之前清晰很多。
4. 逆波兰表达式求值：从人脑到栈的运算规则转换
4.1 什么是逆波兰表达式：后缀表达式为什么被发明出来
我们平时写的1 + 2 * 3是中缀表达式，运算符在两个操作数中间，读起来符合直觉，但计算机处理它需要额外考虑运算符优先级和括号。逆波兰表达式也叫后缀表达式，把运算符放到操作数后面，比如1 2 3 * +，它不需要括号，也不需要优先级规则，因为表达式的顺序已经把计算次序固定了。
这个想法来自波兰逻辑学家卢卡西维茨，所以叫“逆波兰”。“逆”是因为正常波兰表示法是前缀（运算符在操作数前面），他这个是把运算符放后面。很多老式计算器，尤其是HP的工程计算器，至今仍使用RPN输入方式，输入数字按回车压栈，按运算符弹栈计算，和这道题的逻辑完全一样。
4.2 用栈模拟运算过程：数字入栈，运算符触发归约
求值规则很简单：遇到数字就压栈，遇到运算符就从栈顶弹出两个数，做运算，再把结果压回栈里。这里有一个非常容易错的细节：先弹出的是右操作数，后弹出的是左操作数。
拿示例跑一遍：["2","1","+","3","*"]。先是2入栈，再是1入栈，遇到+，弹出1作为num2、弹出2作为num1，计算2+1=3，把3压回栈。接着3入栈，遇到*，弹出3作为num2、弹出3作为num1，计算3*3=9，最终栈顶就是9。
这里为什么先弹出的是右操作数？因为表达式是顺序进入的，越晚进入的数字在栈顶，而数字进的顺序就是从左到右，所以栈顶对应右边的操作数，它的下面那一个才是左边的操作数。减法和除法尤其依赖这个顺序。
class Solution { public: int evalRPN(vector<string>& tokens) { stack<long long> st; for (string& s : tokens) { if (s == "+" || s == "-" || s == "*" || s == "/") { long long num2 = st.top(); st.pop(); long long num1 = st.top(); st.pop(); if (s == "+") st.push(num1 + num2); else if (s == "-") st.push(num1 - num2); else if (s == "*") st.push(num1 * num2); else st.push(num1 / num2); // 整除 } else { st.push(stoll(s)); // 字符串转 long long } } return (int)st.top(); } };4.3 两个必踩的细节坑：操作数顺序和整除方向
第一个坑就是4.2节说的减法顺序。表达式["5","3","-"]，正确结果是5-3=2。如果弹出后算num2 - num1，就会变成3-5=-2，样例直接过不去。除法同理，["4","2","/"]正确是2，算反了会得到0，因为2/4=0。每道栈题里都藏着一个操作数的顺序问题，这道题是最典型的。
第二个坑是整除方向。C++的整数除法是向零截断的，比如-3 / 2 = -1，这恰好符合这道题的要求。但如果你用Python做，默认的//是向下取整，-3 // 2会得到-2，就错了。在Python里想保持向零截断，得写成int(num1 / num2)，用浮点数除法之后截断，我这里特别提醒一下跨语言刷题的朋友。
4.4 为什么编译器最终选择了后缀表达式
中缀表达式对计算机来说并不友好，因为1 + 2 * 3必须知道*的优先级高于+，这需要额外的规则或者括号。编译器在处理表达式时，通常会把中缀转成后缀，再顺序求值。转换的经典算法叫调度场算法，用两个栈分别保存运算符和输出结果，遇到低优先级运算符时就把高优先级的先弹出去。
这个过程本质上就是把“人的阅读习惯”翻译成“机器的线性处理方式”。后缀表达式还可以直接对应表达式树的后序遍历：树的中序遍历是中缀，后序遍历就是后缀。理解了这道题，后面再接触编译原理里的表达式解析，就会觉得编译器这么做是有道理的，因为它最大程度利用了栈的顺序性。
4.5 边界情况与实际工程中的提醒
实际写的时候要小心除数为零，LeetCode的测试数据里一般不包含，但自己练习时可以额外判断一下。另一个容易被忽略的是中间结果溢出：题目允许的整数范围很大，中间计算可能超出int的范围，所以我代码里用long long来存操作数和中间结果，最后再转回int，这样最稳。
工程实践里，如果自己写一个基于RPN的计算器，还需要考虑数字里包含负号的情况，比如"-4"看起来像运算符，实际是数字。LeetCode的测试数据中负数可以作为操作数出现，stoll能正确处理带符号的字符串，所以我的代码里把“判断是否是四则运算符”放在最前面，剩下的通通按数字处理，这个顺序非常关键。
5. 三题复盘：规律、延伸与刷题节奏
5.1 三题核心套路对比：一张表看懂共同点
刷完三道题之后，我建议你合上代码，用一张表的形式在脑子里过一遍它们的共性：
| 题目 | 核心动作 | 栈的职责 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 20. 有效的括号 | 左右括号配对 | 暂存等待匹配的左括号 | O(n) | O(n) |
| 1047. 删除字符串中的所有相邻重复项 | 相邻相同字符消除 | 暂存最近的未消除字符 | O(n) | O(n) |
| 150. 逆波兰表达式求值 | 表达式运算 | 暂存中间操作数 | O(n) | O(n) |
看见没有，全是O(n)时间、O(n)空间，全都依赖“栈顶是最近信息”这一条。下次遇到一道新题，只要问题描述里出现了“最近的”“相邻的”“嵌套的”“向后看”这些关键词，第一反应就该是栈。
5.2 从这三题延伸出去：单调栈、单调队列和优先队列
这三题刷完，代码随想录的栈与队列专题其实就基本收官了，但它们的延伸题更值得留意。比如239.滑动窗口最大值，用的是单调队列——队列里的元素保持单调递减，每次取队首就是窗口最大值，这是“队列”进阶用法；347.前K个高频元素，用的是优先级队列也就是堆；还有后面的单调栈专题，像每日温度、接雨水，都是利用栈内元素的单调性来求解。
另外，你在面试中一旦提到队列，很容易被追问到工程领域的消息队列：Kafka、RabbitMQ、RocketMQ怎么选型，线程池的阻塞队列怎么选。这些看起来高大上的名词，起点其实就是算法里这个朴素的FIFO队列。生产者-消费者模型、队列的入队出队、顺序保证这些概念，在算法题里先打好底子，再去理解消息队列的ACK机制、重复消费、顺序消费，会轻松很多。
5.3 栈在程序运行时的身影：函数调用栈与栈帧形成过程
栈的应用远不止算法题。程序运行时，每一次函数调用都会在系统栈上分配一个栈帧，栈帧里保存了返回地址、参数、局部变量和寄存器状态。函数开始执行时栈帧压栈，函数返回时栈帧弹栈，这个“压栈-弹栈”的过程和算法题里的入栈出栈完全一致。
理解这件事之后，很多概念都能串起来：递归能写成函数调用自己的形式，是因为系统帮你维护了调用栈；递归深度太大会导致栈溢出，是因为栈空间是有限的；程序崩溃时打印的backtrace栈回溯，就是从当前函数一层层往上找，把栈帧里的函数名字列出来。甚至那句“C语言局部变量越少，占用的栈空间越小”，说的也是栈帧里的局部变量区域会更小。这些知识点回到代码层面，都指向栈这一个核心结构。
5.4 我的刷题经验与节奏建议：一天三道题该怎么消化
我按代码随想录的节奏刷下来，个人体会是：一天三道题刚刚好，再多就容易走马观花。具体安排可以这样：上午先做20.有效的括号，下午做1047和150，每道题先自己思考15到20分钟，想不出来再看题解。题解看懂之后不要急着收工，把代码抄一遍，然后合上题解自己重新写一遍，写到完全不需要看答案为止。
第二天早上，花15分钟把这三道题再快速过一遍。哪道题卡住了，说明那道题的思路还没真正长在脑子里，需要再刷一遍。这三道题都不算难，但它们是后面所有栈相关题目的地基，地基打不牢，后面的单调栈、表达式解析、括号生成都会比较吃力。
最后分享一个我实际用下来很有用的小习惯：刷栈和队列这类题，我面前会放一张白纸，每遇到一个入栈出栈操作就往纸上写一遍当前栈的状态。刚开始觉得有点多余，但刷到day11这三题就会发现，能徒手在纸上完整复现栈的变化过程的人，和只能对着代码一步步调试的人，对栈的理解深度完全是两个层次。栈这个东西，只要真正理解了“回看最近”这四个字，后面无论是单调栈、逆波兰、函数调用栈，还是消息队列的那堆延伸概念，都不会再觉得陌生。
