代码随想录刷到 Day13，正好是栈与队列专题。这一天的四道题——232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047.删除字符串中的所有相邻重复项——看着是四道独立的题，实际串起来就是一条完整的思路链：先用栈和队列互相模拟去理解两者的行为差异，再用栈去解决括号匹配和相邻重复删除这两个最经典的场景。如果你正在刷题入门阶段，这四道题属于那种“搞懂了就不难，没搞懂就处处别扭”的类型，非常值得停下来细细复盘。这篇文章就把我自己的实现思路、踩过的坑和细节上的优化过程完整写出来。
1. 先搞懂栈与队列的本质差异
1.1 栈：只从一端进出的“叠盘子”
栈这个东西，你用代码实现就是几行，但它的行为特性你得先刻在脑子里：只能在同一端（栈顶）做插入和删除。我用叠盘子来理解它——你往一摞盘子上叠新盘子，只能放在最上面；拿盘子，也只能从最上面拿。想拿最下面的那个盘子？对不起，你得先把上面的全挪走。所以栈的进出顺序是后进先出（LIFO），最后一个进去的元素，永远最先出来。
工程里的例子到处都是：文本编辑器的撤销（Ctrl+Z）就是一个栈，每次撤销都是撤销最近一次操作；浏览器后退按钮也是栈，你点后退，返回的是最近访问的页面。函数调用栈更是基础中的基础，一层层函数调进去，再一层层返回来，顺序严丝合缝。
在 Python 里用list模拟栈极方便，append()入栈、pop()出栈，两个操作都是 O(1)。需要注意的就是别用list头部的操作，比如pop(0)、insert(0, ...)，那是 O(n) 的，栈的语义也完全不是这样。
1.2 队列：两端的“排队通道”
队列对应的生活场景就是排队，我常举的例子是排队买奶茶。新来的人排在队伍末尾，队伍最前面的人先拿到奶茶走人。所以队列是先进先出（FIFO），先来的先走，后来的后走。
实现队列在 Python 里有个小讲究：别用list模拟队列的头部弹出。list.pop(0)会把后面所有元素都往前挪一位，时间复杂度 O(n)，数据一多直接拉胯。正确的做法是用collections.deque，它的append()和popleft()都是 O(1)。deque 底层是双向链表或者分块数组，反正两头操作都高效就对了。
1.3 为什么要把这两个结构放在一起学
栈和队列都是线性表，底层都可以用数组或者链表实现，唯一的区别就是出入口规则。232 题要求用栈实现队列，225 题要求用队列实现栈，这种“互相模拟”的题目，真的是检验理解程度的试金石。你背会“栈是 LIFO、队列是 FIFO”这句话很容易，但当你真正动手用栈去模拟队列行为时，才发现顺序反转、双栈协作这些细节，一写就暴露你懂没懂。
从刷题路线的角度看，栈与队列也是后面一堆难题的地基。单调栈、滑动窗口、表达式求值、BFS 的队列实现，全都依赖今天这几道题建立起来的直觉。所以 Day13 这四道题，刷的时候别急着 AC，多想想每一步为什么这么写。
2. 232. 用栈实现队列：双栈倒腾才是正解
2.1 核心思路：两个栈，一个管进一个管出
一个栈实现不了队列，原因很简单：栈是 LIFO，你往栈里依次 push 1、2、3，pop 出来是 3、2、1，顺序反了。队列需要的是先进先出，你希望 pop 出来是 1、2、3。
怎么把顺序再反转一次？再用一个栈。第一个栈叫stack_in，专门负责接收 push 进来的元素；第二个栈叫stack_out，专门负责 pop 时提供元素。关键操作发生在 pop 的时候：如果stack_out是空的，就把stack_in里的所有元素全部弹出，再按顺序压进stack_out。这样顺序被反转了两次，负负得正，stack_out的栈顶正好是队列的队头。
我实际推演一遍你就懂了：push 1、2、3 后，stack_in = [1, 2, 3]（栈顶是 3）。现在要 pop，stack_out为空，执行迁移：从stack_in依次弹出 3、2、1，压入stack_out，迁移完stack_out = [3, 2, 1]，栈顶是 1。stack_out.pop()返回 1，完美，这就是队列应该弹出的第一个元素。
这里有个很重要的细节：必须等stack_out空了，才能从stack_in倒数据，而且一倒就是全部倒完。为什么？你想想，如果stack_out里还有元素时就往里面倒新数据，新数据会压在旧数据上面，那 pop 出来的顺序就乱了；如果只倒一半，另一半留在stack_in里，下次再倒时顺序又对不上。所以规则就是：stack_out空 → 一次性倒空stack_in。
2.2 代码实现：边写边讲每个方法
class MyQueue: def __init__(self): self.stack_in = [] # 负责入队 self.stack_out = [] # 负责出队 def push(self, x: int) -> None: self.stack_in.append(x) def pop(self) -> int: if self.empty(): return -1 if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) -> int: # 复用 pop，再把元素还回去 res = self.pop() self.stack_out.append(res) return res def empty(self) -> bool: return not self.stack_in and not self.stack_outpush没什么好说的，直接进stack_in。pop里第一行if self.empty()是防御性判断，LeetCode 的题目保证不会对空队列调用 pop，但写出来更稳。中间那段 while 是核心：只在stack_out为空时才触发迁移，迁移时用while self.stack_in保证一次倒干净。
peek我用了“复用 + 还回去”的写法：先调用pop()拿到队头元素，再把元素压回stack_out。因为pop()已经把迁移逻辑处理好了，所以peek就不用重复写迁移的代码，这也是一个减少重复代码的小技巧。不过要注意，pop()里我加了if self.empty(): return -1，所以peek复用的时候也得接受 pop 返回的是有效元素，不能拿 -1 当真元素压回去。实际刷题时题目保证不会空调用，这个问题不大，但思路要清晰。
2.3 复杂度分析和两个容易忽略的细节
先算复杂度。push就是一次 append，O(1)。pop乍一看是 O(n)，因为要倒数据，但仔细想想：每个元素最多被弹出stack_in一次、压入stack_out一次，真正被 pop 也就是一次。整体看，n 次操作总的元素移动次数是 O(n)，均摊到每次操作就是 O(1)。这就是摊还分析（amortized analysis），面试里常被问到，建议自己心里过一遍这个推导。
第二个容易忽略的细节是peek的另一种写法。如果你不想用“pop 再还回去”这种复用方式，也可以直接判断stack_out是否为空，为空就先迁移，然后返回stack_out[-1]。好处是peek不会改变队列状态，逻辑更直白：
def peek(self) -> int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1]两种写法都对，我个人的习惯是复用pop，因为pop已经保证了迁移逻辑只会写一份。但面试的时候，如果面试官让你分别实现 peek 和 pop，用第二种会更直观，不容易绕晕。
3. 225. 用队列实现栈：两种写法各有取舍
3.1 两个队列的写法：把队尾“抬”到队首
队列模拟栈，思路和栈模拟队列不太一样。栈的 pop 要弹出最后进来的元素，也就是队列的队尾，但队列只能从队头弹出元素，所以核心操作就是：把队尾元素变成队头元素。
两个队列的做法是：维护一个主队列queue_in，push 时直接进主队列。pop 时，把主队列里除了最后一个元素以外的所有元素，全部挪到辅助队列queue_out，此时主队列剩下的那个元素，就是最后进来的“栈顶”，直接popleft()弹出。然后交换两个队列的引用，保证下次继续用主队列接收新元素。
我举个例子：队列里现在是 [1, 2, 3]（队头是 1，队尾是 3，对应栈顶是 3）。要 pop，把 1、2 挪到辅助队列，主队列只剩 [3]，弹出 3。此时辅助队列是 [1, 2]，交换引用，主队列变成 [1, 2]，下一次 pop 就继续把 1 挪走，弹出 2。顺序完全符合栈的后进先出。
3.2 一个队列的写法：循环左移 n-1 次
其实仔细想，辅助队列并没有存什么特殊数据，它只是临时存放“暂时不要的元素”，最终还是要回到主队列。既然这样，用一个队列就够了：pop 的时候，把队头的元素依次弹出、再压到队尾，循环 n-1 次，队头就是原来的队尾。
代码非常干净：
from collections import deque class MyStack: def __init__(self): self.queue = deque() def push(self, x: int) -> None: self.queue.append(x) def pop(self) -> int: if self.empty(): return -1 for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) return self.queue.popleft() def top(self) -> int: res = self.pop() self.queue.append(res) return res def empty(self) -> bool: return not self.queue看pop里的那个 for 循环：len(self.queue) - 1次，每次把队头挪到队尾。比如队列是 [1, 2, 3]，第一次 popleft 拿到 1，append 回去变成 [2, 3, 1]；第二次 popleft 拿到 2，append 回去变成 [3, 1, 2]；循环结束，队头是 3，popleft()弹出，正好是栈顶。
这是一种“轮转”的思路：队列就像一个环形结构，你不停地从一端取元素放到另一端，转一圈之后，原来的队尾就自然到了队头。
3.3 对比：push O(1) 好还是 pop O(1) 好
用上面的写法，push 是 O(1)，pop 是 O(n)。那能不能反过来，push O(n)、pop O(1)？也可以。做法是：每 push 一个新元素，就把队列里已有的元素全部循环挪到新元素后面，这样新元素永远在队头，pop 的时候直接popleft()就行。
两种方案总的均摊复杂度其实一样，n 次操作都是 O(n) 的移动总量，区别只是把开销放在哪。我个人的建议是：记住“单队列 + pop 时轮转”这种写法，它最好理解、代码最少。面试时如果你能主动提一句“其实一个队列就够了”，会显得你对这个问题的认识更深一层。
再补充一个 top 的实现细节。上面代码里top是复用pop，然后把元素还回去，这和 232 的 peek 思路完全一样。还有一种做法是维护一个top_value变量，每次push时更新它为最新入队的元素，这样top就是 O(1)。但用“复用 + 还回去”的方式，代码统一，也不容易漏更新变量，我更喜欢这个。
4. 20. 有效的括号：栈的教科书级应用
4.1 无效括号的三种情况
这题我当年第一次做的时候，总觉得要分很多种情况处理，后来理清楚了，其实就三种：
- 左括号多了：比如
"(()"，遍历完整个字符串，栈里还剩一个'('没被匹配，说明多了个左括号。 - 右括号多了：比如
"())"，遍历到第二个')'时，栈已经空了，没有左括号可以和它匹配。 - 左右括号类型不匹配：比如
"(]"，遍历到']'时，栈顶是'('，和']'对应的'['对不上。
只要代码把这三件事都判断到，这题就稳了。
思路也很直接：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶。栈顶如果是匹配的左括号，就弹出去；如果栈空或者不匹配，直接返回 False。遍历结束后，如果栈为空，说明所有左括号都被匹配掉了，返回 True。
4.2 代码实现：用一个字典做映射
def isValid(s: str) -> bool: if len(s) % 2 == 1: return False stack = [] mapping = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in mapping: # 当前是右括号 if not stack or stack[-1] != mapping[ch]: return False stack.pop() else: # 当前是左括号，入栈 stack.append(ch) return not stack这里我用了一个字典mapping，把右括号映射到对应的左括号。这样判断stack[-1] != mapping[ch]一行就能完成“类型不匹配”的校验，不用写三个 if。哈希映射的好处是：以后如果括号类型多了，比如加上[、]以外的自定义标记，只需要往字典里加一对映射，代码逻辑不用动。
4.3 易错点，全是我刷题时踩过的
第一个坑：访问stack[-1]之前必须先检查stack是否为空。Python 里空列表取stack[-1]会直接抛IndexError，如果不加not stack这个判断，遇到")"这种开头就是右括号的用例直接崩。
第二个坑：判断一个字符是否右括号，用if ch in mapping。这个写法很巧妙，因为字典的 key 全是右括号，ch in mapping就等价于判断 ch 是不是右括号。反过来，左括号就走 else 分支入栈。不需要额外再维护一个左括号集合。
第三个坑：奇数长度直接剪枝。字符串长度为奇数，括号永远不可能全部匹配，直接返回 False。这是一个小优化，但能体现出你对题目边界条件的把握。
第四个坑：处理多层嵌套时的栈深度。比如"[{([({})])}]"这种深层嵌套的字符串，显式用栈是安全的，因为 Python 的递归深度有限制。这题如果用递归思路去做推导，嵌套一深就容易碰到递归层数上限，但用循环 + 显式栈就完全没有这个问题。
这题背后的应用场景也很实在：编译器的语法检查、IDE 里的括号自动匹配高亮、XML/HTML 标签嵌套校验，本质上都是同一个模型。刷完这题，你对“CPU 怎么校验括号”就有了具体的画面感。
5. 1047. 删除字符串中的所有相邻重复项：消消乐背后的栈思路
5.1 为什么栈能高效解决“消消乐”
先看题目给的例子："abbaca"。第一次看到bb相邻重复，删掉，字符串变成"aaca"。这时候aa又相邻重复了，再删，最后得到"ca"。
关键点在于：删除一对字符后，新的相邻关系可能继续触发新的删除。这个“连锁反应”如果用暴力解法，每删一次就要重新扫描字符串，时间复杂度很高。但如果你用栈，一切就顺理成章了：
遍历字符串，每次只跟栈顶比较。如果当前字符和栈顶相同，说明栈顶和当前字符是一对相邻重复项，把栈顶弹出去，相当于“消掉”；如果不同，就把当前字符压入栈顶，等待后续匹配。
拿"abbaca"推演一下：a 入栈 → b 入栈 → 下一个 b 和栈顶 b 相同，弹出 b → 下一个 a 和栈顶 a 相同，弹出 a → 当前栈空 → c 入栈 → a 入栈。最后栈里剩[c, a]，拼成字符串就是"ca"。
这个模型像什么？我觉得特别像消消乐或者俄罗斯方块——新方块落到顶部，如果和上一个方块颜色一样就消除，不一样就叠上去。每次只要关注“当前的最后一块”就够了，之前的历史都被栈牢牢记着。
5.2 代码实现：前后两种思路对比
def removeDuplicates(s: str) -> str: stack = [] for ch in s: if stack and stack[-1] == ch: stack.pop() else: stack.append(ch) return ''.join(stack)就这么多，核心逻辑只有三行：入栈、比较、弹出。时间复杂度 O(n)，空间复杂度 O(n)，n 是字符串长度。
我再看另一种写法，用双指针做原地操作，可以把空间省到 O(1)（如果忽略结果字符串本身占用的空间）。思路是把字符串转成字符数组，用slow指针表示“当前结果写到哪了”，用fast指针遍历原字符串：
def removeDuplicates(s: str) -> str: chars = list(s) slow = 0 for fast in range(len(chars)): if slow > 0 and chars[slow - 1] == chars[fast]: slow -= 1 else: chars[slow] = chars[fast] slow += 1 return ''.join(chars[:slow])slow这个指针模拟的就是“栈顶位置”。slow > 0相当于stack非空，chars[slow - 1]相当于stack[-1]。如果相同就slow -= 1，相当于弹出；如果不同就把chars[fast]写到slow位置然后slow += 1，相当于入栈。
这个优化有点意思，但我的建议是：第一步先用栈版本 AC，再去看原地双指针。双指针思路在代码上确实省了空间，可读性不如栈版本直观。面试的时候，先把栈版本解释清楚，再提一句“可以用双指针做原地优化”，就显得你对复杂度和代码思路都有掌控。
5.3 和“有效的括号”放在一起看，模板就出来了
20 题和 1047 题，一个是括号匹配，一个是相邻重复删除，表面看起来不同，但用栈的姿势一模一样：遍历每个字符，跟栈顶比较，能匹配就弹出，不能匹配就入栈。
- 20 题里：遇到右括号，检查栈顶是否为对应的左括号，是则弹出，否则返回 False。
- 1047 题里：遇到字符，检查栈顶是否相同，是则弹出，否则入栈。
区别只在比较条件和弹出条件，剩下的骨架完全一致。所以很多刷题人会告诉你，栈的“相邻消除类”题目是有一套通用模板的。你刷完这两题，可以自己总结出一句话：“凡是需要回头看最近一个元素、并且可能产生连锁反应的问题，优先想栈。”后面再遇到类似题目，比如“删除字符串中出现次数大于 2 的相邻重复项”“行星碰撞”这类变体，你就能触类旁通了。
6. 四道题纵向对比与刷题心得
6.1 一张表对照核心考点
四道题全部刷完，我习惯放在一起做一次横向对比，这样复习时一眼能抓住重点。
| 题号 | 题目 | 核心考点 | 时间复杂度 | 空间复杂度 | 最关键的一步 |
|---|---|---|---|---|---|
| 232 | 用栈实现队列 | 双栈协作，顺序反转两次 | push O(1) / pop 均摊 O(1) | O(n) | 只有 out 栈空了才一次性倒数据 |
| 225 | 用队列实现栈 | 队列轮转，把队尾移到队头 | push O(1) / pop O(n) | O(n) | pop 前循环左移 n-1 次 |
| 20 | 有效的括号 | 栈顶比较 + 哈希映射 | O(n) | O(n) | 先判空再访问栈顶 |
| 1047 | 删除相邻重复项 | 栈顶比较 + 相邻消除 | O(n) | O(n) | 相同就弹，不同就压 |
从这张表能看出两个特点。第一，时间复杂度的关键在于你要不要访问“另一头”的元素：栈访问的是栈顶，天然顺手；队列访问队尾，就得先把前面的元素挪走。第二，空间复杂度基本都是 O(n)，因为需要用一个额外容器存储“还没处理完的元素”，这也是这类题型的普遍代价。
6.2 栈与队列互相模拟的统一思维模型
232 和 225 放在同一天刷，最大的收获是你会发现“用 A 模拟 B”是有通用套路的：
模拟的本质，是用底层数据结构的操作，去实现目标数据结构的操作语义。你需要承认一个现实：底层数据结构做不到“直接”完成目标操作，所以你要么做额外搬运（队列模拟栈时的轮转），要么做顺序反转（栈模拟队列时的双栈）。
具体到操作层面，就两个关注点：
- 迁移时机：栈模拟队列时，必须在 out 栈为空才迁移；队列模拟栈时，必须在 pop 时一次性把前 n-1 个元素挪走。时机错了，顺序就乱了。
- 空判断：pop 和 top/peek 之前，都要判断当前是否为空，不然就会越界或返回错误结果。
我刷完这两道模拟题之后，再看 20 和 1047，忽然觉得前面两题练的“对栈顶和队头的敏感度”直接派上了用场。这就是为什么刷题路线要把它们安排在同一天——模拟题训练你对数据结构行为的理解，应用题训练你把它用到具体场景中的能力。
6.3 我的踩坑记录和几个实用习惯
最后分享几个我在实操中反复踩过、后来养成习惯的点：
空容器访问越界。Python 里stack[-1]在空栈时报 IndexError，popleft()在空队列时也会报错。所以只要涉及取栈顶/队头，我写的第一个判断永远是if not stack / if not queue。这个习惯在 20 题和 1047 题里尤其关键，因为你不知道测试用例里会不会突然来一个空字符串或者以右括号开头。
peek/top 复用 pop 时记得还元素。232 和 225 的题目都要求实现 peek/top，我一开始写 peek 时直接对底层容器取[-1]，结果没有考虑数据还在 stack_in 里的情况。后来改成复用 pop 再还回去，逻辑就顺了。但“还回去”这个动作容易漏，你要清楚自己写的 peek 是否改变了数据结构状态。
Python 里 deque 和 list 的选用。只要涉及“队列”操作，我统一用collections.deque，哪怕刷题时数据量不大，这是习惯问题——避免某天遇到大数据量时直接用list.pop(0)写出 O(n) 的代码。而模拟栈就用普通list，append/pop足够。
先写方法签名，再填实现。像 232、225 这种要设计一个类的题，我拿到题先把__init__、push、pop、top/peek、empty的签名列出来，再一个个想每个方法要调用哪些辅助逻辑。这个方法能让你避免“写一个方法时发现另一个状态变量还没初始化”的尴尬。
这四道题刷完，我对栈和队列的理解明显上了一个台阶，尤其是“什么时候用栈、什么时候用队列”不再靠背，而是能根据题目场景自然判断。建议你也尝试在做完一组题后，像我一样画一张对比表、总结一个通用模板，这种“复盘”比多刷十道新题都管用。
