先讲个场景。你在浏览器里一个页面接一个页面地看文章想回上一篇点一下后退就回去了再想回来点前进又回去了。这背后就是一个栈。再看食堂中午排队买饭先来的人先拿到餐盘后面的人只能等着这背后就是一个队列。算法与程序设计课程里很多人第一堂数据结构课就是从这两个最简单的结构开始的——它们不复杂却建立起你对“数据怎么组织、怎么存取”的第一次完整认知。这篇文章是我结合自己学习和实际项目中的使用经验为刚接触算法与程序设计的同学写的一份“栈与队列初体验”记录。我会从生活场景切入把栈和队列的本质讲透然后手把手带你用数组和链表分别实现它们接着讲清楚循环队列里的取模运算到底怎么回事最后用函数调用、浏览器历史、消息队列这些真实场景让你看到学的东西是怎么被用起来的。文章里的代码我会尽量简单还会把初学阶段最容易踩的坑单独列出来方便你对照排查。看完之后你至少能自己写出一份能跑、能讲、能应对常见面试题的栈和队列实现。1. 先搞清楚栈和队列到底在解决什么问题1.1 两种“存取规则”就是两套秩序栈Stack和队列Queue在教科书里被归为“线性表”的两种受限形式。所谓线性表就是数据一个接一个排成一串而“受限”的意思是数组和链表允许你在任意位置插入或删除元素栈和队列却只允许你在特定位置操作。栈只允许在“栈顶”top这一个端口放东西和取东西最后一个放进去的元素最先被取出来英文叫 LIFOLast In, First Out后进先出。想体会这个规则最简单的就是看一摞叠起来的餐盘你总是先把新盘子放在最上面取盘子时也只能先取最上面的那个底下的盘子不会被立刻碰到。队列则正好相反允许两端操作但方向固定新的元素从“队尾”rear进入要取元素只能从“队头”front离开第一个进来的元素第一个出去即 FIFOFirst In, First Out。食堂排队打饭就是教科书级的例子排在队伍最前面的先打到饭后到的人只能排在队尾等着。为什么特意强调这种“受限”因为很多初学者会疑惑数组和链表明明可以做同样的事为什么还要定义栈和队列答案是限制操作范围恰恰是为了更清晰地表达模型。当你只需要“后进先出”或“先进先出”这种单一规则时把接口收敛成 push/pop 或 enqueue/dequeue 几个操作调用者就不用关心内部怎么组织、不需要在任意位置插删出错的概率大幅降低代码的可读性也提升一截。这种“只暴露必要接口隐藏内部实现细节”的思想其实就是抽象数据类型ADT的雏形。往后学到映射、堆、图的时候你会发现这个思维模式始终贯穿。1.2 为什么算法课总把栈和队列放在第一站我自己带过不少初学者发现课程大纲把栈和队列安排在第一梯队是有道理的。原因有三点。第一它们足够简单适合建立信心。你不需要先理解复杂的树形结构或递归思维只要抓住“一端口进出一端口进出”和“一头进另一头出”两条规则就能上手写代码。对刚接触数据结构的人来说这种“我也能实现一个结构”的正反馈非常重要比一上来就啃红黑树不知道友好多少。第二它们是理解其他结构的跳板。树的遍历尤其是深度优先和广度优先背后分别站着一个栈和一个队列图的搜索也同样如此。递归的执行过程其实就是函数调用栈一层层入栈出栈的过程。换句话说栈和队列是很多进阶算法里那个“隐形的关键先生”很多看起来花哨的问题拆到底就是“维护一个栈”或者“维护一个队列”。第三它们天然带着一堆“边界问题”要你处理。容量满了怎么办队列空了还能出队吗循环队列怎么区分满和空这类问题锻炼的是程序员最重要的基本功——边界条件思维。我面试别人的时候经常用一道“用栈实现队列”的题考察的其实并不是代码量而是你有没有把两种结构的入出方向理清楚。能顺手写对说明基本的存取秩序已经内化了。2. 手写一个栈先写数组版再写链表版2.1 数组版栈一个索引就够用先看最直观的数组版。我们用一个连续数组存储数据再用一个整数 top 记录当前栈顶的位置。核心操作就三个push 在栈顶加元素pop 把栈顶元素取走peek 只看顶部不取走。class ArrayStack: def __init__(self, capacity10): self.capacity capacity self.data [None] * capacity self.top -1 # 初始时栈为空 def is_empty(self): return self.top -1 def is_full(self): return self.top self.capacity - 1 def push(self, value): if self.is_full(): raise OverflowError(栈已满无法入栈) self.top 1 self.data[self.top] value def pop(self): if self.is_empty(): raise IndexError(栈为空无法出栈) value self.data[self.top] self.data[self.top] None # 释放引用 self.top - 1 return value def peek(self): if self.is_empty(): raise IndexError(栈为空无法查看栈顶) return self.data[self.top]这里有个细节值得单独说top 初始化成 -1不是 0。为什么因为 -1 这个值巧妙地表达了“当前栈里没有任何元素”当栈里有一个元素时 top 变成 0这个元素就存在 data[0] 里有两个元素时 top 是 1。这样 push 时先自增再赋值pop 时先取值再自减两个操作都不用额外特判边界自然被索引值覆盖。如果你把 top 初始化为 0push 就要“先赋值再自增”pop 要“先自减再取值”写起来别扭稍不留神就越界。这是很多教材默认 -1 的真实原因不是一个随意的约定。数组版的缺点也很明显容量是写死的。push 满员后要么抛异常要么做扩容。如果在工程里做动态扩容常见策略是“当前容量翻倍”整体摊还复杂度仍是 O(1)很多高级语言动态数组就是这么干的。学习阶段建议先写固定容量版本把索引边界想清楚再考虑扩容。2.2 链表版栈用指针代替容量限制数组版的核心问题是容量固定链表版则通过把每个元素装进一个节点node节点之间用指针串起来彻底摆脱容量限制。栈顶就是链表的头节点push 相当于在头部插入pop 相当于删除头节点两个操作都只动一根指针O(1)。用 Python 写链表版class Node: def __init__(self, value): self.value value self.next None class LinkedStack: def __init__(self): self.head None # 栈顶指针 def is_empty(self): return self.head is None def push(self, value): new_node Node(value) new_node.next self.head self.head new_node def pop(self): if self.is_empty(): raise IndexError(栈为空无法出栈) value self.head.value self.head self.head.next return value def peek(self): if self.is_empty(): raise IndexError(栈为空无法查看栈顶) return self.head.value这段代码里最容易写错的是 push 的四行顺序正确顺序是“先让新节点指向旧头再把头指针挪到新节点”。反过来的话旧链表就丢了。我见过不少初学同学先写 self.head new_node再写 new_node.next self.head结果新节点指向了自己形成环调试半天找不出来。记住一个口诀先搭线再动指针。先让新节点的 next 指向当前头然后再更新头指针。链表版没有容量上限上限只取决于内存也不需要预分配空间但每个节点都额外保存一个 next 指针空间开销比数组版大。在极端情况下频繁 new 节点和释放节点还可能带来内存碎片和性能损耗。所以两种实现没有绝对优劣取决于场景。2.3 两种实现的对比与选型对比维度数组版栈链表版栈容量固定或需动态扩容理论无上限随机访问支持data[i] 可取任意元素不支持只能访问栈顶空间效率可能浪费未用槽位每个节点多存一个指针插入删除O(1)数组连续内存更友好O(1)但有节点分配开销适用场景容量可预估、追求性能容量未知、数据波动大选型心得我放在最后说如果是练习题和竞赛数组版几乎总是更顺手如果是设计一个生命周期长、数据量波动大的系统组件链表版或者直接用语言自带库更合理。但学习阶段建议两种都写一遍因为“数组实现锻炼索引思维链表实现锻炼指针思维”这两种思维恰好是数据结构里最核心的两套基本功。3. 队列的三种写法顺序、循环、链式3.1 顺序队列为什么明明有空位却“溢出”了队列用数组实现时需要两个指针front 指向队头rear 指向队尾。入队时 rear 后移并写入出队时 front 后移并取出。听起来很简单但很快会遇到一个经典问题假溢出。假设一个长度为 5 的数组你连续入队 5 个元素rear 走到下标 4。然后出队 3 次front 走到下标 3。这时候数组前三个位置是空着的但 rear 已经在最右边新元素想入队数组说“满了”。可明明有 3 个空格子没人用这就是“假溢出”。如果直接报满空间就被白白浪费了。解决假溢出的第一反应是把所有元素整体往左挪但挪动是 O(n) 的出队一次就要挪一次代价太难看。于是出现了循环队列。3.2 循环队列取模运算和那个“牺牲掉的空位”循环队列的思路是把数组想象成一个环形跑道rear 到达数组末尾时下一步绕回下标 0就好像跑完一圈再从头开始。实现上只需要一个取模运算rear (rear 1) % capacity front (front 1) % capacity关键问题是怎么区分“队空”和“队满”如果只用 front rear 判断空那满的时候 front 也等于 rear两个状态就分不开了。常规解法有三种。第一种牺牲一个存储单元。约定队满条件是 (rear 1) % capacity front也就是说 rear 后面紧挨着的那个槽位不能放数据。这样做代码最简单代价是数组永远有一个格子是空的。第二种在结构体里加一个 size 字段记录当前元素个数。入队 size1出队 size-1判空判满看 size 就行。空间不浪费但多维护一个变量。第三种加一个 flag 标记最后一次操作是入队还是出队。个人不推荐太绕出问题的概率高。我看过很多同学的循环队列代码最常见的问题是判断条件写串。比如用 while 循环遍历队列终止条件写成 front ! rear结果因为满时 front 也等于 rear把满队列当成空队列处理直接跳出不输出任何元素。这类差一错误最好的排查办法是画图。把数组画成一个圈用两个不同颜色的箭头标记 front 和 rear模拟入队出队各几步立刻能看出条件错在哪。class CircularQueue: def __init__(self, capacity5): self.capacity capacity self.data [None] * capacity self.front 0 self.rear 0 # 牺牲一个空位rear 指向下一个要写入的位置 def is_empty(self): return self.front self.rear def is_full(self): return (self.rear 1) % self.capacity self.front def enqueue(self, value): if self.is_full(): raise OverflowError(队列已满) self.data[self.rear] value self.rear (self.rear 1) % self.capacity def dequeue(self): if self.is_empty(): raise IndexError(队列为空) value self.data[self.front] self.data[self.front] None self.front (self.front 1) % self.capacity return value def size(self): return (self.rear - self.front self.capacity) % self.capacity注意 size 的公式(rear - front capacity) % capacity。这个公式很有代表性它说明取模运算在处理“环状下标”问题里的妙处两个指针在环上绕圈差值可能为负数比如 rear 越过末尾回到 0而 front 还在 3加上 capacity 再取模就把差值修正到 0 到 capacity-1 之间。后面学哈希表、环形缓冲区你会反复看到这个套路。3.3 链式队列两个指针都别忘链式队列用链表实现时需要维护两个指针head 指向队头出队端tail 指向队尾入队端。入队时在 tail 后面挂新节点并更新 tail出队时取 head 指向的节点并让 head 后移。这里的坑比栈的链表版更多。第一个坑出队时如果发现 head 指向的节点是最后一个节点那么删除它之后tail 也必须更新为 None。很多初学者只更新 head不更新 tail结果队列空了之后 tail 还指向已经被释放的节点形成“悬空指针”下次再入队时 tail.next new_node 会写到非法地址上程序直接崩溃。第二个坑入队时如果不是第一次入队代码是 tail.next new_node; tail new_node但如果队列本来就是空的head 和 tail 都是 None你就要同时把 head 和 tail 都指向新节点。这个 if/else 分支很容易被漏掉。我习惯把链式队列的入队写成def enqueue(self, value): new_node Node(value) if self.tail is None: # 队列为空 self.head new_node self.tail new_node else: self.tail.next new_node self.tail new_node出队时则先判断空然后保存 value再判断“出队后是否为空队列”来决定要不要把 tail 置 None。判断的条件就是出队之前 head tail说明这个节点是唯一的节点。4. 学完得用起来几个经典应用4.1 函数调用栈你写的每一层递归都靠它每个程序在运行时会维护一个函数调用栈。每次调用一个函数系统会把这次调用的局部变量、返回地址、参数等信息打包成一个栈帧压到调用栈上函数返回时这个栈帧被弹出。嵌套调用就是不断的压栈和弹栈所以递归过深时会报“栈溢出”——不是机器没内存而是这个调用栈被撑满了。理解了栈你就真正理解了递归的代价每一层递归都要额外的栈帧空间递归深度过大时空间开销会直接变成程序的致命伤。举一个可视化例子斐波那契数列的朴素递归 fib(5)调用树里 fib(3) 会被重复计算多次这些重复调用在调用栈里是“先深入再回来”的过程栈帧创建和销毁都很频繁。这也是为什么很多算法课讲递归和动态规划之前会先用栈来铺垫“递归是怎么执行的”。学完栈之后再回头看递归你不会再觉得它是魔法而是一套明确可追踪的压栈弹栈流程。4.2 括号匹配、表达式求值与浏览器栈的经典应用算法题是括号匹配。给你一串包含左右圆括号、方括号、花括号的字符判断是否合法“([])”合法“([)]”不合法。标准解法是遇到左括号就压栈遇到右括号就弹出栈顶并检查类型是否匹配。如果遍历完栈不为空或者遇到右括号时栈是空的都不合法。这个算法代码很短但考察的就是栈“后进先出”的特性——最近的左括号必须最先被右括号闭合。写的时候你还能顺便练到字典映射的用法一举两得。浏览器前进后退是双栈的经典模型用一个后退栈记录访问历史一个前进栈记录“退回去的那些页面”。点击后退时当前页面压入前进栈把后退栈顶弹出来显示点击前进时反过来。做完这个例子你就能理解很多产品的“撤销/重做”功能本质上也是两棵版本的栈。表达式求值也用栈。中缀表达式“3 4 * 2”要计算计算机往往先把它转成后缀表达式“3 4 2 * ”然后从左往右扫描遇到数字就压栈遇到运算符就弹出两个操作数计算结果再压回去。为什么非要用后缀因为后缀表达式不需要括号、不需要考虑运算符优先级计算过程完全线性正好和栈的天然操作吻合。我自己第一次写完表达式求值的时候对这种“把一个看似有歧义的问题变成机械流程”的转变印象很深强烈建议你亲手实现一次。4.3 队列在系统里的地位从打印机到消息队列队列的应用更偏系统侧。最朴素的例子是打印机任务队列多个用户同时提交打印任务系统按提交顺序把它们排成队列一个接一个打印谁也不能插队。操作系统里的进程调度也确实用到了队列思想——先来先服务调度就是按到达顺序排队时间片轮转调度则是把所有就绪进程排成一个循环队列每个进程轮流获得一小段时间片。再往大了说分布式系统里到处是“消息队列”。生产者把消息投递到一个队列消费者按顺序消费生产者和消费者可以完全解耦即便瞬间流量洪峰消息也只是在队列里排队等待而不是直接把服务压垮。这个模型某种程度上就是你在数据结构课上学到的那个 queue只是加了持久化、集群、确认机制等等工业化的外壳。我第一次在真实项目里看到消息队列的时候脑子里第一反应就是“这不是课上的队列加了个分布式马甲吗”。底层原理明白了上层技术再多也只是包装。5. 初学阶段踩过的坑和排查清单5.1 栈顶初始值-1 还是 0前面提到 top 初始为 -1 的用法。很多人转用 C 语言写的时候容易混因为 C 里数组下标从 0 开始于是把 top 也初始化成 0导致第一个元素入栈时被写进 data[1]data[0] 白空着或者 push/pop 顺序反了出现索引越界。我的建议是写代码之前先在纸上定好两个约定——“top 表示栈顶元素的下标”还是“top 表示下一个可写入位置的下标”。前者初始 -1后者初始 0。任何教材都不会同时用两种你只要统一其中一种整个 push/pop 的加减顺序就顺理成章。5.2 循环队列判空判满总差一个这个坑前面提过这里再展开。假设牺牲一个空位的方案存储能力是 capacity-1。如果你入队了 capacity-1 个元素此时 rear 等于 (front capacity - 1) % capacity条件 (rear 1) % capacity front 正好成立判定为满。但如果你偷懒用了 rear front 判满那就永远判不了满。还有一种常见错误是遍历时循环次数算错比如应该输出 size 个元素结果写成 while front ! rear在满队列时直接少输出一个。建议初始化时把容量设小一点比如 5然后手推一遍 0、1、2、3、4 个元素的进出过程再对照代码看输出很快能找到问题。5.3 链式队列出队单节点场景前面提过 tail 忘记更新的问题。我再补充一个更隐蔽的坑如果你用单向链表实现队列出队完把 head 后移之后旧 head 节点还在内存里没人引用语言会自动回收但旧 head 的 next 可能还指向新的 head。如果你在出队时还顺手做了一些“遍历查找”操作用的又是旧引用可能会看到不对的数据。这种问题在 C/C 里表现得更明显在 Python/Java 里往往不会崩但逻辑会错。排查时先画链表结构图标出 head 和 tail 的位置再模拟一次出队过程尤其是队列只有一个节点的那一步。5.4 一个通用的调试方法小规模手推各类数据结构初学阶段最底层的排查思路就三个字画、推、验。画画数组或链表示意图标记指针位置推手工模拟每一步操作记下期望结果验拿代码和小数据量甚至容量为 1 或 2 的极端情况跑一遍对比手推。很多初学者喜欢一上来就在大数据量上调效率极低。我带人 debug 的时候说的第一句话永远是“把规模降到最小然后告诉我如果容量是 2你的代码会发生什么”。这个习惯养成了能省下大把的排查时间。6. 从初体验到进阶栈和队列还能延伸出什么写完基础版本之后我建议你按这个顺序继续进阶。第一步把题目做透。经典的“有效的括号”“用两个栈实现队列”“用队列实现栈”“最小栈”都是栈与队列章节的高频题。做这些题不是背答案而是训练“把一个结构的能力翻译成另一种结构”的能力。我见过很多人刷题刷得飞快但让他讲为什么这样做就卡壳多半是没把存取规则真正理解成一种秩序只是记住了套路。第二步认识变体。双端队列deque两头都能进出Python 的 collections.deque 和 C 的 deque 都是这个结构的工程实现优先队列堆按优先级出队不再是单纯 FIFO而是“优先级最高先出”。到了这层你会发现自己当初那点“后进先出/先进先出”的规则只是更大设计谱系的起点。第三步把栈和队列放回更大的算法框架里。深度优先搜索DFS显式使用时是栈隐式使用时就是递归广度优先搜索BFS必定用到队列因为它要一层一层推进。树和图的很多问题写代码之前先问自己一句这个遍历或搜索过程天然是“后进先出”还是“先进先出”答出来数据结构的选择就水到渠成。我个人给初学者讲这部分内容时常说的一句话是栈和队列不是两个需要背的定义它们是你在真实程序里反复遇到的两类“存取秩序”。你用编辑器里 CtrlZ 撤销的时候就经历了栈你在食堂排队的时候就经历了队列。把抽象概念拉回生活把生活经验再提炼成代码这是学数据结构最有效的路径也是我这么多年实践下来最有用的心得。希望这份初体验记录能帮你把这两块基石稳稳砌进自己的知识体系里。 
长河君 · 2026/10/17 9:14:06 · 阅读 1.2k 栈与队列初体验：从生活场景到工程实现与经典应用
先讲个场景。你在浏览器里一个页面接一个页面地看文章想回上一篇点一下后退就回去了再想回来点前进又回去了。这背后就是一个栈。再看食堂中午排队买饭先来的人先拿到餐盘后面的人只能等着这背后就是一个队列。算法与程序设计课程里很多人第一堂数据结构课就是从这两个最简单的结构开始的——它们不复杂却建立起你对“数据怎么组织、怎么存取”的第一次完整认知。这篇文章是我结合自己学习和实际项目中的使用经验为刚接触算法与程序设计的同学写的一份“栈与队列初体验”记录。我会从生活场景切入把栈和队列的本质讲透然后手把手带你用数组和链表分别实现它们接着讲清楚循环队列里的取模运算到底怎么回事最后用函数调用、浏览器历史、消息队列这些真实场景让你看到学的东西是怎么被用起来的。文章里的代码我会尽量简单还会把初学阶段最容易踩的坑单独列出来方便你对照排查。看完之后你至少能自己写出一份能跑、能讲、能应对常见面试题的栈和队列实现。1. 先搞清楚栈和队列到底在解决什么问题1.1 两种“存取规则”就是两套秩序栈Stack和队列Queue在教科书里被归为“线性表”的两种受限形式。所谓线性表就是数据一个接一个排成一串而“受限”的意思是数组和链表允许你在任意位置插入或删除元素栈和队列却只允许你在特定位置操作。栈只允许在“栈顶”top这一个端口放东西和取东西最后一个放进去的元素最先被取出来英文叫 LIFOLast In, First Out后进先出。想体会这个规则最简单的就是看一摞叠起来的餐盘你总是先把新盘子放在最上面取盘子时也只能先取最上面的那个底下的盘子不会被立刻碰到。队列则正好相反允许两端操作但方向固定新的元素从“队尾”rear进入要取元素只能从“队头”front离开第一个进来的元素第一个出去即 FIFOFirst In, First Out。食堂排队打饭就是教科书级的例子排在队伍最前面的先打到饭后到的人只能排在队尾等着。为什么特意强调这种“受限”因为很多初学者会疑惑数组和链表明明可以做同样的事为什么还要定义栈和队列答案是限制操作范围恰恰是为了更清晰地表达模型。当你只需要“后进先出”或“先进先出”这种单一规则时把接口收敛成 push/pop 或 enqueue/dequeue 几个操作调用者就不用关心内部怎么组织、不需要在任意位置插删出错的概率大幅降低代码的可读性也提升一截。这种“只暴露必要接口隐藏内部实现细节”的思想其实就是抽象数据类型ADT的雏形。往后学到映射、堆、图的时候你会发现这个思维模式始终贯穿。1.2 为什么算法课总把栈和队列放在第一站我自己带过不少初学者发现课程大纲把栈和队列安排在第一梯队是有道理的。原因有三点。第一它们足够简单适合建立信心。你不需要先理解复杂的树形结构或递归思维只要抓住“一端口进出一端口进出”和“一头进另一头出”两条规则就能上手写代码。对刚接触数据结构的人来说这种“我也能实现一个结构”的正反馈非常重要比一上来就啃红黑树不知道友好多少。第二它们是理解其他结构的跳板。树的遍历尤其是深度优先和广度优先背后分别站着一个栈和一个队列图的搜索也同样如此。递归的执行过程其实就是函数调用栈一层层入栈出栈的过程。换句话说栈和队列是很多进阶算法里那个“隐形的关键先生”很多看起来花哨的问题拆到底就是“维护一个栈”或者“维护一个队列”。第三它们天然带着一堆“边界问题”要你处理。容量满了怎么办队列空了还能出队吗循环队列怎么区分满和空这类问题锻炼的是程序员最重要的基本功——边界条件思维。我面试别人的时候经常用一道“用栈实现队列”的题考察的其实并不是代码量而是你有没有把两种结构的入出方向理清楚。能顺手写对说明基本的存取秩序已经内化了。2. 手写一个栈先写数组版再写链表版2.1 数组版栈一个索引就够用先看最直观的数组版。我们用一个连续数组存储数据再用一个整数 top 记录当前栈顶的位置。核心操作就三个push 在栈顶加元素pop 把栈顶元素取走peek 只看顶部不取走。class ArrayStack: def __init__(self, capacity10): self.capacity capacity self.data [None] * capacity self.top -1 # 初始时栈为空 def is_empty(self): return self.top -1 def is_full(self): return self.top self.capacity - 1 def push(self, value): if self.is_full(): raise OverflowError(栈已满无法入栈) self.top 1 self.data[self.top] value def pop(self): if self.is_empty(): raise IndexError(栈为空无法出栈) value self.data[self.top] self.data[self.top] None # 释放引用 self.top - 1 return value def peek(self): if self.is_empty(): raise IndexError(栈为空无法查看栈顶) return self.data[self.top]这里有个细节值得单独说top 初始化成 -1不是 0。为什么因为 -1 这个值巧妙地表达了“当前栈里没有任何元素”当栈里有一个元素时 top 变成 0这个元素就存在 data[0] 里有两个元素时 top 是 1。这样 push 时先自增再赋值pop 时先取值再自减两个操作都不用额外特判边界自然被索引值覆盖。如果你把 top 初始化为 0push 就要“先赋值再自增”pop 要“先自减再取值”写起来别扭稍不留神就越界。这是很多教材默认 -1 的真实原因不是一个随意的约定。数组版的缺点也很明显容量是写死的。push 满员后要么抛异常要么做扩容。如果在工程里做动态扩容常见策略是“当前容量翻倍”整体摊还复杂度仍是 O(1)很多高级语言动态数组就是这么干的。学习阶段建议先写固定容量版本把索引边界想清楚再考虑扩容。2.2 链表版栈用指针代替容量限制数组版的核心问题是容量固定链表版则通过把每个元素装进一个节点node节点之间用指针串起来彻底摆脱容量限制。栈顶就是链表的头节点push 相当于在头部插入pop 相当于删除头节点两个操作都只动一根指针O(1)。用 Python 写链表版class Node: def __init__(self, value): self.value value self.next None class LinkedStack: def __init__(self): self.head None # 栈顶指针 def is_empty(self): return self.head is None def push(self, value): new_node Node(value) new_node.next self.head self.head new_node def pop(self): if self.is_empty(): raise IndexError(栈为空无法出栈) value self.head.value self.head self.head.next return value def peek(self): if self.is_empty(): raise IndexError(栈为空无法查看栈顶) return self.head.value这段代码里最容易写错的是 push 的四行顺序正确顺序是“先让新节点指向旧头再把头指针挪到新节点”。反过来的话旧链表就丢了。我见过不少初学同学先写 self.head new_node再写 new_node.next self.head结果新节点指向了自己形成环调试半天找不出来。记住一个口诀先搭线再动指针。先让新节点的 next 指向当前头然后再更新头指针。链表版没有容量上限上限只取决于内存也不需要预分配空间但每个节点都额外保存一个 next 指针空间开销比数组版大。在极端情况下频繁 new 节点和释放节点还可能带来内存碎片和性能损耗。所以两种实现没有绝对优劣取决于场景。2.3 两种实现的对比与选型对比维度数组版栈链表版栈容量固定或需动态扩容理论无上限随机访问支持data[i] 可取任意元素不支持只能访问栈顶空间效率可能浪费未用槽位每个节点多存一个指针插入删除O(1)数组连续内存更友好O(1)但有节点分配开销适用场景容量可预估、追求性能容量未知、数据波动大选型心得我放在最后说如果是练习题和竞赛数组版几乎总是更顺手如果是设计一个生命周期长、数据量波动大的系统组件链表版或者直接用语言自带库更合理。但学习阶段建议两种都写一遍因为“数组实现锻炼索引思维链表实现锻炼指针思维”这两种思维恰好是数据结构里最核心的两套基本功。3. 队列的三种写法顺序、循环、链式3.1 顺序队列为什么明明有空位却“溢出”了队列用数组实现时需要两个指针front 指向队头rear 指向队尾。入队时 rear 后移并写入出队时 front 后移并取出。听起来很简单但很快会遇到一个经典问题假溢出。假设一个长度为 5 的数组你连续入队 5 个元素rear 走到下标 4。然后出队 3 次front 走到下标 3。这时候数组前三个位置是空着的但 rear 已经在最右边新元素想入队数组说“满了”。可明明有 3 个空格子没人用这就是“假溢出”。如果直接报满空间就被白白浪费了。解决假溢出的第一反应是把所有元素整体往左挪但挪动是 O(n) 的出队一次就要挪一次代价太难看。于是出现了循环队列。3.2 循环队列取模运算和那个“牺牲掉的空位”循环队列的思路是把数组想象成一个环形跑道rear 到达数组末尾时下一步绕回下标 0就好像跑完一圈再从头开始。实现上只需要一个取模运算rear (rear 1) % capacity front (front 1) % capacity关键问题是怎么区分“队空”和“队满”如果只用 front rear 判断空那满的时候 front 也等于 rear两个状态就分不开了。常规解法有三种。第一种牺牲一个存储单元。约定队满条件是 (rear 1) % capacity front也就是说 rear 后面紧挨着的那个槽位不能放数据。这样做代码最简单代价是数组永远有一个格子是空的。第二种在结构体里加一个 size 字段记录当前元素个数。入队 size1出队 size-1判空判满看 size 就行。空间不浪费但多维护一个变量。第三种加一个 flag 标记最后一次操作是入队还是出队。个人不推荐太绕出问题的概率高。我看过很多同学的循环队列代码最常见的问题是判断条件写串。比如用 while 循环遍历队列终止条件写成 front ! rear结果因为满时 front 也等于 rear把满队列当成空队列处理直接跳出不输出任何元素。这类差一错误最好的排查办法是画图。把数组画成一个圈用两个不同颜色的箭头标记 front 和 rear模拟入队出队各几步立刻能看出条件错在哪。class CircularQueue: def __init__(self, capacity5): self.capacity capacity self.data [None] * capacity self.front 0 self.rear 0 # 牺牲一个空位rear 指向下一个要写入的位置 def is_empty(self): return self.front self.rear def is_full(self): return (self.rear 1) % self.capacity self.front def enqueue(self, value): if self.is_full(): raise OverflowError(队列已满) self.data[self.rear] value self.rear (self.rear 1) % self.capacity def dequeue(self): if self.is_empty(): raise IndexError(队列为空) value self.data[self.front] self.data[self.front] None self.front (self.front 1) % self.capacity return value def size(self): return (self.rear - self.front self.capacity) % self.capacity注意 size 的公式(rear - front capacity) % capacity。这个公式很有代表性它说明取模运算在处理“环状下标”问题里的妙处两个指针在环上绕圈差值可能为负数比如 rear 越过末尾回到 0而 front 还在 3加上 capacity 再取模就把差值修正到 0 到 capacity-1 之间。后面学哈希表、环形缓冲区你会反复看到这个套路。3.3 链式队列两个指针都别忘链式队列用链表实现时需要维护两个指针head 指向队头出队端tail 指向队尾入队端。入队时在 tail 后面挂新节点并更新 tail出队时取 head 指向的节点并让 head 后移。这里的坑比栈的链表版更多。第一个坑出队时如果发现 head 指向的节点是最后一个节点那么删除它之后tail 也必须更新为 None。很多初学者只更新 head不更新 tail结果队列空了之后 tail 还指向已经被释放的节点形成“悬空指针”下次再入队时 tail.next new_node 会写到非法地址上程序直接崩溃。第二个坑入队时如果不是第一次入队代码是 tail.next new_node; tail new_node但如果队列本来就是空的head 和 tail 都是 None你就要同时把 head 和 tail 都指向新节点。这个 if/else 分支很容易被漏掉。我习惯把链式队列的入队写成def enqueue(self, value): new_node Node(value) if self.tail is None: # 队列为空 self.head new_node self.tail new_node else: self.tail.next new_node self.tail new_node出队时则先判断空然后保存 value再判断“出队后是否为空队列”来决定要不要把 tail 置 None。判断的条件就是出队之前 head tail说明这个节点是唯一的节点。4. 学完得用起来几个经典应用4.1 函数调用栈你写的每一层递归都靠它每个程序在运行时会维护一个函数调用栈。每次调用一个函数系统会把这次调用的局部变量、返回地址、参数等信息打包成一个栈帧压到调用栈上函数返回时这个栈帧被弹出。嵌套调用就是不断的压栈和弹栈所以递归过深时会报“栈溢出”——不是机器没内存而是这个调用栈被撑满了。理解了栈你就真正理解了递归的代价每一层递归都要额外的栈帧空间递归深度过大时空间开销会直接变成程序的致命伤。举一个可视化例子斐波那契数列的朴素递归 fib(5)调用树里 fib(3) 会被重复计算多次这些重复调用在调用栈里是“先深入再回来”的过程栈帧创建和销毁都很频繁。这也是为什么很多算法课讲递归和动态规划之前会先用栈来铺垫“递归是怎么执行的”。学完栈之后再回头看递归你不会再觉得它是魔法而是一套明确可追踪的压栈弹栈流程。4.2 括号匹配、表达式求值与浏览器栈的经典应用算法题是括号匹配。给你一串包含左右圆括号、方括号、花括号的字符判断是否合法“([])”合法“([)]”不合法。标准解法是遇到左括号就压栈遇到右括号就弹出栈顶并检查类型是否匹配。如果遍历完栈不为空或者遇到右括号时栈是空的都不合法。这个算法代码很短但考察的就是栈“后进先出”的特性——最近的左括号必须最先被右括号闭合。写的时候你还能顺便练到字典映射的用法一举两得。浏览器前进后退是双栈的经典模型用一个后退栈记录访问历史一个前进栈记录“退回去的那些页面”。点击后退时当前页面压入前进栈把后退栈顶弹出来显示点击前进时反过来。做完这个例子你就能理解很多产品的“撤销/重做”功能本质上也是两棵版本的栈。表达式求值也用栈。中缀表达式“3 4 * 2”要计算计算机往往先把它转成后缀表达式“3 4 2 * ”然后从左往右扫描遇到数字就压栈遇到运算符就弹出两个操作数计算结果再压回去。为什么非要用后缀因为后缀表达式不需要括号、不需要考虑运算符优先级计算过程完全线性正好和栈的天然操作吻合。我自己第一次写完表达式求值的时候对这种“把一个看似有歧义的问题变成机械流程”的转变印象很深强烈建议你亲手实现一次。4.3 队列在系统里的地位从打印机到消息队列队列的应用更偏系统侧。最朴素的例子是打印机任务队列多个用户同时提交打印任务系统按提交顺序把它们排成队列一个接一个打印谁也不能插队。操作系统里的进程调度也确实用到了队列思想——先来先服务调度就是按到达顺序排队时间片轮转调度则是把所有就绪进程排成一个循环队列每个进程轮流获得一小段时间片。再往大了说分布式系统里到处是“消息队列”。生产者把消息投递到一个队列消费者按顺序消费生产者和消费者可以完全解耦即便瞬间流量洪峰消息也只是在队列里排队等待而不是直接把服务压垮。这个模型某种程度上就是你在数据结构课上学到的那个 queue只是加了持久化、集群、确认机制等等工业化的外壳。我第一次在真实项目里看到消息队列的时候脑子里第一反应就是“这不是课上的队列加了个分布式马甲吗”。底层原理明白了上层技术再多也只是包装。5. 初学阶段踩过的坑和排查清单5.1 栈顶初始值-1 还是 0前面提到 top 初始为 -1 的用法。很多人转用 C 语言写的时候容易混因为 C 里数组下标从 0 开始于是把 top 也初始化成 0导致第一个元素入栈时被写进 data[1]data[0] 白空着或者 push/pop 顺序反了出现索引越界。我的建议是写代码之前先在纸上定好两个约定——“top 表示栈顶元素的下标”还是“top 表示下一个可写入位置的下标”。前者初始 -1后者初始 0。任何教材都不会同时用两种你只要统一其中一种整个 push/pop 的加减顺序就顺理成章。5.2 循环队列判空判满总差一个这个坑前面提过这里再展开。假设牺牲一个空位的方案存储能力是 capacity-1。如果你入队了 capacity-1 个元素此时 rear 等于 (front capacity - 1) % capacity条件 (rear 1) % capacity front 正好成立判定为满。但如果你偷懒用了 rear front 判满那就永远判不了满。还有一种常见错误是遍历时循环次数算错比如应该输出 size 个元素结果写成 while front ! rear在满队列时直接少输出一个。建议初始化时把容量设小一点比如 5然后手推一遍 0、1、2、3、4 个元素的进出过程再对照代码看输出很快能找到问题。5.3 链式队列出队单节点场景前面提过 tail 忘记更新的问题。我再补充一个更隐蔽的坑如果你用单向链表实现队列出队完把 head 后移之后旧 head 节点还在内存里没人引用语言会自动回收但旧 head 的 next 可能还指向新的 head。如果你在出队时还顺手做了一些“遍历查找”操作用的又是旧引用可能会看到不对的数据。这种问题在 C/C 里表现得更明显在 Python/Java 里往往不会崩但逻辑会错。排查时先画链表结构图标出 head 和 tail 的位置再模拟一次出队过程尤其是队列只有一个节点的那一步。5.4 一个通用的调试方法小规模手推各类数据结构初学阶段最底层的排查思路就三个字画、推、验。画画数组或链表示意图标记指针位置推手工模拟每一步操作记下期望结果验拿代码和小数据量甚至容量为 1 或 2 的极端情况跑一遍对比手推。很多初学者喜欢一上来就在大数据量上调效率极低。我带人 debug 的时候说的第一句话永远是“把规模降到最小然后告诉我如果容量是 2你的代码会发生什么”。这个习惯养成了能省下大把的排查时间。6. 从初体验到进阶栈和队列还能延伸出什么写完基础版本之后我建议你按这个顺序继续进阶。第一步把题目做透。经典的“有效的括号”“用两个栈实现队列”“用队列实现栈”“最小栈”都是栈与队列章节的高频题。做这些题不是背答案而是训练“把一个结构的能力翻译成另一种结构”的能力。我见过很多人刷题刷得飞快但让他讲为什么这样做就卡壳多半是没把存取规则真正理解成一种秩序只是记住了套路。第二步认识变体。双端队列deque两头都能进出Python 的 collections.deque 和 C 的 deque 都是这个结构的工程实现优先队列堆按优先级出队不再是单纯 FIFO而是“优先级最高先出”。到了这层你会发现自己当初那点“后进先出/先进先出”的规则只是更大设计谱系的起点。第三步把栈和队列放回更大的算法框架里。深度优先搜索DFS显式使用时是栈隐式使用时就是递归广度优先搜索BFS必定用到队列因为它要一层一层推进。树和图的很多问题写代码之前先问自己一句这个遍历或搜索过程天然是“后进先出”还是“先进先出”答出来数据结构的选择就水到渠成。我个人给初学者讲这部分内容时常说的一句话是栈和队列不是两个需要背的定义它们是你在真实程序里反复遇到的两类“存取秩序”。你用编辑器里 CtrlZ 撤销的时候就经历了栈你在食堂排队的时候就经历了队列。把抽象概念拉回生活把生活经验再提炼成代码这是学数据结构最有效的路径也是我这么多年实践下来最有用的心得。希望这份初体验记录能帮你把这两块基石稳稳砌进自己的知识体系里。