1. 别急着写代码先看透“操作受限”这四个字栈和队列这两个数据结构难吗说实话每个学过编程的人都能说出个大概栈是“后进先出”队列是“先进先出”。但真到用的时候问题就来了——为什么函数调用非要栈为什么操作系统的消息队列不叫消息栈为什么同样是线性表数组实现和链表实现写出来的栈性能差距能到几倍甚至十几倍我在一次团队代码评审里见过一个很典型的情况功能全部跑通但用了一个list.pop(0)模拟队列数据量一大接口直接超时。所以这篇不是给你背定义的是想把栈与队列里那些“大家默认你会但你其实没想透”的部分一次讲完。1.1 栈和队列本身也是线性表先回到本质。线性表就是一组数据排成一列每个元素有前驱和后继。数组和链表都是线性表的底层实现方式。栈和队列有什么特殊特殊不在存储方式而在操作规则栈只允许在同一端栈顶插入和删除队列只允许在一端队尾插入、另一端队头删除。所以教科书里把栈和队列叫作“操作受限的线性表”。很多人把这句话当理论背过去了其实它是整个数据结构的核心。正是因为操作被“锁死”使用者在写代码时只需要关心顺序规则不用操心内部数据的排列细节抽象层级一下就拉上去了。你想想如果函数调用可以随便从任意位置存取栈帧那程序没跑两步就全乱套了。栈遵循“后进先出LIFO”队列遵循“先进先出FIFO”。这两个规则不是随便定的它们分别对应两类不同的问题一类需要“撤销最近的操作”一类需要“按到达顺序处理事件”。1.2 限制操作带来的三个实际好处限制操作这件事在工程上至少有三个好处第一便于推理和保证一致性。栈和队列的操作模式固定行为可预期写业务逻辑的时候你不需要担心某个地方被意外修改。好比排队买饭大家按顺序往前走队伍不会乱新来的人永远排在队尾。第二便于复用和组合。因为底层只要实现“从一端放入、从一端取出”这组接口上层就可以构建表达式求值、括号匹配、广度优先搜索、消息队列等大量应用不需要知道底层是数组还是链表。第三便于实现算法的高效性。很多算法的复杂度优势恰恰来自“只用一端操作”。比如单调栈、深度优先搜索的递归改非递归如果数据结构没有这种限制就得额外维护状态代码复杂度成倍上升。1.3 基本操作与时间复杂度速览先列一个表后面每个章节都会围绕这个表展开操作栈队列说明插入push 栈顶enqueue 队尾入栈/入队删除pop 栈顶dequeue 队头出栈/出队查看队头/栈顶peek/topfront不删除只看判空isEmptyisEmpty经常被忽略平均时间复杂度O(1)O(1)数组链表都是空间复杂度O(n)O(n)存储数据本身这里需要注意一点O(1) 说的是“均摊”或“在固定容量场景下”的时间。如果你用 Python 的 list 当栈append和pop确实是 O(1)但如果拿它当队列用pop(0)会把后面所有元素往前搬一次就是 O(n)。这个坑我放到最后一章专门讲这里先记住一个结论数据结构选对代码复杂度直接降一个量级。2. 两种底层实现数组方案的快与链表方案的活很多人觉得栈和队列的实现太简单不值得认真写。但恰恰是这些“简单结构”的实现最能暴露对内存、指针、边界条件的理解程度。我用 Python 做演示因为代码短、可读性强但思路对所有语言通用。2.1 顺序栈用一个游标就能完成的实现数组实现栈的核心是维护一个top指针指向当前栈顶元素。插入元素时top加 1删除时top减 1。下面是带扩容的版本class ArrayStack: def __init__(self, capacity8): self.data [None] * capacity self.capacity capacity self.top -1 # 栈顶元素的索引空栈时为 -1 def push(self, val): if self.top self.capacity - 1: # 栈满扩容 self._resize(self.capacity * 2) self.top 1 self.data[self.top] val def pop(self): if self.isEmpty(): raise IndexError(pop from empty stack) val self.data[self.top] self.data[self.top] None # 帮助 GC 回收引用 self.top - 1 return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty stack) return self.data[self.top] def isEmpty(self): return self.top -1 def _resize(self, new_capacity): old self.data self.data [None] * new_capacity for i in range(self.top 1): self.data[i] old[i] self.capacity new_capacity两个细节值得多说。一是self.data[self.top] None这一行很多教科书代码里没有。它看起来可有可无但在长期运行的程序里如果栈里存的是大对象、大数组不把弹出的引用清掉对象就永远不会被回收内存悄悄涨上去。所谓“内存泄漏”很多就是这么积累出来的。二是top -1而不是top 0这样空栈的判断和pop之前的判断共用一套逻辑少一次比较。2.2 链式栈该还回去的引用一定要还链表实现栈不需要提前分配容量每个元素是一个节点指向下一个节点。入栈就是在链表头插入节点出栈就是移除链表头节点。class LinkedStack: class _Node: __slots__ (value, next) def __init__(self, value, nextNone): self.value value self.next next def __init__(self): self._head None self._size 0 def push(self, val): self._head self._Node(val, self._head) self._size 1 def pop(self): if self.isEmpty(): raise IndexError(pop from empty stack) val self._head.value self._head self._head.next # 让原头节点失去引用 self._size - 1 return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty stack) return self._head.value def isEmpty(self): return self._head is None链式栈的pop只需要让_head指向下一个节点原来那个节点就会被回收同样要注意的是不要先把头节点的next存到临时变量再改那样一步到位反而不容易出错。用__slots__声明节点属性是为了减少每个节点的内存占用节点数量大的时候能省不少。2.3 数组与链表的真实选择逻辑这两个实现哪种更好要看场景。数组栈的优势在内存连续。连续内存在 CPU 层面可以被预取到缓存遍历和存取的速度远高于散落在不同地址的链表节点。如果你要写一个高频入栈、出栈的组件比如函数调用的调度器数组方案通常更快。劣势是要扩容扩容那一次需要把旧数据复制到新数组最坏情况 O(n)但均摊下来依然是 O(1)。链表栈的优势在无需扩容、结构简单每次插入只需分配一块节点内存。劣势是指针占空间而且节点分散缓存不友好在数据量变大后性能反而下降。所以我的建议是默认选数组除非你需要实现“无上限”且“插入删除频繁”的场景才考虑链表。算法题里没有特殊说明数组栈足够。工程里如果容量不可控可以选择动态扩容数组而不是一上来就上链表。队列的数组实现比栈麻烦——它需要两个指针一个指向队头一个指向队尾。如果只用线性数组出队时所有元素得往前移那就 O(n) 了。解决办法就是下一章要讲的循环队列。3. 循环队列的边界条件为什么白白空一格反而最省事我见过不少人手写队列写完一测看起来没问题但把队列填满再全部弹出程序进入死循环或者直接给出错误结果。几乎所有 bug 都出在同一个地方判空和判满的条件不清晰。3.1 不循环会遇到的搬移问题如果用一个普通数组记录队列队头指针head指向第一个元素队尾指针tail指向下一个插入位置。入队时tail 1出队时head 1。问题很明显出队操作让head越来越大数组前面的位置空出来却无法复用。当tail到达数组末尾时即使前面有一大片空位也没有办法继续入队。循环队列的思路是逻辑上把数组头尾相接tail从n-1再往前走一步就回到下标 0。这样空出来的位置就能被重复利用。3.2 判空判满与长度计算的统一套路循环队列最经典的做法是牺牲一个存储单元。tail永远指向下一个入队的位置队列最多只存capacity - 1个元素。class CircularQueue: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.head 0 # 队头元素下标 self.tail 0 # 下一个入队位置 def enqueue(self, val): if self.isFull(): raise OverflowError(queue is full) self.data[self.tail] val self.tail (self.tail 1) % self.capacity def dequeue(self): if self.isEmpty(): raise IndexError(dequeue from empty queue) val self.data[self.head] self.data[self.head] None self.head (self.head 1) % self.capacity return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty queue) return self.data[self.head] def isEmpty(self): return self.head self.tail def isFull(self): return (self.tail 1) % self.capacity self.head def size(self): return (self.tail - self.head self.capacity) % self.capacity这套代码里有几个点必须理解透enqueue里先写数据再移动tail因为tail指向的是“空位”不是当前元素。dequeue里先取数据再移动head因为head指向的就是当前元素。判空用head tail。刚初始化时两者相等出队出到两者又相等时队列一定是空的。判满用(tail 1) % capacity head。因为永远留一个空位所以当tail的下一个位置是head时说明只剩一个空位按约定不能再入队。长度计算(tail - head capacity) % capacity这个公式可能第一次看不直观。举个例子capacity 5head 3tail 1实际元素在下标 3、4、0 三个位置长度是 3。(1 - 3 5) % 5 3正确。如果不加capacity再取模1 - 3 -2直接当长度就会得到负数。3.3 另外一种方言用 size 字段替代空位法空位法虽然经典但让容量打了折扣明明分配了capacity个位置最多只能存capacity - 1个。有人觉得不爽就改用size字段记录当前元素个数。class SizedCircularQueue: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.head 0 self.tail 0 self.size 0 def enqueue(self, val): if self.size self.capacity: raise OverflowError(queue is full) self.data[self.tail] val self.tail (self.tail 1) % self.capacity self.size 1 def dequeue(self): if self.size 0: raise IndexError(dequeue from empty queue) val self.data[self.head] self.data[self.head] None self.head (self.head 1) % self.capacity self.size - 1 return val这样能存满capacity个元素但代价是多维护一个size变量每次插入删除都要同步更新。工程上如果队列绝大多数时间不满空位法的“浪费”其实可以忽略如果需要精确利用容量带size的版本也不错。两种写法都见过关键是别混着用——一会用head tail判空一会用size 0判空逻辑很快就乱了。3.4 队列实现里最容易写错的三个点第一tail指针更新时需要取模。很多人漏掉% capacity入队几次后下标就越界。第二size()公式里的 capacity不能省。第三使用引用类型的元素时出队后一定要把原位置置为None否则大对象滞留内存。这三个问题我都在实际项目里见过排查到最后往往就是一行代码的事。4. 栈和队列在真实系统里的出场频率比你想象的高得多栈和队列不只是刷题用的工具。计算机系统里它们是无处不在的基础设施。这一章从应用场景入手帮你建立直觉什么信号出现时第一反应应该用栈什么信号出现时应该用队列。4.1 函数调用栈每个程序都在隐形使用栈写程序的人未必手动写过栈但每次函数调用都在用系统栈。函数 A 调用函数 BB 调用 C系统需要记住“C 结束后回到 B 的哪一行B 结束后回到 A 的哪一行”。这天然是个后进先出问题最后被调用的函数最先返回。所以 CPU 用栈帧保存局部变量、参数、返回地址一层层压栈返回时一层层弹栈。递归之所以可能栈溢出就是因为每层递归都会压一帧层数太多栈空间不够了。理解了这一点你就知道“递归改迭代”的本质是什么——用自己显式维护的栈替代系统隐式维护的调用栈。举一个实际例子树的深度优先遍历。教科书写递归很简单但工程里如果树很深递归可能溢出。改成非递归核心就是一个栈压入根节点后不断弹出并压入子节点。4.2 表达式求值一个栈把中缀转后缀讲清楚表达式求值是栈的经典应用。直观上人来算3 4 * 2知道先乘后加但程序需要规则明确于是先转成后缀表达式3 4 2 * 然后用一个栈逐项计算碰到数字压栈碰到运算符弹出两个数字算出结果再压回去。中缀转后缀的“调度场算法”同样只用到一个栈遇到数字直接输出遇到运算符如果栈顶运算符优先级不低于当前运算符就弹出栈顶最后把当前运算符压栈。规则不难但能帮你彻底理解栈的“延迟处理”作用——先暂存不急着计算的符号等优先级更高的符号处理完再弹出。4.3 队列在系统侧从任务调度到消息削峰队列的核心语义是“先来先得”天然适合任务排队。操作系统里的进程调度、打印机任务队列、Web 服务器的请求队列本质都是队列。再看消息队列中间件名字里就带“队列”它的价值不只是排队而是削峰填谷请求峰值时生产者猛往队列里塞消息消费者按自己的速度慢慢处理系统不会被打垮。生产者消费者模型也是围绕队列展开的。我经常用食堂打饭来类比厨师是生产者打饭的人是消费者中间那个餐台就是队列。餐台能缓冲食堂就不会因为厨师做得慢导致窗口全堵死。工程里用阻塞队列生产者放不进去就等消费者取不到也等解耦效果极其明显。4.4 DFS 与 BFS两种遍历只是栈和队列的选择题深度优先搜索DFS和广度优先搜索BFS的区别本质就是选择“下一个访问谁”DFS 用栈最近加入的节点优先BFS 用队列最早加入的节点优先。同一个迷宫问题用栈做能一条路走到底再回头用队列做会像水波纹一样一层层往外扩。这个视角对解题特别有启发很多“最短路径”问题用 BFS因为先进先出保证了第一次到达目标时的步数一定最小很多“所有方案”问题用 DFS因为栈能帮我们维护一个完整路径的状态。所以当你拿到一个新问题先想一想这题的搜索顺序应该是什么答案是“按层级扩散”还是“按深度探索”把这个判断做了数据结构选型就完成了一半。5. 从普通容器到解题利器双端队列、单调栈、单调队列理解了栈和队列本身再去看它们的“变体”很多题目的套路就通了。这一章讲三个经常混在一起的概念双端队列、单调栈、单调队列。它们不是全新的数据结构而是基于栈和队列思想改造出来的工具。5.1 双端队列把栈和队列合成一个还能做更多双端队列deque全称 double-ended queue允许在头部和尾部都能插入、删除所以它既可以当栈用也可以当队列用。Python 的collections.deque是工程里最常用的双端队列实现它内部是一系列的固定大小“块”通过指针连接而不是简简单单的链表节点。这样设计的好处有两个头部和尾部插入删除都是 O(1)而且内存是分块连续分配的比纯链表节点省空间、访问缓存也更友好。在很多算法题里“窗口滑动、需要同时从两端淘汰元素”的场景非 deque 不可。最典型的就是下一节的单调队列。5.2 单调栈栈顶存的是“还没找到答案的候选”单调栈就是在压栈过程中保持栈内元素单调递增或递减。单调递减栈有个经典用途找每个元素右边第一个比它大的数。用一个具体例子说数组[2, 1, 3, 4]从左到右遍历维护一个栈底到栈顶递减的栈。规则是当前元素比栈顶大时说明栈顶元素的“下一个更大元素”就是当前元素弹出栈顶并记录答案直到栈空或栈顶大于等于当前元素再把当前元素压进去。整个过程2 入栈栈[2]1 比2小入栈栈[2,1]3 比1大弹出1答案 1 - 33 比2大弹出2答案 2 - 3栈空3 入栈栈[3]4 比3大弹出3答案 3 - 44 入栈所以结果为2 - 31 - 33 - 44 - -1。为什么这样能行因为栈里保存的是“还在等待答案的候选元素”一旦遇到第一个比它们大的数它们的答案就定了。这个过程每个元素最多入栈一次、出栈一次整体 O(n)。def next_greater(nums): n len(nums) ans [-1] * n stack [] for i, x in enumerate(nums): while stack and nums[stack[-1]] x: idx stack.pop() ans[idx] x stack.append(i) return ans单调栈属于“看着简单想通很难”的一类。关键在于理解栈内元素代表的是一组“尚未解决”的候选人。一旦新元素比栈顶大新的元素就是栈顶的答案栈顶的历史使命完成自然退场。5.3 单调队列滑动窗口最大值的一个高性价比解法单调队列用来解决“滑动窗口最大值”这类问题。给你一个数组和一个窗口大小 k窗口每次往右滑一格要求输出每个窗口的最大值。如果每次窗口滑动都重新扫描复杂度 O(nk)。用单调队列可以把每个元素进队出队各一次整体 O(n)。核心思想是队列里只保留可能成为窗口最大值的候选元素并且从队头到队尾单调递减。新元素入队时把队尾所有比它小的元素全部弹出——因为它们永远不可能成为当前或未来窗口的最大值了。同时如果队头元素已经滑出窗口也要从队头弹出。from collections import deque def max_sliding_window(nums, k): q deque() result [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() # 队尾弹出比 x 小的元素 q.append(i) # 当前元素入队 if q[0] i - k: # 队头滑出窗口 q.popleft() if i k - 1: # 窗口形成后开始记录 result.append(nums[q[0]]) return result为什么用双端队列而不用普通队列因为既要容纳“未来可能成为答案”的候选又需要从队尾弹出不合适的元素还要求能从队头淘汰过期元素。这三个操作要同时支持普通队列做不到只有 deque 可以。这类变体的价值在于它们让你意识到数据结构不是死的理解规则后可以在约束内做改造。单调栈和单调队列就是给基础结构加了一个“单调性约束”结果威力翻倍。6. 标准库选型与常见误区排查笔记最后一个章节我挑几个大家在日常编码里真的会踩到的坑来聊。很多坑不是栈和队列本身的问题而是语言标准库的使用姿势问题。6.1 别拿 list 当队列用pop(0) 的代价超出想象Python 的 list 是按连续数组实现的。从头部弹出元素需要把后面所有元素往前挪一位时间复杂度 O(n)。如果队列规模是一万pop(0)一次要挪一万次十万就挪十万次。接口在数据量变大后变慢几乎都是这类“隐藏的 O(n)”引起的。正确做法是用collections.dequefrom collections import deque q deque() q.append(1) # 入队 x q.popleft() # 出队O(1) x q.pop() # 当栈用的出栈O(1)注意 deque 的pop()不带参数默认从尾部弹出想要从头部弹出就用popleft()。很多从 list 转过来的人习惯性写q.pop(0)结果发现 deque 不支持pop(0)——这恰恰是它的设计不提供 O(n) 的接口避免你不小心写出低效代码。6.2 Java 的 Stack 是历史遗留ArrayDeque 才是正解Java 里的java.util.Stack在教科书里经常出现但实际上它是一个历史遗留类继承了Vector所有方法都加了同步锁。这意味着你在单线程场景下用 Stack会白白背上同步开销而且因为继承关系你可以对 Stack 做add(0, elem)这种违背栈语义的操作破坏了栈的“操作受限”特性。现代 Java 推荐的方案是ArrayDequeDequeInteger stack new ArrayDeque(); stack.push(1); // 入栈 int top stack.peek(); int x stack.pop();ArrayDeque 既支持push/pop当栈用也支持addLast/removeFirst当队列用初始容量 16自动扩容没有加锁开销几乎在所有指标上都优于 Stack。如果你看到老代码里还在用 Stack可以建议改成 ArrayDeque但要注意push是从头部插入的和addLast方向不同混用容易搞乱。6.3 几道能快速验证理解的真问题怎么检验自己是不是真懂了我总结了三道题不用写完整代码回答上来就行第一循环队列用空位法时容量为 5head是 3tail是 1队列里有多少个元素答案是 3。如果你第一反应是“这不矛盾吗tail 在 head 后面啊”说明还得多算几遍取模。第二用单调栈找“下一个更大元素”为什么数组里最后一个元素的答案一定是 -1因为后面没有元素能成为它的候选。第三滑动窗口最大值里为什么入队前要把队尾所有比当前元素小的都弹出因为它们不仅不可能是当前窗口的最大值在它们“退出视线”之前窗口的最大值已经被当前元素覆盖了——留着它们只会浪费空间和时间。这三个问题想通了栈和队列那些“看一眼就会、写一次就错”的边界和思想基本就都掌握了。最后再分享一点个人经验别嫌基础结构“太简单”就在编辑器里敲一遍就完事。我建议每过一段时间就手写一次数组栈、循环队列、链表队列再把单调栈和单调队列各写一遍。写的时候留意自己在哪一步迟疑了——迟疑的地方就是理解还没到位的地方。基础结构这东西不贵在多贵在每次重新写都有新的体会。
1. 别急着写代码先看透“操作受限”这四个字栈和队列这两个数据结构难吗说实话每个学过编程的人都能说出个大概栈是“后进先出”队列是“先进先出”。但真到用的时候问题就来了——为什么函数调用非要栈为什么操作系统的消息队列不叫消息栈为什么同样是线性表数组实现和链表实现写出来的栈性能差距能到几倍甚至十几倍我在一次团队代码评审里见过一个很典型的情况功能全部跑通但用了一个list.pop(0)模拟队列数据量一大接口直接超时。所以这篇不是给你背定义的是想把栈与队列里那些“大家默认你会但你其实没想透”的部分一次讲完。1.1 栈和队列本身也是线性表先回到本质。线性表就是一组数据排成一列每个元素有前驱和后继。数组和链表都是线性表的底层实现方式。栈和队列有什么特殊特殊不在存储方式而在操作规则栈只允许在同一端栈顶插入和删除队列只允许在一端队尾插入、另一端队头删除。所以教科书里把栈和队列叫作“操作受限的线性表”。很多人把这句话当理论背过去了其实它是整个数据结构的核心。正是因为操作被“锁死”使用者在写代码时只需要关心顺序规则不用操心内部数据的排列细节抽象层级一下就拉上去了。你想想如果函数调用可以随便从任意位置存取栈帧那程序没跑两步就全乱套了。栈遵循“后进先出LIFO”队列遵循“先进先出FIFO”。这两个规则不是随便定的它们分别对应两类不同的问题一类需要“撤销最近的操作”一类需要“按到达顺序处理事件”。1.2 限制操作带来的三个实际好处限制操作这件事在工程上至少有三个好处第一便于推理和保证一致性。栈和队列的操作模式固定行为可预期写业务逻辑的时候你不需要担心某个地方被意外修改。好比排队买饭大家按顺序往前走队伍不会乱新来的人永远排在队尾。第二便于复用和组合。因为底层只要实现“从一端放入、从一端取出”这组接口上层就可以构建表达式求值、括号匹配、广度优先搜索、消息队列等大量应用不需要知道底层是数组还是链表。第三便于实现算法的高效性。很多算法的复杂度优势恰恰来自“只用一端操作”。比如单调栈、深度优先搜索的递归改非递归如果数据结构没有这种限制就得额外维护状态代码复杂度成倍上升。1.3 基本操作与时间复杂度速览先列一个表后面每个章节都会围绕这个表展开操作栈队列说明插入push 栈顶enqueue 队尾入栈/入队删除pop 栈顶dequeue 队头出栈/出队查看队头/栈顶peek/topfront不删除只看判空isEmptyisEmpty经常被忽略平均时间复杂度O(1)O(1)数组链表都是空间复杂度O(n)O(n)存储数据本身这里需要注意一点O(1) 说的是“均摊”或“在固定容量场景下”的时间。如果你用 Python 的 list 当栈append和pop确实是 O(1)但如果拿它当队列用pop(0)会把后面所有元素往前搬一次就是 O(n)。这个坑我放到最后一章专门讲这里先记住一个结论数据结构选对代码复杂度直接降一个量级。2. 两种底层实现数组方案的快与链表方案的活很多人觉得栈和队列的实现太简单不值得认真写。但恰恰是这些“简单结构”的实现最能暴露对内存、指针、边界条件的理解程度。我用 Python 做演示因为代码短、可读性强但思路对所有语言通用。2.1 顺序栈用一个游标就能完成的实现数组实现栈的核心是维护一个top指针指向当前栈顶元素。插入元素时top加 1删除时top减 1。下面是带扩容的版本class ArrayStack: def __init__(self, capacity8): self.data [None] * capacity self.capacity capacity self.top -1 # 栈顶元素的索引空栈时为 -1 def push(self, val): if self.top self.capacity - 1: # 栈满扩容 self._resize(self.capacity * 2) self.top 1 self.data[self.top] val def pop(self): if self.isEmpty(): raise IndexError(pop from empty stack) val self.data[self.top] self.data[self.top] None # 帮助 GC 回收引用 self.top - 1 return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty stack) return self.data[self.top] def isEmpty(self): return self.top -1 def _resize(self, new_capacity): old self.data self.data [None] * new_capacity for i in range(self.top 1): self.data[i] old[i] self.capacity new_capacity两个细节值得多说。一是self.data[self.top] None这一行很多教科书代码里没有。它看起来可有可无但在长期运行的程序里如果栈里存的是大对象、大数组不把弹出的引用清掉对象就永远不会被回收内存悄悄涨上去。所谓“内存泄漏”很多就是这么积累出来的。二是top -1而不是top 0这样空栈的判断和pop之前的判断共用一套逻辑少一次比较。2.2 链式栈该还回去的引用一定要还链表实现栈不需要提前分配容量每个元素是一个节点指向下一个节点。入栈就是在链表头插入节点出栈就是移除链表头节点。class LinkedStack: class _Node: __slots__ (value, next) def __init__(self, value, nextNone): self.value value self.next next def __init__(self): self._head None self._size 0 def push(self, val): self._head self._Node(val, self._head) self._size 1 def pop(self): if self.isEmpty(): raise IndexError(pop from empty stack) val self._head.value self._head self._head.next # 让原头节点失去引用 self._size - 1 return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty stack) return self._head.value def isEmpty(self): return self._head is None链式栈的pop只需要让_head指向下一个节点原来那个节点就会被回收同样要注意的是不要先把头节点的next存到临时变量再改那样一步到位反而不容易出错。用__slots__声明节点属性是为了减少每个节点的内存占用节点数量大的时候能省不少。2.3 数组与链表的真实选择逻辑这两个实现哪种更好要看场景。数组栈的优势在内存连续。连续内存在 CPU 层面可以被预取到缓存遍历和存取的速度远高于散落在不同地址的链表节点。如果你要写一个高频入栈、出栈的组件比如函数调用的调度器数组方案通常更快。劣势是要扩容扩容那一次需要把旧数据复制到新数组最坏情况 O(n)但均摊下来依然是 O(1)。链表栈的优势在无需扩容、结构简单每次插入只需分配一块节点内存。劣势是指针占空间而且节点分散缓存不友好在数据量变大后性能反而下降。所以我的建议是默认选数组除非你需要实现“无上限”且“插入删除频繁”的场景才考虑链表。算法题里没有特殊说明数组栈足够。工程里如果容量不可控可以选择动态扩容数组而不是一上来就上链表。队列的数组实现比栈麻烦——它需要两个指针一个指向队头一个指向队尾。如果只用线性数组出队时所有元素得往前移那就 O(n) 了。解决办法就是下一章要讲的循环队列。3. 循环队列的边界条件为什么白白空一格反而最省事我见过不少人手写队列写完一测看起来没问题但把队列填满再全部弹出程序进入死循环或者直接给出错误结果。几乎所有 bug 都出在同一个地方判空和判满的条件不清晰。3.1 不循环会遇到的搬移问题如果用一个普通数组记录队列队头指针head指向第一个元素队尾指针tail指向下一个插入位置。入队时tail 1出队时head 1。问题很明显出队操作让head越来越大数组前面的位置空出来却无法复用。当tail到达数组末尾时即使前面有一大片空位也没有办法继续入队。循环队列的思路是逻辑上把数组头尾相接tail从n-1再往前走一步就回到下标 0。这样空出来的位置就能被重复利用。3.2 判空判满与长度计算的统一套路循环队列最经典的做法是牺牲一个存储单元。tail永远指向下一个入队的位置队列最多只存capacity - 1个元素。class CircularQueue: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.head 0 # 队头元素下标 self.tail 0 # 下一个入队位置 def enqueue(self, val): if self.isFull(): raise OverflowError(queue is full) self.data[self.tail] val self.tail (self.tail 1) % self.capacity def dequeue(self): if self.isEmpty(): raise IndexError(dequeue from empty queue) val self.data[self.head] self.data[self.head] None self.head (self.head 1) % self.capacity return val def peek(self): if self.isEmpty(): raise IndexError(peek from empty queue) return self.data[self.head] def isEmpty(self): return self.head self.tail def isFull(self): return (self.tail 1) % self.capacity self.head def size(self): return (self.tail - self.head self.capacity) % self.capacity这套代码里有几个点必须理解透enqueue里先写数据再移动tail因为tail指向的是“空位”不是当前元素。dequeue里先取数据再移动head因为head指向的就是当前元素。判空用head tail。刚初始化时两者相等出队出到两者又相等时队列一定是空的。判满用(tail 1) % capacity head。因为永远留一个空位所以当tail的下一个位置是head时说明只剩一个空位按约定不能再入队。长度计算(tail - head capacity) % capacity这个公式可能第一次看不直观。举个例子capacity 5head 3tail 1实际元素在下标 3、4、0 三个位置长度是 3。(1 - 3 5) % 5 3正确。如果不加capacity再取模1 - 3 -2直接当长度就会得到负数。3.3 另外一种方言用 size 字段替代空位法空位法虽然经典但让容量打了折扣明明分配了capacity个位置最多只能存capacity - 1个。有人觉得不爽就改用size字段记录当前元素个数。class SizedCircularQueue: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.head 0 self.tail 0 self.size 0 def enqueue(self, val): if self.size self.capacity: raise OverflowError(queue is full) self.data[self.tail] val self.tail (self.tail 1) % self.capacity self.size 1 def dequeue(self): if self.size 0: raise IndexError(dequeue from empty queue) val self.data[self.head] self.data[self.head] None self.head (self.head 1) % self.capacity self.size - 1 return val这样能存满capacity个元素但代价是多维护一个size变量每次插入删除都要同步更新。工程上如果队列绝大多数时间不满空位法的“浪费”其实可以忽略如果需要精确利用容量带size的版本也不错。两种写法都见过关键是别混着用——一会用head tail判空一会用size 0判空逻辑很快就乱了。3.4 队列实现里最容易写错的三个点第一tail指针更新时需要取模。很多人漏掉% capacity入队几次后下标就越界。第二size()公式里的 capacity不能省。第三使用引用类型的元素时出队后一定要把原位置置为None否则大对象滞留内存。这三个问题我都在实际项目里见过排查到最后往往就是一行代码的事。4. 栈和队列在真实系统里的出场频率比你想象的高得多栈和队列不只是刷题用的工具。计算机系统里它们是无处不在的基础设施。这一章从应用场景入手帮你建立直觉什么信号出现时第一反应应该用栈什么信号出现时应该用队列。4.1 函数调用栈每个程序都在隐形使用栈写程序的人未必手动写过栈但每次函数调用都在用系统栈。函数 A 调用函数 BB 调用 C系统需要记住“C 结束后回到 B 的哪一行B 结束后回到 A 的哪一行”。这天然是个后进先出问题最后被调用的函数最先返回。所以 CPU 用栈帧保存局部变量、参数、返回地址一层层压栈返回时一层层弹栈。递归之所以可能栈溢出就是因为每层递归都会压一帧层数太多栈空间不够了。理解了这一点你就知道“递归改迭代”的本质是什么——用自己显式维护的栈替代系统隐式维护的调用栈。举一个实际例子树的深度优先遍历。教科书写递归很简单但工程里如果树很深递归可能溢出。改成非递归核心就是一个栈压入根节点后不断弹出并压入子节点。4.2 表达式求值一个栈把中缀转后缀讲清楚表达式求值是栈的经典应用。直观上人来算3 4 * 2知道先乘后加但程序需要规则明确于是先转成后缀表达式3 4 2 * 然后用一个栈逐项计算碰到数字压栈碰到运算符弹出两个数字算出结果再压回去。中缀转后缀的“调度场算法”同样只用到一个栈遇到数字直接输出遇到运算符如果栈顶运算符优先级不低于当前运算符就弹出栈顶最后把当前运算符压栈。规则不难但能帮你彻底理解栈的“延迟处理”作用——先暂存不急着计算的符号等优先级更高的符号处理完再弹出。4.3 队列在系统侧从任务调度到消息削峰队列的核心语义是“先来先得”天然适合任务排队。操作系统里的进程调度、打印机任务队列、Web 服务器的请求队列本质都是队列。再看消息队列中间件名字里就带“队列”它的价值不只是排队而是削峰填谷请求峰值时生产者猛往队列里塞消息消费者按自己的速度慢慢处理系统不会被打垮。生产者消费者模型也是围绕队列展开的。我经常用食堂打饭来类比厨师是生产者打饭的人是消费者中间那个餐台就是队列。餐台能缓冲食堂就不会因为厨师做得慢导致窗口全堵死。工程里用阻塞队列生产者放不进去就等消费者取不到也等解耦效果极其明显。4.4 DFS 与 BFS两种遍历只是栈和队列的选择题深度优先搜索DFS和广度优先搜索BFS的区别本质就是选择“下一个访问谁”DFS 用栈最近加入的节点优先BFS 用队列最早加入的节点优先。同一个迷宫问题用栈做能一条路走到底再回头用队列做会像水波纹一样一层层往外扩。这个视角对解题特别有启发很多“最短路径”问题用 BFS因为先进先出保证了第一次到达目标时的步数一定最小很多“所有方案”问题用 DFS因为栈能帮我们维护一个完整路径的状态。所以当你拿到一个新问题先想一想这题的搜索顺序应该是什么答案是“按层级扩散”还是“按深度探索”把这个判断做了数据结构选型就完成了一半。5. 从普通容器到解题利器双端队列、单调栈、单调队列理解了栈和队列本身再去看它们的“变体”很多题目的套路就通了。这一章讲三个经常混在一起的概念双端队列、单调栈、单调队列。它们不是全新的数据结构而是基于栈和队列思想改造出来的工具。5.1 双端队列把栈和队列合成一个还能做更多双端队列deque全称 double-ended queue允许在头部和尾部都能插入、删除所以它既可以当栈用也可以当队列用。Python 的collections.deque是工程里最常用的双端队列实现它内部是一系列的固定大小“块”通过指针连接而不是简简单单的链表节点。这样设计的好处有两个头部和尾部插入删除都是 O(1)而且内存是分块连续分配的比纯链表节点省空间、访问缓存也更友好。在很多算法题里“窗口滑动、需要同时从两端淘汰元素”的场景非 deque 不可。最典型的就是下一节的单调队列。5.2 单调栈栈顶存的是“还没找到答案的候选”单调栈就是在压栈过程中保持栈内元素单调递增或递减。单调递减栈有个经典用途找每个元素右边第一个比它大的数。用一个具体例子说数组[2, 1, 3, 4]从左到右遍历维护一个栈底到栈顶递减的栈。规则是当前元素比栈顶大时说明栈顶元素的“下一个更大元素”就是当前元素弹出栈顶并记录答案直到栈空或栈顶大于等于当前元素再把当前元素压进去。整个过程2 入栈栈[2]1 比2小入栈栈[2,1]3 比1大弹出1答案 1 - 33 比2大弹出2答案 2 - 3栈空3 入栈栈[3]4 比3大弹出3答案 3 - 44 入栈所以结果为2 - 31 - 33 - 44 - -1。为什么这样能行因为栈里保存的是“还在等待答案的候选元素”一旦遇到第一个比它们大的数它们的答案就定了。这个过程每个元素最多入栈一次、出栈一次整体 O(n)。def next_greater(nums): n len(nums) ans [-1] * n stack [] for i, x in enumerate(nums): while stack and nums[stack[-1]] x: idx stack.pop() ans[idx] x stack.append(i) return ans单调栈属于“看着简单想通很难”的一类。关键在于理解栈内元素代表的是一组“尚未解决”的候选人。一旦新元素比栈顶大新的元素就是栈顶的答案栈顶的历史使命完成自然退场。5.3 单调队列滑动窗口最大值的一个高性价比解法单调队列用来解决“滑动窗口最大值”这类问题。给你一个数组和一个窗口大小 k窗口每次往右滑一格要求输出每个窗口的最大值。如果每次窗口滑动都重新扫描复杂度 O(nk)。用单调队列可以把每个元素进队出队各一次整体 O(n)。核心思想是队列里只保留可能成为窗口最大值的候选元素并且从队头到队尾单调递减。新元素入队时把队尾所有比它小的元素全部弹出——因为它们永远不可能成为当前或未来窗口的最大值了。同时如果队头元素已经滑出窗口也要从队头弹出。from collections import deque def max_sliding_window(nums, k): q deque() result [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() # 队尾弹出比 x 小的元素 q.append(i) # 当前元素入队 if q[0] i - k: # 队头滑出窗口 q.popleft() if i k - 1: # 窗口形成后开始记录 result.append(nums[q[0]]) return result为什么用双端队列而不用普通队列因为既要容纳“未来可能成为答案”的候选又需要从队尾弹出不合适的元素还要求能从队头淘汰过期元素。这三个操作要同时支持普通队列做不到只有 deque 可以。这类变体的价值在于它们让你意识到数据结构不是死的理解规则后可以在约束内做改造。单调栈和单调队列就是给基础结构加了一个“单调性约束”结果威力翻倍。6. 标准库选型与常见误区排查笔记最后一个章节我挑几个大家在日常编码里真的会踩到的坑来聊。很多坑不是栈和队列本身的问题而是语言标准库的使用姿势问题。6.1 别拿 list 当队列用pop(0) 的代价超出想象Python 的 list 是按连续数组实现的。从头部弹出元素需要把后面所有元素往前挪一位时间复杂度 O(n)。如果队列规模是一万pop(0)一次要挪一万次十万就挪十万次。接口在数据量变大后变慢几乎都是这类“隐藏的 O(n)”引起的。正确做法是用collections.dequefrom collections import deque q deque() q.append(1) # 入队 x q.popleft() # 出队O(1) x q.pop() # 当栈用的出栈O(1)注意 deque 的pop()不带参数默认从尾部弹出想要从头部弹出就用popleft()。很多从 list 转过来的人习惯性写q.pop(0)结果发现 deque 不支持pop(0)——这恰恰是它的设计不提供 O(n) 的接口避免你不小心写出低效代码。6.2 Java 的 Stack 是历史遗留ArrayDeque 才是正解Java 里的java.util.Stack在教科书里经常出现但实际上它是一个历史遗留类继承了Vector所有方法都加了同步锁。这意味着你在单线程场景下用 Stack会白白背上同步开销而且因为继承关系你可以对 Stack 做add(0, elem)这种违背栈语义的操作破坏了栈的“操作受限”特性。现代 Java 推荐的方案是ArrayDequeDequeInteger stack new ArrayDeque(); stack.push(1); // 入栈 int top stack.peek(); int x stack.pop();ArrayDeque 既支持push/pop当栈用也支持addLast/removeFirst当队列用初始容量 16自动扩容没有加锁开销几乎在所有指标上都优于 Stack。如果你看到老代码里还在用 Stack可以建议改成 ArrayDeque但要注意push是从头部插入的和addLast方向不同混用容易搞乱。6.3 几道能快速验证理解的真问题怎么检验自己是不是真懂了我总结了三道题不用写完整代码回答上来就行第一循环队列用空位法时容量为 5head是 3tail是 1队列里有多少个元素答案是 3。如果你第一反应是“这不矛盾吗tail 在 head 后面啊”说明还得多算几遍取模。第二用单调栈找“下一个更大元素”为什么数组里最后一个元素的答案一定是 -1因为后面没有元素能成为它的候选。第三滑动窗口最大值里为什么入队前要把队尾所有比当前元素小的都弹出因为它们不仅不可能是当前窗口的最大值在它们“退出视线”之前窗口的最大值已经被当前元素覆盖了——留着它们只会浪费空间和时间。这三个问题想通了栈和队列那些“看一眼就会、写一次就错”的边界和思想基本就都掌握了。最后再分享一点个人经验别嫌基础结构“太简单”就在编辑器里敲一遍就完事。我建议每过一段时间就手写一次数组栈、循环队列、链表队列再把单调栈和单调队列各写一遍。写的时候留意自己在哪一步迟疑了——迟疑的地方就是理解还没到位的地方。基础结构这东西不贵在多贵在每次重新写都有新的体会。
