你有没有过这种经历代码逻辑看着没什么问题一运行就卡死递归一写就停不下来最后丢给你一句堆栈溢出又或者在高并发场景下明明接口都被打满了前端却还在傻等。这些问题的底层答案往往都指向两个最基础的数据结构——栈和队列。初识数据结构栈和队列很多刚开始学编程的人一听到数据结构四个字就头皮发麻觉得又是链表又是二叉树离实际工作好远。但如果你把程序运行的过程拆开看就会发现函数调用靠栈消息处理靠队列甚至浏览器后退、IDE撤销、任务调度背后全是这两个结构在撑场子。栈和队列不光是数据结构教材里排在最前面的两个基础结构更是理解递归、系统设计、并发模型的一把钥匙。这篇文章我会从是什么、为什么、怎么用三个层面拆透它们尽量把原理讲得接地气代码部分给到可以直接跑的实例后面还整理了一份我踩过的坑清单希望能帮刚入门的同学少走弯路。1. 为什么先学栈和队列1.1 数据结构解决的根本问题数据结构本质上解决一件事怎么把数据存下来并且让增删改查变得高效。不同的场景对数据的操作方式要求不一样于是就有了各种形态的结构。栈和队列恰恰代表了两类最极端的操作约束——一个只允许在一端进出一个一端进另一端出。这两种约束看似简单却构成了大量复杂系统的基础。打个比方你去食堂排队打饭这就是队列先来的人先打到饭后来的排在队尾谁也不能插队。而如果你往一个桶里叠盘子后放进去的盘子会先被拿出来这就是栈。生活里这两个场景无处不在程序世界无非是把这种直觉用代码表达出来。1.2 栈和队列的本质受限的线性表栈和队列都可以看作是线性表的特殊形态。线性表就是把数据排成一条线数组和链表是两种最常见的物理存储方式。栈和队列不关心底层是数组还是链表它们关心的是对外暴露的操作规则。栈遵循后进先出LIFOLast In First Out队列遵循先进先出FIFOFirst In First Out。这两个规则就是它们的灵魂。其他所有的细节比如扩容、指针移动、边界检查都是围绕这两条规则服务的。很多初学者会纠结一个问题既然数组和链表已经能存数据了为什么还要弄出栈和队列答案很简单——因为不受限的操作会带来心智负担。如果一段数据可以被任意位置插入删除你必须时刻维护它内部的顺序关系。而栈和队列把操作限制死了反而让逻辑变得清晰可控。写代码的时候你能明确知道数据从哪来、往哪去、什么时候能拿到。2. 栈的深度拆解2.1 栈的核心操作与行为特征栈就是只能在栈顶做操作的结构。它对外通常只提供几个方法push入栈往栈顶放一个元素pop出栈从栈顶取走一个元素peek / top查看栈顶只看一眼不取走isEmpty判断是否为空栈顶是关键概念。入栈和出栈都发生在栈顶栈底永远不动。你只能接触到最上面那个元素想拿底部的元素得先把上面的全部弹出。这个限制看起来很不方便但正是这种限制带来了极大的确定性。比如函数嵌套调用时系统就是靠栈来记住每一层调用返回后该去哪里的。A调用BB调用CC返回后回到B的下一行B返回后回到A的下一行。这就是一个天然的栈结构谁最后被调用谁最先返回。2.2 基于数组实现栈数组实现栈是最直接的方式。用一个变量记录当前栈顶位置push时把数据写到数组里并移动指针pop时指针回退。上代码class ArrayStack: def __init__(self, capacity10): self.capacity capacity self.data [None] * capacity self.top 0 # top指向下一个可写入位置 def push(self, value): if self.top self.capacity: # 这里可以扩容本示例先抛异常 raise OverflowError(栈已满) self.data[self.top] value self.top 1 def pop(self): if self.top 0: raise IndexError(栈为空) self.top - 1 value self.data[self.top] self.data[self.top] None # 释放引用 return value def peek(self): if self.top 0: raise IndexError(栈为空) return self.data[self.top - 1] def is_empty(self): return self.top 0这里面有个细节很多人会忽略pop的时候最好把原位置清空。如果只是把top减一数组里还保留着旧对象的引用在长时间运行的程序里就会造成内存无法回收。平时写Demo可能无所谓但在服务端程序里这种细节有可能就是内存泄漏的源头。数组栈的优点是内存连续缓存命中率高读写快。缺点是容量固定虽然也可以实现动态扩容但扩容需要整体拷贝有瞬时开销。2.3 基于链表实现栈链表实现栈不需要预设容量按需分配节点push和pop的时间复杂度都是O(1)。但每个节点要额外存储一个指针内存开销比数组大。我用Python简单写一个class LinkedStackNode: def __init__(self, value): self.value value self.next None class LinkedStack: def __init__(self): self.head None self.size 0 def push(self, value): node LinkedStackNode(value) node.next self.head self.head node self.size 1 def pop(self): if self.head is None: raise IndexError(栈为空) value self.head.value self.head self.head.next self.size - 1 return value def peek(self): if self.head is None: raise IndexError(栈为空) return self.head.value def is_empty(self): return self.head is None这段代码里我把新节点插在链表头部head就是栈顶。入栈出栈都对head操作复杂度天然O(1)。如果你非要把链表尾部当栈顶那出栈就得遍历到倒数第二个节点复杂度变成了O(n)那就完全失去栈的意义了。这也是我经常跟初学者强调的实现细节不但影响效率甚至决定了一种结构是否还算它本来的样子。2.4 栈的实战括号匹配与函数调用栈最经典的入门应用就是括号匹配。LeetCode 20题那种判断一串字符串里的括号是否成对且嵌套正确。思路很清晰遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配就弹出不匹配直接判定失败。遍历结束后如果栈为空说明全部匹配。再往深看一个东西调用栈。你写递归函数的时候每一次调用都会在系统调用栈上压一层帧每层帧里存着局部变量、返回地址这些信息。如果递归没有终止条件或者递归深度太大栈会耗尽程序直接崩掉——就是你常看到的Stack Overflow。我用一个简单的递归例子展示一下栈的压入与弹出过程def factorial(n): if n 1: return 1 return n * factorial(n - 1)当n等于3时调用过程是这样的factorial(3)压栈里面调用factorial(2)再压栈然后factorial(1)压栈。factorial(1)返回1后弹栈接着factorial(2)计算2乘1返回2后弹栈最后factorial(3)计算3乘2返回6后弹栈。整个过程就是一个后进先出的流程。理解了调用栈你就能明白为什么递归层数太多会栈溢出也能理解为什么尾递归在某些语言里能被优化因为它能让栈帧复用。3. 队列的深入解析3.1 队列的核心操作与行为特征队列的操作与栈对应但规则相反enqueue入队从队尾添加一个元素dequeue出队从队头移除一个元素front / peek查看队头只看不移除isEmpty判断是否为空队列体现的是公平性。谁先来谁先被处理不存在插队。这种特性让它成了天然的缓冲器和调度器。3.2 循环队列数组实现队列的正确方式用数组实现队列有一个经典问题如果队头指针不断后移前面空出来的位置就浪费了。很多人第一版写的数组队列入队几次再出队几次就会遇到数组前面空着后面却满了的尴尬局面。解决办法是循环队列。循环队列的核心思想是把数组当作一个环队尾指针移动到数组末尾时重新绕回开头。这里需要维护两个指针front指向队头rear指向队尾的下一个位置。判空条件是front等于rear判满条件是(rear 1) % capacity等于front。注意这种写法会故意浪费一个存储位置否则无法区分空和满。class CircularQueue: def __init__(self, capacity5): self.capacity capacity self.data [None] * capacity self.front 0 self.rear 0 def enqueue(self, value): if (self.rear 1) % self.capacity self.front: raise OverflowError(队列已满) self.data[self.rear] value self.rear (self.rear 1) % self.capacity def dequeue(self): if self.front self.rear: raise IndexError(队列为空) value self.data[self.front] self.data[self.front] None self.front (self.front 1) % self.capacity return value def is_empty(self): return self.front self.rear def __len__(self): return (self.rear - self.front self.capacity) % self.capacity取模运算是循环队列的灵魂。很多初学者看不懂(self.rear 1) % self.capacity到底在干什么其实就是在模拟指针走到数组末尾后跳回开头。这个操作在数组下标处理里非常常见以后你写环形缓冲区、定时器轮转调度都会碰到同样的套路。3.3 链式队列不需要容量的动态方案如果队列长度不确定可以用链表实现。入队操作在链表尾部追加节点出队操作移除链表头部节点。维护一个tail指针指向队尾这样入队就不用遍历整个链表。class LinkedQueueNode: def __init__(self, value): self.value value self.next None class LinkedQueue: def __init__(self): self.head None self.tail None def enqueue(self, value): node LinkedQueueNode(value) if self.tail is None: self.head node self.tail node else: self.tail.next node self.tail node def dequeue(self): if self.head is None: raise IndexError(队列为空) value self.head.value self.head self.head.next if self.head is None: self.tail None return value def is_empty(self): return self.head is None这里必须注意一个边界情况当队列中只有一个节点时出队后head和tail都要置空。很多人只更新了head忘了清tail结果tail指向一个已经出队的节点下一次入队时链表就被污染了。这个bug非常隐蔽我自己当年调试这类问题花了不少时间。3.4 队列的实战消息队列与任务调度队列在工程里的应用比栈还广泛。消息队列Message Queue可以看作一个标准的FIFO缓冲区生产者把消息塞进队列尾部消费者从队列头部取消息。生产者和消费者的速度可以不一致队列就在中间做削峰填谷防止系统被突发流量打崩。任务调度也是队列的经典场景。比如一个后台线程池接到了100个耗时任务如果来一个处理一个操作系统的线程数量很容易失控。把这些任务排进队列由固定数量的工作线程慢慢消费既保证了资源可控也保证了任务按提交顺序被处理。再举一个你每天都在用的例子打印任务。当你同时向打印机提交多个文档时打印机会按照提交的先后顺序依次打印这就是一个标准队列。4. 栈和队列的选择与应用场景对比4.1 什么时候用栈什么时候用队列很多初学者拿到一个需求不知道该用哪个。这里给出一个简单粗暴的判断方法如果业务逻辑里存在明显的后到的先被处理语义比如撤销、回退、递归、括号匹配、表达式求值用栈。如果业务逻辑里存在明显的先到先得语义比如排队、缓存、异步解耦、广度优先遍历用队列。如果数据可以从任意位置插入删除不要硬套栈和队列直接考虑数组或链表。判断依据就是操作顺序是否符合LIFO或FIFO。千万别为了用数据结构而用数据结构先理清楚业务里数据的流转规则再决定采用哪种结构。4.2 数组与链表实现方式对比我给一个对比表方便大家直接对照选型对比维度数组实现栈/队列链表实现栈/队列内存占用预分配容量可能有闲置浪费按需分配但每个节点有指针开销访问速度连续内存缓存友好节点离散缓存不友好容量扩展需要扩容搬移数据天然动态扩展实现难度循环队列边界易错指针操作易错适合场景容量可预估、追求性能容量不可预估、频繁增删如果容量是明确的比如缓存池最大100个连接数组实现更合适。如果流量波动剧烈、容量不好估算链表实现更省心。4.3 搭配实战用栈实现队列有一个联练习非常能帮助理解这两个结构的差异如何用两个栈实现一个队列这个题在很多面试里都会出现。核心思路是入队时直接往入栈里push出队时如果出栈为空先把入栈的所有元素弹出并压进出栈再取出出栈的栈顶元素。因为栈会把元素顺序倒过来经过两次倒转之后顺序又变正了。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self): return not self.in_stack and not self.out_stack这个实现的摊还时间复杂度是O(1)。每个元素最多被压入两次、弹出两次整体均摊下来性能非常好。做一遍这个练习你对栈的倒序特性和队列的顺序要求理解都能上一个台阶。5. 常见问题与调试经验5.1 一定要避开的几个坑第一个坑栈溢出。不只是递归会触发如果你用一个容量很小的数组栈又在循环里频繁push同样会溢出。我见过不少新手在写括号匹配时直接给栈分配了10个大小然后拿一个很长的字符串去跑一跑就崩。解决办法很简单要么用动态扩容的栈要么预估好最坏情况下的元素数量。第二个坑循环队列判空判满混淆。这是数组队列里最典型的问题。判空是front等于rear判满是(rear 1) % capacity等于front。如果你在判满时也写成front等于rear循环队列就会在只剩一个空位时继续入队覆盖掉队头数据。这个bug排查起来很费劲因为触发条件取决于指针相对位置。第三个坑链式队列出队时忘更新tail。前面已经说过在队列只剩一个节点时出队后head和tail都要置空。建议每次写完出队逻辑都测试一下一个元素入队后立即出队再入队一个新元素这个边界场景。第四个坑并发环境下直接用线程不安全的栈或队列。Python自带list的append和pop是线程安全的吗单个操作是原子的但如果你先判断isEmpty再pop中间就可能被其他线程打断。生产环境里不要自己写这种带状态的容器直接用专门的并发队列。5.2 排查问题的实用思路写栈和队列相关代码如果出了问题我一般按这个顺序排查先打印指针状态。把front、rear、top这些变量的值每次操作后都打出来手动模拟一遍看看是否符合预期。千万别盯着代码干瞪眼手写一遍运行过程问题往往一眼就看出来了。再检查边界条件。空容器执行pop/dequeue满容器执行push/enqueue单元素容器执行操作后再执行操作这些场景最容易出问题。写单元测试时把这几个用例全部覆盖到。最后检查内存/引用清理。数组队列里出队时不置空链式栈里pop后没释放节点引用这些问题平时不爆炸跑久了就出妖。5.3 如何彻底掌握这两个结构我的建议是不要只停留在看书和做题。你一定要动手实现一遍数组栈、链栈、循环队列、链式队列用代码把几个核心逻辑跑通。实现完之后再把下面几个经典问题亲手做一遍用两个栈实现一个队列用两个队列实现一个栈括号匹配问题逆波兰表达式求值最近的请求次数队列经典题这几道题做完并且能讲清楚原理你对栈和队列的理解就已经超过大多数人。后面再去学递归、深度优先搜索、广度优先搜索、滑动窗口这些概念你会发现自己上手速度明显变快因为它们本质上都建立在栈和队列这两种结构之上。我个人在实际带人时发现很多同学不是学不会栈和队列而是太急着往前赶。总觉得这么简单的东西不值得认真实现随便看看就跳到二叉树结果遇到递归深了栈溢出、BFS不会用队列又回过头来补基础。你要是能沉下心把这两个结构彻底吃透后面学什么都会顺很多。