1. 先搞清楚栈和队列到底在解决什么问题1.1 用生活场景理解两种排队方式写算法题的人十有八九都翻车过这么一次第一次看到用栈实现队列的题脑子里全是这不就是用List倒腾两下吗的错觉。但实际上栈和队列是两种截然不同的数据组织方式它们的核心区别不是用什么容器装数据而是数据的进出顺序。栈是后进先出LIFO你可以把它想象成一摞盘子——你总是先拿最上面那个新放上去的想拿底下那个得先把上面所有的都端走。队列是先进先出FIFO就像食堂打饭的排队队伍先来的先打到饭后来的排后面谁也不许插队。这两种顺序听起来很简单但所有进阶的数据结构、算法题、甚至系统设计里的消息队列底层都逃不开这两种顺序。我见过不少初学者一上来就刷动态规划结果连回文串判断用双端队列这种基础应用都卡壳回头发现是栈和队列的底子没打牢。训练营放在第10天讲栈和队列正好卡在这个时间点你已经有了数组、链表的基础可以开始接触带约束的数据结构了。1.2 栈和队列的异同对比先别急着写代码把两者的特性用表格列清楚后面所有题目都从这张表出发特性栈Stack队列Queue数据进出顺序后进先出 LIFO先进先出 FIFO主要操作push入栈、pop出栈、peek看栈顶enqueue入队、dequeue出队、front看队头操作位置只在栈顶操作队尾入、队头出现实类比叠盘子、浏览器后退、函数调用栈排队打饭、打印机任务队列、消息队列常考题型括号匹配、表达式求值、单调栈循环队列、双端队列、用栈实现队列从这张表能看出栈和队列唯一的差别就是操作位置和顺序但就是这一点差别决定了它们被用在完全不同的场景里。栈擅长处理需要回退、嵌套的问题队列擅长处理需要按顺序公平消费的问题。你可能会问为什么不能直接用数组当然能用但数组是无约束的你想从哪里读就从哪里读写算法题时约束反而是一种简化——你不用再考虑从中间插入之类的操作所有逻辑都被压缩到一个端点上。这就是为什么栈和队列被称为受限的线性表限制越多思维越清晰。2. 手写实现把底层逻辑吃透2.1 用Python实现一个栈含动态扩容思考刷题时直接用语言内置的list当然方便但训练营里我一直建议至少手写一遍底层。原因很简单面试时会问Python的list底层是怎么扩容的你不会写数组栈连这个问题都接不住。再者手写一遍能让你真正理解栈顶指针是怎么移动的。用Python实现一个纯数组栈class ArrayStack: def __init__(self, capacity8): self.capacity capacity self.data [None] * capacity self.top -1 # 栈顶指针-1表示空栈 def push(self, value): if self.top 1 self.capacity: # 动态扩容倍增策略 self._resize(self.capacity * 2) self.top 1 self.data[self.top] value def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) value self.data[self.top] self.data[self.top] None # 释放引用 self.top - 1 return value def peek(self): if self.is_empty(): raise IndexError(peek from empty stack) return self.data[self.top] def is_empty(self): return self.top -1 def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self.top 1): new_data[i] self.data[i] self.data new_data self.capacity new_capacity这里有几个细节新手很容易漏top指针初始化为什么是-1因为空栈时栈顶位置是数组下标前面的一个虚拟位置这样push第一个元素时top从-1变成0刚好落在下标0上。如果你把top初始化为0那得额外用一个size变量区分空栈和栈顶位置反而绕弯子。扩容为什么用倍增而不是每次加1倍增的时间复杂度均摊下来是O(1)而每次加1是O(n)。Python的list底层用的就是类似策略实际上它会先申请8个槽位然后按比例扩容这是工程界的常青树方案。pop时为什么要把原位置置为NonePython有垃圾回收机制但如果你存的是一个大型对象不置None的话引用还挂着这个对象不会被回收。大流量服务里这就是内存泄漏的隐患。刷题时可以不在意但写工程代码必须养成习惯。2.2 用Python实现一个队列解决假溢出问题队列的实现比栈多一个坑点——数组队列存在假溢出问题。先看一个错误的示范如果你用两个指针front和rear每次入队rear加1出队front加1那么当rear到达数组末尾时即便数组前面空着一大片空间你也没法再入队了。这就是假溢出。一个标准的数组队列实现class ArrayQueue: def __init__(self, capacity8): self.capacity capacity self.data [None] * capacity self.front 0 # 队头下标 self.rear 0 # 队尾下标指向下一个入队的位置 self.size 0 # 当前元素个数 def enqueue(self, value): if self.size self.capacity: self._resize(self.capacity * 2) self.data[self.rear] value self.rear (self.rear 1) % self.capacity # 循环移动 self.size 1 def dequeue(self): if self.is_empty(): raise IndexError(dequeue from empty queue) value self.data[self.front] self.data[self.front] None self.front (self.front 1) % self.capacity self.size - 1 return value def peek_front(self): if self.is_empty(): raise IndexError(peek from empty queue) return self.data[self.front] def is_empty(self): return self.size 0 def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self.size): new_data[i] self.data[(self.front i) % self.capacity] self.data new_data self.front 0 self.rear self.size self.capacity new_capacity这段代码里最关键的是两处取模运算rear (rear 1) % capacity和front (front 1) % capacity。取模让指针能够绕回数组开头形成一个逻辑上的环这就是循环队列的核心思想。如果你不用循环而选择在出队时把所有元素往前挪一位那时间复杂度会从O(1)变成O(n)刷题时可以AC但面试会挂。再注意size这个变量。有人会问为什么不用front rear来判断空和满因为空和满时front都等于rear区分不开。解决方案有两个一是用size计数代码直观一些二是牺牲一个存储单元让(rear 1) % capacity front表示满。我推荐用size逻辑清晰不容易出错刷题时效率差别也不大。2.3 两种实现必须注意的边界条件把栈和队列实现完你可能会觉得不过如此但边界条件才是真正杀死人的地方。我整理了训练营里学员踩过的坑空栈pop/peek必须先判断isEmpty否则下标越界或返回None。有些语言里这会直接抛异常或崩掉。扩容后数据搬迁栈扩容时按top顺序搬队列扩容时要注意从front开始搬不能从0开始。很多人在写队列resize时直接把原数组整体拷贝过来结果元素的相对顺序全乱了。队列无效化旧元素出队后把原位置置None。这不仅仅是防止内存泄漏更重要的是避免调试时看到一堆脏数据影响判断。Python刷题时可以偷懒用list模拟栈——因为list的append和pop天然就在末尾操作复杂度是O(1)。但队列用list的pop(0)就不行因为pop(0)会触发O(n)的元素迁移刷题时数据量小可能没感觉但你会养成非常坏的习惯不看复杂度只求过case。训练营的要求是每道题至少分析清楚时间复杂度和空间复杂度再动手哪怕代码看起来多一行也要明白这一行是干什么的。3. 经典算法题拆解栈和队列的三大必刷题型3.1 有效的括号栈最经典的匹配问题有效括号这道题LeetCode 20基本是算法面试的入门标配但每年还是有一大批人在上面翻车。题目要求判断一个只包含()[]{}的字符串是否有效规则有三种左括号必须用同类型右括号闭合、闭合顺序要正确、嵌套要正确。核心思路很简单遇到左括号就入栈遇到右括号就弹出栈顶看是否匹配。但如果弹出前没检查栈是否为空遇到}这种单独出现的右括号就会报错。def is_valid(s: str) - bool: stack [] mapping {): (, ]: [, }: {} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping: if not stack or stack[-1] ! mapping[char]: return False stack.pop() else: return False return not stack这个版本用了一个反向映射表用右括号反查左括号比用if char ) and stack[-1] (这种多分支写法清爽得多。要注意最后返回的是not stack因为如果栈里还有没匹配完的左括号说明括号没闭合完。实际刷这道题时常见的错误排序是忘了处理}(这种情况——遇到右括号时栈是空的没有判断就pop。用正向映射表{(: )}然后去比较当前char是否等于栈顶的映射值逻辑绕来绕去容易漏case。只验证了数量没验证顺序。这道题还有一种扩展考法不只是三种括号而是出现自定义的符号映射关系。比如把{}替换成 和《 》思路完全一样但需要你真正理解映射表的用法而不是背答案。3.2 用两个栈实现队列经典双栈切换这道题LeetCode 232看起来是基础题实际上把栈和队列的性质玩得很透彻。思路是维护两个栈in_stack专门用来入队out_stack专门用来出队。入队时直接压入in_stack。出队时如果out_stack是空的就把in_stack的所有元素逐个弹出并压入out_stack然后弹出out_stack栈顶。为什么能这样因为栈的反序恰好是队列的顺序——in_stack里栈顶是最后进来的元素但队列需要最先出去的恰恰是最先进来的所以倒一次手后栈顶就变成了最先进来的元素。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x: int) - None: self.in_stack.append(x) def pop(self) - int: self._transfer() return self.out_stack.pop() def peek(self) - int: self._transfer() return self.out_stack[-1] def empty(self) - bool: return not self.in_stack and not self.out_stack def _transfer(self): # 注意只有当 out_stack 为空时才搬运 if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())很多初学者在这里犯的一个关键错误是每次pop前都想搬运一次。如果这么干时间复杂度会变成O(n)而且会破坏队列顺序。比如先push 1、2、3然后pop两次每次都搬运第一次out_stack是[3,2,1]pop出1第二次再搬运时in_stack已经空了一来一回没问题。但万一中途又push 4再pop时如果out_stack还有元素却优先把4搬到out_stack里顺序就乱了。正确逻辑是out_stack有货就先出货没货才从in_stack搬运全部。这样均摊下来每个元素最多被搬两次时间复杂度均摊O(1)。面试时如果被问为什么摊还复杂度是O(1)就回答每个元素入栈一次、出栈一次、进out_stack一次、出out_stack一次总共4次常数操作。这道题还有个变形用栈实现双端队列Deque思路类似但需要额外处理两端操作。如果你能稳定切出这道题说明栈和队列的相互转化已经通了。3.3 用两个队列实现栈单队列循环法既然有用两个栈实现队列就一定有用两个队列实现栈LeetCode 225。这道题解法比上一题烧脑一点因为队列天然是FIFO要实现LIFO必须玩一个最后一招。我用的是一个更省空间的变体只用一个队列就能实现栈。核心操作是每次push新元素后把队列里前面的所有元素依次取出放到队尾这样新元素就挪到了队头pop时直接弹出队头即可。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) # 把前面的n-1个元素依次挪到队尾 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.qpush操作里的循环是关键每次入队新元素后把所有其他元素依次旋转到新元素后面相当于每次push都是O(n)的代价。这题的均摊复杂度没必要像上一题一样好因为每次push就是O(n)pop是O(1)属于写操作贵、读操作便宜的模型。官方题解里还有一种双队列做法push时先把新元素放到q2然后清空q1全部搬到q2之后交换两个队列的指针逻辑上等同于上述旋转。但我个人觉得单队列的旋转思想更直观代码也更短。面试时如果你能把这个for循环的原理讲清楚效果比背双队列代码好得多。4. 实际应用场景栈和队列是怎么进工程里的4.1 栈从函数调用栈到撤销功能再到单调栈很多刷题的人有一个误区觉得栈和队列只是考试用的抽象概念和真实项目没关系。实际上你写的每一行代码都在用栈——函数调用栈Call Stack就是栈的典型应用。函数A调用函数B系统会把A的现场信息压栈B返回后再弹栈恢复A的执行。你在调试器里看到的调用堆栈本质就是一层层栈帧。热词里提到的函数栈帧的创建与销毁就是这个过程caller的局部变量、返回地址、参数按顺序压栈被调函数结束后弹栈恢复现场。理解了这一点你再看递归崩溃时的Stack Overflow才会真正明白——栈的空间是有限的无限递归必然爆栈。另一个非常贴近生活的应用是编辑器的撤销功能Undo。每次操作压入栈撤销时弹出撤销再撤销就是多重撤销。如果你想实现支持任意撤销深度那就是一个永远不弹的栈但如果为了限制内存就得用固定容量并覆盖旧元素——这又引出了循环队列的思想。热词里的单调栈揭秘很有意思它是栈在算法竞赛中特别高频的一个进阶话题。单调栈的核心是维护一个栈让栈内元素保持单调递增或递减常用于解决下一个更大元素问题——比如热词里的算法 找下一个身高更高的小朋友。遇到这种题暴力解法是O(n^2)单调栈能把复杂度降到O(n)。我建议你把每日温度这道题刷一遍它会让你意识到栈不只能做括号匹配还能做更高效的查找。4.2 队列从消息队列到线程池的阻塞队列队列在工程里的应用比栈更广泛因为现实世界中大量的任务是先到先服务的。最常见的例子是消息队列Message Queue生产者把消息放到队列尾部消费者从队列头部取走消息。热词里专门有消息队列重复消费问题——这正是队列的语义和应用重点消息一旦被消费并确认ack就应该从队列中移除但如果没有正确处理ack比如消费者处理完但ack丢失消息就会重新入队被再次消费导致重复。这个问题在分布式系统里尤其突出实际上是通过分布式幂等来解决的——即使消费者收到重复消息也要保证处理结果一致。线程池里的等待队列也是队列任务提交时如果线程池满了新的任务会放入等待队列空闲线程依次取走执行。热词里提到的线程池的阻塞队列选择——Java里LinkedBlockingQueue和ArrayBlockingQueue的区别本质上就是链表队列和数组队列在并发场景下的取舍。数组队列预分配内存读写效率更高但容量固定链表队列按需分配节点容量可以设很大但每个节点有额外内存开销。我自己的经验是默认选LinkedBlockingQueue通常更稳妥因为它的锁粒度更细put和take各一把锁尤其在读多写多的场景下并发度更高。还有热词里的python队列queue不堵塞——Python的queue.Queue可以直接设置timeout参数超过指定时间就抛出异常或返回标志这在写爬虫限速、任务分发时特别好用。另外Python里还有一个很容易混淆的东西qsize()法和task_done()。qsize()并不是一个线程安全的准确值只适合做粗略判断真正判断队列状态应该用empty()和full()或者直接依赖阻塞机制。4.3 常见错误与排查技巧实录把训练营里学员在栈和队列题目上遇到的典型问题汇总一下有则改之无则加勉问题场景直接原因解决方案pop from empty stack栈题中连续出栈没先检查空栈每次pop前判断is_empty()队列顺序错乱用两个栈实现队列out_stack非空时仍然搬运新元素只在out_stack为空时搬运死循环队列入队判断用front rear判断满且没含size用size计数或留一个空位只过一半case括号匹配没考虑空栈pop匹配右括号前检查not stack栈溢出递归思想误用到栈题里用递归代替显式栈且递归过深先用显式栈模拟避免递归爆栈假溢出数组队列连续入队出队rear到达末尾后无法复用前段空间改成循环队列取模其中死循环这个问题调试起来最头痛。有位学员实现队列时用了while not queue.is_empty()但is_empty判断的是self.front self.rear结果入队一个元素后front等于rear空状态循环条件立刻不满足入队操作等于白做。这种问题不看打印日志根本查不出来因为逻辑看起来完全正确。我Debug了几年普遍的经验是栈和队列的边界错误靠眼睛看是不行的必须人为构造边界case来验证。比如栈的题目一定测空栈、一个元素pop后回到空、连续push到扩容点如第8个元素、扩容后pop到空再push。队列的题目一定测入队一个出队一个再入队触发循环绕回、队列刚刚满时再入队触发扩容、扩容后数据顺序是否正确。把这些case记下来刷任何一道栈或队列题都能快速自检。5. 训练营Day10的实操复盘与个人心得5.1 本节的完整学习路径总结讲完理论、实现、刷题和工程应用还是要把训练营Day10的整体学习路径理一遍。我在这天的安排是画图理解概念20分钟在白板上画出栈的初始化、push、pop三个状态图和队列的初始化、入队、出队三个状态图一定要画到rear指针绕回数组开头这一步否则循环队列的取模永远理解不透。手写两种结构的代码30分钟必须基于数组实现而不是直接用list偷懒。重点体会栈的top指针和队列的front/rear指针的区别以及扩容时数据搬迁的差异。刷题验证40分钟LeetCode 20有效括号、LeetCode 232用栈实现队列、LeetCode 225用队列实现栈。这三道题做完再把它们的变形题看一眼比如LeetCode 1047删除字符串中的所有相邻重复项用栈思路可以直接秒杀。总结错误场景10分钟把自己在做题中写错的case记录到错题本里。我强烈建议用表格的形式记录错误代码、正确代码、失败case、原因分析。这样一周后回看时一眼就能定位自己的短板。这套流程不需要额外资料就靠白板、编辑器、LeetCode三个工具。第一次基础的同学对栈和队列有惧怕感但按照这个路径走下来基本两小时内就能达到中等刷题水平。5.2 想进一步深入该往哪些方向扩展Day10只是part01栈和队列这个主题还有很大空间后续训练营会继续展开的内容包括单调栈解决下一个更大元素每日温度接雨水LeetCode 739/42。这类题训练的是什么时候该弹栈的判断力是栈的进阶应用。双端队列Deque一句话理解一个deque使用场景——滑动窗口最大值LeetCode 239。它的巧妙之处在于不仅两端可以进出还能在维护窗口时淘汰过期元素。优先队列堆热词里堆和栈经常被混在一起提。堆是一种特殊的树形结构TopK问题、合并K个有序链表全靠它。堆和栈的区别要单独花时间理解——前者是树后者是线性表。栈与递归的转换任意递归都可以改成非递归的显式栈。理解这个转换对理解深度学习中的反向传播也有帮助——神经网络里的梯度传播本质上是个栈式的回溯过程。如果你能把Day10的栈和队列打牢到后面学树、图、动态规划时你会发现好多结构都依赖这些基础的进出顺序思想。说到底算法不是背题而是理解数据在特定约束下的流动方式。栈和队列就是那两扇最基础的门推开它们后面广阔得很。我个人在带训练营时的切身体会是栈和队列的题看起来简单但极其容易犯错尤其是边界条件。所以Day10这天宁可多花时间把实现代码写明白、边界case测彻底也不要急着一口气刷十道题。基础结构一旦理解错了后面所有题都会跟着错。拿张纸把每次错误的case画出来比刷十道题都管用。