企业官网建设流程全解析

代码随想录训练营到第10天，主题是栈和队列。如果你是从零开始刷的，前面几天数组、链表、哈希表下来，应该已经有一个感觉：绝大多数题目本质上都是在和“存取方式”较劲。栈和队列最特别的地方在于，它们底下其实还是数组或者链表，但被强行规定了操作接口，一个只能从一头进出，一个只能一头进另一头出。这篇内容适合两类人：一类是跟着训练营节奏走、想把这章题目吃透的新手，另一类是刷过但总是混淆pop和peek、不清楚该用deque还是stack的老朋友。我会从底层原理讲到训练营第10天的四道核心题，最后再聊一些刷题之外的工程联想。

1. 为什么第10天要把栈和队列放在一起学：先补上底层认知

1.1 栈：一条只能从一头进出的“死胡同”

栈的抽象定义大家都会背：后进先出（LIFO）。但真正动手写过实现的人，可能反而比背定义的人印象更深。用数组实现一个栈，只需要一个指针：push写进数组当前位置并把指针往上移，pop把指针往下移就行，整个操作的时间复杂度是O(1)。用链表实现栈同样简单，只在头部插入和删除即可。之所以它能做到O(1)，就是因为操作被限制在了一个端点上。

可能有人会问：既然数组和链表都能实现栈，那刷题时到底用什么？这取决于语言。C++里std::stack默认底层是deque，也可以用vector或者list作为底层的模板参数；Java里Stack是Vector的遗留子类，官方其实更推荐使用ArrayDeque；Python没有专门叫Stack的类，list自带append和pop，天然就是栈。这些底层差异平时刷题不太容易暴露，但当你真正做工程时，就会开始关心内存分布、扩容成本和缓存命中率，那时候回头再看栈的底层，思路会完全不一样。

栈在生活中最形象的类比就是死胡同：最先进去的车，要等后面的车全部倒出来之后才能出来；换到编程场景，函数调用的过程就是靠栈来管理的，每一个函数调用都会在栈上分配一个“栈帧”，记录局部变量、返回地址，函数返回时栈帧被销毁。所以我在第10天上课前都会强烈建议：先别着急刷题，花20分钟把栈的数组实现和链表实现各写一遍，你会发现后面所有栈题都能落到这两个模型上。

1.2 队列：两个口各管各的“排队窗口”

队列的模型也很直白：先进先出（FIFO），像食堂打饭排队，先到的人先打到饭。实现上它比栈稍微绕一点。用数组实现队列，如果每次出队都把后面的元素往前挪，那出队就是O(n)，这不可接受，所以常规做法是循环队列：维护队头和队尾两个指针，指针走到数组尾部就回绕到0，用浪费一个空间的方式区分队空和队满。用链表实现就省心很多，队尾入队、队头出队，两个指针分别维护前后即可。

为什么要纠结这些细节？因为代码随想录训练营后面很多题目，尤其是一些模拟题，会要求你“自己设计数据结构”或者“用现有容器模拟另一种容器”，比如本题的232和225。你如果不知道栈和队列各自的实现代价，就不会理解为什么“用栈实现队列”需要用两个栈，而“用队列实现栈”只需要一个队列。底层的实现方式决定了上层操作的代价，这两题就是逼你去体会这件事。

2. 第10天核心题实操：232用栈实现队列、225用队列实现栈

2.1 232题解：两个栈是怎么“接力”出队顺序的

232的要求是只使用栈这个后进先出结构，模拟出队列的先进先出效果。我第一眼看到这题的想法很简单：栈是反的，那用两个栈各反一次，不就正过来了吗。这个直觉是对的，但具体到代码有一些细节值得展开。

维护两个栈，一个叫stack_in只负责入队，另一个叫stack_out只负责出队。push的时候直接往stack_in里压，这点无脑做就行。难点在pop：如果stack_out非空，直接从stack_out弹出栈顶；如果stack_out为空，就把stack_in里的元素全部弹出来并按顺序压进stack_out。这一步相当于把进来的顺序倒了一次，再从stack_out弹出时，就变成了最先进来的元素。

这里有一个均摊复杂度的概念值得多说一句。如果100个元素入队，前99个都直接push，最后一次pop才触发一次性搬运，看起来最坏一次pop是O(n)，但平均下来每个元素最多被搬进stack_in一次、搬进stack_out一次、弹出一次，总共算下来还是O(1)的均摊复杂度。这个“均摊O(1)”在很多面试里会追问，建议你自己画一个入队、出队交替进行的例子，体会一下为什么不能只看单次操作。

peek的实现，我见过不少人的写法是直接看stack_out的栈顶，不行的话再看stack_in的底部。这样逻辑上也能对，但代码分支很多，容易漏情况。我更推荐复用pop，拿到结果之后再塞回stack_out：

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 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: res = self.pop() self.stack_out.append(res) return res def empty(self) -> bool: return not self.stack_in and not self.stack_out

peek复用pop是很多参考答案的写法，它牺牲了一次多出来的append和pop，换来了逻辑的统一，我建议新手先按这种方式写，理解了之后再去优化分支判断。

2.2 225题解：一个队列也能实现栈？关键在“转圈”

用队列实现栈看起来是和232正好反过来，但解法比232更反直觉：其实只需要一个队列。核心思路是制造一些“无效操作”，把顺序扭过来。

如果用两个队列，操作方式是这样的：push时先放入queue2，再把queue1里的元素全部倒入queue2，然后交换queue1和queue2的名字。这样queue1里的元素始终保持“最后入队的在前面”。如果用一个队列，做法更简单：每次push之后，把队列里前面的n-1个元素依次出队再重新入队，这样最后一个入队的元素就绕到了队头，也就是“栈顶”。

我放一个单队列版本的Python代码：

from collections import deque class MyStack: def __init__(self): self.queue = deque() def push(self, x: int) -> None: self.queue.append(x) for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) def pop(self) -> int: return self.queue.popleft() def top(self) -> int: return self.queue[0] def empty(self) -> bool: return not self.queue

这个实现里push的成本是O(n)，因为每入队一个元素，都要把前面所有元素往后挪一个位置。有人可能会想，能不能让pop变成O(n)、push保持O(1)？当然可以，那就是在pop的时候把除了队尾元素之外的元素全部搬到另一个队列里。两种方案各有取舍，刷题时我建议你各写一遍，感受一下“操作发生在入口还是出口”对复杂度分布的影响。

2.3 容器选择：deque还是list，Stack还是ArrayDeque

写代码时语言选择也很影响手感。Python里很多人习惯用list当栈，append和pop都是O(1)，没问题；但当队列用就会出问题，因为list的pop(0)是O(n)。所以队列一定要用collections.deque，它的popleft才是O(1)。C++里std::queue默认底层是deque，std::stack默认也是deque，如果你只是刷题，直接用std::stack和std::queue就行；Java则推荐用LinkedList实现队列、ArrayDeque实现栈，不要去用Stack类。

这里插入一个工程上的联想：很多框架里的“线程池阻塞队列”就是队列模型，生产者和消费者之间靠一个队列解耦；而你写的每一个递归函数，背后都是函数栈帧的创建与销毁。刷题时学到的“进出顺序”约束，到了工程里就是消息队列的顺序保证、调用栈的回溯路径，抽象模型一模一样。不过第10天阶段先别贪多，抓住两种模型的操作特性就好。

3. 栈怎么处理配对问题：20有效的括号与1047删除相邻重复项

3.1 20题解：括号匹配就是“最近的左括号必须对应最近的右括号”

有效的括号这题，本质上考察的是：遇见一个右括号时，它要和“最近的未匹配左括号”配对。这个“最近”两个字，天然就是栈的适用场景。维护一个栈，遇到左括号就压栈，遇到右括号就弹出栈顶并检查是不是匹配的类型，不匹配或者栈为空就返回false。

我在训练营里见过不少同学一上来就写四五个if判断左括号和右括号的计数，这种思路在只有一种括号时还行，有三种括号时就会出错，因为“数量对得上”不代表“位置对得上”。用栈的话，三种括号统一处理起来非常干净：

class Solution: def isValid(self, 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

这里有两个细节值得记一下。第一个是提前剪枝：字符串长度如果是奇数，直接返回False，不用再做任何入栈操作；第二个是mapping的写法，用右括号当key，遇到右括号时去查它应该配对的左括号，比用左括号当key分支更少。我看过很多代码在遇到右括号时用elif判断三种情况，那样可读性和性能都不如一个字典来的干净。

3.2 1047题解：把栈当作“临时缓冲区”来消除相邻重复

1047和20共用同一个核心思想：当前字符和栈顶相等，就说明出现了相邻重复，栈顶弹出；不相等就把当前字符压入。最后栈里剩下的字符按顺序拼接就是答案。代码非常短：

class Solution: def removeDuplicates(self, s: str) -> str: stack = [] for ch in s: if stack and stack[-1] == ch: stack.pop() else: stack.append(ch) return "".join(stack)

这里有一个很容易被忽略的坑：返回结果时，栈底的元素应该是结果字符串的前缀，所以直接join栈的内容就行，不需要反转。有些习惯从栈顶往外拼的人会不小心写成先拼栈顶再反转，反而多此一举。

这两道题放在第10天，我觉得最大的价值不是学会这两道题本身，而是建立起“栈能处理相邻相关性问题”的直觉。你可能想不到，后续很多看似高阶的题目，比如单调栈里的接雨水、柱状图中最大的矩形，底层的操作逻辑都还是“遇到破坏单调性的元素，就从栈里弹出一些元素，并计算结果”。所以说第10天这几道题真的很像母题，值得亲手实现不止一遍。

3.3 配对与消除题的常见翻车点

这一章我最常看到的问题有三个。第一个是20题里忘了检查栈是否为空，例如输入“())”，处理完两个括号后栈是空的，最后的return不写not stack就会直接漏掉“左括号冗余”这一种情况。第二个是1047题返回结果时反转方向搞错，前面说了，直接用join即可，不要额外反转。第三个是忽略字符串长度的奇偶剪枝，这个虽然不影响正确性，但在循环里多做很多没意义的入栈操作，养成先做边界判断的习惯没坏处。

我自己的建议是，这两道题写完以后，用最暴力的方式各测十组用例，包括空字符串、全重复、左右交替重复、只含一种括号等情况，比只提交一次通过更有价值。测试的过程就是在帮你把栈的操作顺序内化成直觉。

4. 从训练营第10天向外看：栈和队列的工程投影

4.1 逆波兰表达式：150题里的操作数顺序陷阱

严格来说150逆波兰表达式求值有的版本会放在第10天前后，它也是栈的经典应用。逆波兰表达式的意思是运算符跟在两个操作数后面，计算时遇到数字就压栈，遇到运算符就弹出两个数字计算完再压回去。代码逻辑非常短，但有一个非常隐蔽的坑：弹栈时先出来的是右操作数，后出来的是左操作数。

举个例子，表达式“3 - 4”写成逆波兰是“3 4 -”，先弹出4，再弹出3，如果写作a + b或者a - b时把顺序搞反，减法会得到1而不是-1，除法也会得到完全不同的结果。另一个坑是Python的整除，如果两个数一正一负，比如-3除以2，期望的数学结果是-1.5，取整后一般是-1，但如果用a // b，在Python里结果是-2，因为它向下取整。正确写法是int(a / b)，这是我在实际提交里踩过最多次的坑，建议你直接背下来。

4.2 单调栈和单调队列：今天种下的种子

代码随想录训练营的题目单里，栈和队列这一章的后半部分通常会提到239滑动窗口最大值和347前K个高频元素，其中239就是单调队列，而很多读者可能听说过“单调栈揭秘”这个词。单调栈，简单说就是让栈内元素保持单调递增或者单调递减。当新元素破坏单调性时，把不满足条件的栈顶元素弹出并结算，常用于找数组中每个元素左右两边第一个比它大或比它小的位置。

为什么要在第10天里提前提一句？因为很多同学刷到后面接雨水时，不清楚为什么要用栈，其实从1047的经验就能顺过来：栈天然适合处理“相邻元素之间的先后/大小关系”，而单调栈是在这个基础上增加了“淘汰劣质候选”的规则。今天这几道题让你先熟悉栈顶操作，后面理解单调栈时会省很多力。

4.3 从算法题到工程：阻塞队列、消息队列与幂等消费

栈和队列不只是算法题里的主角，也是工程里重复出现的抽象。队列在生产者和消费者之间搭桥，就是消息队列的本质；线程池的阻塞队列选择，本质上是问“当队列满的时候，任务请求该被阻塞还是拒绝”，这是对队列容量和吞吐量的权衡。再比如消息队列重复消费问题，消费者收到两条相同的消息，要去重保证幂等性，这既和队列的顺序语义有关，也和我们今天在1047里用“当前状态对照历史状态”的思路相通。

我不是说刷完第10天就能解决这些工程难题，而是想说，当你把栈和队列的进出顺序、底层实现、复杂度分布搞明白以后，再看这些框架源码时会觉得很多设计并不是天马行空。先把理论基础和代码基本功打牢，模块模型自然会长出来。

5. 实操心得与问题排查：给刷完第10天的你一份速查清单

5.1 常见错误速查表

这张表里的每一个场景我都实际遇到过。尤其是最后一条，我刚开始用Python刷题时一直用list当队列，结果在滑动窗口这类需要频繁出队的题目里频繁超时，换成deque之后一下就过了。语言内置容器的底层特性，在刷题初期就该形成条件反射。

5.2 刷题顺序建议与时间分配

第10天如果按训练营的正常节奏，我建议把时间这样分配：先花20分钟自己画图理解栈和队列的数组/链表实现，再花40分钟左右做232和225两题，做完之后紧接着做20和1047，最后留20分钟把四道题复盘一遍，总结成自己的模板。很多人容易贪快，四道题写完就急着赶进度，其实栈和队列这一章的模板复用性很高，今天总结的比较、入栈、出栈、边界判断，后面单调栈、字符串匹配、表达式解析都能直接套。

复盘的时候我习惯用表格记录每一题的三个信息：核心思路一句话、时间复杂度、我踩的坑。等刷完整个训练营回头翻，会发现很多坑是反复出现的，比如边界检查、顺序颠倒、队列容器的选择。

5.3 一些掏心窝的建议

最后说几句个人体会。栈和队列看着简单，但它可能是整份算法提纲里最容易被“显得会”的一章，因为它代码短、思路直白。但代码短不代表理解浅。我遇到很多人能把232的代码背下来，但你问他为什么需要两个栈，他会说“一个正序一个倒序”，再问他时间复杂度为什么均摊O(1)，他就支支吾吾了。这其实是训练营最想让你突破的地方：不只是把题做出来，而是把每一步操作的本质说出来。

我自己在第10天的经验是，一定要在纸上手动模拟整段入队出队过程。拿232来说，你把数组1、2、3、4按顺序入栈A，再倒到栈B，弹出的顺序是不是正好是1、2、3、4，这个过程用笔画一遍，比看十遍代码都有用。等你把这一层想通了，第10天的四道题也就是同一个道理换着花样考你而已。

刷到这里的你，应该已经把第10天的核心题过了一遍。如果你还觉得有些地方没吃透，我的建议是先别急着刷下一章，拿一个具体的操作序列，比如“入队1、2、3，出队一个，入队4，再出队两个”，在纸上模拟一遍双栈队列的完整变化，你会瞬间明白为什么需要第二个栈。栈和队列的妙处在于它把“顺序”变成了可以被操纵的规则，弄懂这个之后，无论是栈帧的创建与销毁，还是消息队列里那些晦涩的工程问题，你会觉得它们隐隐约约都指向同一种东西。按照自己的节奏把这四道题吃透，后面还有更多有意思的题等你。