栈和队列是算法训练营里少有的“一开始觉得简单越刷越觉得不简单”的两个结构。Day10的part01通常就是把这两兄弟放在一起过一遍先理解它们各自的“别扭”规则再通过几道经典题把规则焊死在脑子里。这篇文章就按我平时带训练营的节奏来写把为什么这么设计、代码怎么写、哪些地方容易翻车都讲透。适合刚刷完数组和链表、准备进入“受限线性表”阶段的同学也适合二刷时想补底层细节的人。很多人习惯把栈和队列割裂开记结果一看到“用栈实现队列”“用队列实现栈”这种题就傻眼。其实这两个结构天生就是一对镜像一个后进先出一个先进先出一个只在一端操作一个两端各管各的。把它们放在同一天学不是为了赶进度而是为了让你在对比中真正理解“操作受限”这四个字到底改变了什么。1. 为什么先把栈和队列放在一起学1.1 两种结构的“反常识”定义栈的定义是后进先出LIFO队列的定义是先进先出FIFO。听起来很简单但很多初学者会犯一个认知错误觉得栈就是“从一端进出”队列就是“一端进另一端出”然后试图用“数组的正着遍历、倒着遍历”来理解。这个方向其实有点偏。我更喜欢用生活场景来建立直觉。栈就像一摞盘子你永远只能从最上面拿盘子新盘子也永远放在最上面。如果你想拿最底下的盘子必须把上面的全部移开。队列就像奶茶店排队先来的人先点单后到的人站到队尾谁都不能插队。这里的关键不是“顺序”而是“限制”。数组和链表想访问哪个元素都行但栈和队列不行。栈只允许在栈顶操作队列只允许在队尾入队、队头出队。这个限制不是缺点恰恰是它们高效的原因。算法题里很多问题本来就不需要“随机访问”只需要“最近放入的”或“最早放入的”强行用数组反而要想办法维护顺序复杂度还高。还有一个容易踩的坑栈和队列都不是C/Python语言内置的“基础类型”它们是基于数组或链表封装出来的逻辑结构。这意味着你在刷题时不仅要会用语言自带的栈和队列还得能手写一个。Day10 part01的重点之一就是让你看穿这层封装。1.2 底层实现选择的奥妙既然栈和队列是逻辑结构那就得选物理存储方式。最常见的是数组和链表两者各有各的脾气。先说栈。数组实现栈非常自然一个数组加一个top指针top指向栈顶元素的位置。入栈时top加1赋值出栈时top减1逻辑上元素“消失”了。因为所有操作都在栈顶数组的空间是连续分配的CPU缓存友好所以实际性能非常好。链表实现栈则要额外维护节点之间的指针每个节点还要存next内存占用更大但好处是不用考虑扩容。队列就不一样了。如果用数组实现一个普通队列每次出队要让队头指针后移前面空出来的位置就浪费了。等队尾指针到数组末尾队头前面明明还有空位却没法再入队。所以数组实现队列通常要写成“环形队列”也就是让队尾指针到末尾时回到开头。环形队列的难点是区分“空”和“满”如果用size变量记录元素个数就简单很多如果只用两个指针就要空出一个位置来区分。这块是新手最容易绕晕的地方。链表实现队列则更直观一个head指针指向队头一个tail指针指向队尾。入队在tail后面挂新节点出队把head指向下一个节点。但要注意如果只有一个链表头指针出队可以O(1)入队却要遍历到链表尾部变成O(n)。所以标准做法是同时维护head和tail两个指针。这也是面试里很喜欢问的细节让你手写队列时一定要写出两个指针别只写一个。1.3 算法题里的角色定位栈和队列在算法题里各有一片主战场。栈的典型场景是“最近相关性”。括号匹配是最近一个左括号需要被最近的右括号闭合函数递归调用是后调用的先返回浏览器的前进后退也是栈编辑器的撤销操作同样是栈。更深一层单调栈用来处理“下一个更大元素”这类问题本质上也是利用栈顶的“最近”信息。如果你在题目里看到“相邻”“最近”“嵌套”“逆序输出”这些词第一反应就应该是栈。队列的典型场景是“顺序处理”。广度优先搜索BFS就是按层遍历天然适合队列树的层序遍历、无权图的最短路径、拓扑排序都会用到队列。还有滑动窗口最大值虽然最经典解法是单调队列但基础版也是用一个队列维护窗口内的元素。消息队列、线程池里的阻塞队列本质上都是在用“先进先出”做缓冲和削峰。把它们放一起学还有一个原因栈和队列可以互相实现。用两个栈可以拼出一个队列用一个队列可以倒腾出一个栈。这不是瞎折腾而是让你更深刻地理解“操作顺序”是由谁决定的。等你写完这两道题再看到“设计循环队列”“实现最小栈”这类题就不会觉得它们是外星题目了。2. 核心细节栈和队列的操作与实现要点2.1 栈的操作细节入栈、出栈、取栈顶栈的四个核心操作是push、pop、top或peek、empty。不同语言API叫法不同但逻辑一致。以Python为例日常刷题直接用列表模拟栈stack [] stack.append(1) # 入栈相当于 push stack.append(2) top stack[-1] # 取栈顶不删除 stack.pop() # 出栈返回栈顶并删除C里则要注意stack的pop()不返回栈顶元素想取值必须先用top()看栈顶再pop()。这是很多从Python转过来的人踩的第一个坑。还有一个细节判断栈空时不要习惯性写if stack []直接if not stack更简洁而且不会因为类型问题出bug。在C里也不要写stack.size() 0直接stack.empty()。栈的复杂度非常好记push、pop、top都是O(1)因为永远只动栈顶。空间复杂度看存储结构数组连续内存链表离散内存但渐进意义上都是O(n)。2.2 队列的操作细节入队、出队、取队首队列的核心操作是enqueue入队、dequeue出队、front取队首、back取队尾、empty。Python刷题最推荐用collections.deque因为它的左右两端操作都是O(1)from collections import deque q deque() q.append(1) # 队尾入队 q.append(2) front q[0] # 取队首 back q[-1] # 取队尾 q.popleft() # 队首出队为什么不用list模拟队列因为list.pop(0)的时间复杂度是O(n)它会把后面的所有元素都往前挪一遍。刷题时如果数据量小无所谓数据量一大就超时。deque底层是双向链表或分块数组两端操作都是O(1)所以才是正解。C里如果不想用std::queue也可以直接用deque或数组模拟。STL的queue默认基于deque操作已经封装好push、pop、front、back。同样注意pop()也不返回元素。队列的复杂度同样是O(1)。但要注意如果用数组实现普通队列而不做环形处理出队指针后移后前面的空间就废了摊还上来看并不划算。所以在手写时要么用环形数组要么用链表要么用deque总之不要让“队头前面的空间”白白浪费。2.3 手写实现时最容易翻车的三个地方第一空判断。无论是栈还是队列在pop/top/front之前都必须先确认非空。很多同学一紧张就忘了导致stack[-1]直接IndexError或者C里对空stack调用top()提前运行崩溃。写代码前先问自己如果这个结构是空的我的代码会怎样养成这个习惯能挡住80%的边界错误。第二栈的扩容。如果手写用数组实现栈初始化时要给一个初始容量比如cap 8。每次push前检查top cap - 1满了就扩容申请一块更大的空间把旧数据搬过去。扩容的均摊复杂度是O(1)因为扩容不是每次发生。这个点面试官很爱问不要只说“我直接new一个更大的数组”一定把“旧数据拷贝”这一步说出来。第三环形队列的指针移动。环形队列的入队出队指针移动不能简单“加1”要对数组长度取模。很多人写成tail (tail 1) % cap没问题判断空满时却乱了。建议使用size变量记录元素个数这样空和满的判断就很简单size为0是空size等于cap是满。别死记“浪费一个空间”的写法面试时用size方案更不容易错。下面用一个手写环形队列的样例代码帮你把上述细节串起来。注意我用的是数组加size的方案代码中留了扩容逻辑的注释实际刷题如果直接用deque就不用写这么复杂但面试手写时这个骨架能救你命class MyCircularQueue: def __init__(self, k: int): self.cap k self.arr [0] * k self.head 0 self.tail 0 # tail指向下一个可写入的位置 self.size 0 def enQueue(self, value: int) - bool: if self.isFull(): return False self.arr[self.tail] value self.tail (self.tail 1) % self.cap self.size 1 return True def deQueue(self) - bool: if self.isEmpty(): return False self.head (self.head 1) % self.cap self.size - 1 return True def Front(self) - int: if self.isEmpty(): return -1 return self.arr[self.head] def Rear(self) - int: if self.isEmpty(): return -1 return self.arr[(self.tail - 1) % self.cap] def isEmpty(self) - bool: return self.size 0 def isFull(self) - bool: return self.size self.cap这段代码里Rear取的是tail的前一个位置因为tail是指向“下一个空位”的。这个细节不写出来很容易错建议你亲手跑一遍跟普通队列对比一下指针的移动逻辑。3. 实操过程四道经典题直接带你跑一遍3.1 用栈实现队列题目编号是LeetCode 232。乍一看很绕栈是后进先出队列是先进先出怎么用一个栈实现队列呢答案是用两个栈。思路是这样的假设有两个栈inStack负责入队outStack负责出队。入队时直接push到inStack。出队时如果outStack为空就把inStack的所有元素全部倒到outStack里。因为inStack的栈顶是最后入队的元素倒到outStack之后outStack的栈顶就变成了最早入队的元素。这样再pop出来的顺序就是先进先出了。举个例子。入队1、2、3inStack从栈底到栈顶是[1,2,3]。现在要出队把inStack全部弹到outStackoutStack从栈底到栈顶变成[3,2,1]此时outStack.pop()得到1没问题。接下来如果又入队4直接进inStack。再出队时outStack还没空直接弹outStack得到2还是正确的。只有当outStack空了才需要再次把inStack倒过来。摊还复杂度是O(1)。为什么因为每个元素最多被“倒”两次一次进inStack一次倒到outStack然后出栈一次。平均到每次操作上确实是常数时间。很多面试官会追问这个别只答“均摊O(1)”要能把过程讲清楚。下面是完整的Python实现直接可跑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: 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) - int: 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) - bool: return not self.in_stack and not self.out_stack这里有两个小细节。第一peek只取队首不删除所以倒栈逻辑和pop一样但最后返回的是out_stack[-1]而不是pop()。第二empty不能只看in_stack因为可能元素都在out_stack里没被消耗完所以要两个栈都为空才算空队列。3.2 用队列实现栈LeetCode 225。有了上一题的经验这题你会觉得奇怪队列不是先进先出吗怎么实现后进先出的栈其实只需要一个队列配合“重新入队”的技巧就够了。核心思路每次push新元素都把它放到队尾然后把之前的所有元素依次出队再入队使新元素变成队首。这样队列的pop操作拿到的就是最新入队的元素模拟出了栈顶效果。举个例子。队列初始[]。push(1)队列[1]。push(2)先把2放到队尾[1,2]然后让1出队再入队得到[2,1]。此时队首是2相当于栈顶。push(3)放队尾[2,1,3]然后让2和1依次出队再入队得到[3,2,1]。pop()返回3完全符合栈的行为。代码也不复杂from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) size len(self.q) for _ in range(size - 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的时间复杂度是O(n)因为每次都要把前面的元素重新入队。pop、top、empty都是O(1)。为什么用deque因为popleft()是O(1)如果换成list模拟pop(0)是O(n)整个push就会变成O(n^2)直接超时。有人可能问不能用两个队列实现吗也可以但思路更绕。每次push往非空队列放pop时把前面n-1个元素挪到另一个队列剩下那个就是栈顶。但单队列的写法已经足够简洁刷题建议优先掌握单队列版本。3.3 有效的括号LeetCode 20。这道题是栈的入门题几乎每个训练营都会讲。题目是给你一个只包含()[]{}的字符串判断括号是否有效。为什么想到用栈因为括号匹配是典型的“最近相关性”问题。当遇到一个右括号时它必须匹配“最近一个尚未匹配的左括号”。这个“最近”正好是栈顶。算法流程如下遍历字符串遇到左括号就把对应的右括号压入栈。为什么要压右括号而不是左括号这样比较时可以直接用栈顶和当前字符相等判断不用再写map代码更简洁。遇到右括号时如果栈为空说明没有左括号可以匹配直接返回False如果栈顶不等于当前字符说明括号类型对不上返回False否则弹出栈顶。字符串遍历结束后栈应该为空。如果不为空说明还有左括号没被关闭返回False。完整代码如下def isValid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} # 右括号对应的左括号 for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack上面的写法是用pairs映射右括号到左括号。前面说的“压入右括号”是另一种写法def isValid(s: str) - bool: stack [] pairs {(: ), [: ], {: }} for ch in s: if ch in pairs: stack.append(pairs[ch]) else: if not stack or stack.pop() ! ch: return False return not stack两种写法都可以看你习惯。我推荐第二种因为左括号和右括号的对应关系写得很直观而且省去了查左括号的额外判断。需要注意的是if not stack or stack.pop() ! ch这个写法有副作用如果栈空短路求值不会执行stack.pop()所以是安全的但有些人读代码会不习惯你也可以拆成两行写更稳妥。这道题的边界情况很丰富输入)(栈空时遇到右括号直接False输入([]最后栈不空返回False输入([)]最后栈顶]对应的[但当前是)不匹配返回False。建议你把这三组用例都手动过一遍理解得更深。3.4 删除字符串中的所有相邻重复项LeetCode 1047。题目要求给出由小写字母组成的字符串反复删除两个相邻且相同的字母直到没有相邻重复项为止。这题是栈的另一个典型应用相邻消除。为什么用栈因为每次消除完成后新的相邻关系可能诞生这跟“消消乐”很像而栈天然保存“待比较的前一个元素”。思路很简单遍历字符串如果当前字符和栈顶相同就弹出栈顶表示这一对相邻重复项被删掉否则把当前字符入栈。遍历结束后栈里剩下的字符按顺序拼接就是答案。def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)举个例子输入abbaca。遍历a入栈栈为[a]。第二个b入栈栈为[a,b]。第三个b和栈顶相同弹出b栈为[a]。第四个a和栈顶相同弹出a栈为空。第五个c入栈栈为[c]。第六个a入栈栈为[c,a]。最后返回ca。这个代码看起来简单但有个细节值得说if stack and stack[-1] ch一定要先判断stack非空。否则当栈为空时访问stack[-1]会抛IndexError。很多人一紧张就把and写漏了。这题还有另一种非栈写法用字符串本身当栈直接在原字符串上做双端指针。但对于训练营的初学者我建议先用标准栈写法把“相邻消除”的模型建立起来之后再优化也不迟。4. 常见问题与排查实践4.1 空栈/空队列的边界问题怎么防刷栈和队列的题最常见的崩溃原因就是空结构操作。C里空栈调用top()是未定义行为Python里空列表访问[-1]直接报错。以下几点我每次带训练营都会强调在pop/top/front之前永远先确认非空。如果题目逻辑上能保证非空那就加一行注释说明如果不能就写if not stack或if stack.empty()分支处理。用“哨兵”思想简化边界。比如在栈中先压入一个特殊值或者使用虚拟头节点能减少很多空判断。但不要滥用否则代码可读性会变差。写测试用例时一定覆盖空输入。、()、(、)(这些都要过一遍。我自己刷题时养成的习惯是先写正常用例再写边界用例最后写极端用例比如输入长度正好为1。4.2 复杂度分析为什么总被问栈和队列的操作都是O(1)这是它们的卖点。但面试时题目往往不会直接给你一个栈而是让你设计一个数据结构表面上某个操作是O(n)实际上均摊O(1)。“用栈实现队列”就是典型例子。这里的“摊还分析”可以这样理解你每次pop时可能要把inStack所有元素倒到outStack这个瞬间看起来是O(n)。但每个元素只会被倒一次之后它会从outStack中被弹出。把整个操作序列看成一个整体平均每次操作还是O(1)。就像你平时不怎么打扫房间周末花两小时大扫除按一周算平均每天打扫的时间很少。同样的道理也适用于动态数组扩容。容量满了就拷贝全部元素单次push看起来O(n)但扩容频率极低均摊下来O(1)。所以不要一看到循环里有while就慌先判断它“平均”触发多少次。4.3 单调栈、阻塞队列、消息队列什么时候学热词里总看到“单调栈揭秘”“阻塞队列”“消息队列”很多人刚学完栈和队列就急着去看结果被劝退。这里我帮你理一下层次。单调栈是栈的高级应用主要用于解决“下一个更大元素”“接雨水”“柱状图中最大矩形”这类问题。它和普通栈的区别是在入栈时维护栈内元素的单调性单调递增或递减。这个知识点适合在栈的经典题刷完后再学Day10 part01先不用碰。阻塞队列属于并发编程里的概念。线程池的任务队列就是阻塞队列它比普通队列多了“当队列为空时消费线程阻塞等待当队列满时生产线程阻塞等待”的能力。这就牵扯到锁、条件变量、线程安全是操作系统和并发编程的内容不是算法题里的普通队列。消息队列则是分布式系统里的通信组件比如RabbitMQ、Kafka。它的核心虽然是队列但重点在“跨进程通信”“持久化”“削峰填谷”面对的是网络消息而不是内存里的数据。搞清这三者的区别你看到相关热词就不会再觉得“怎么队列还能这么复杂”了。它们都是建立在队列这个基本模型上的但应用层完全不同。4.4 快速查错的小技巧栈和队列相关的题错误的模式很固定我总结了三个排查步骤第一画状态图。遇到“用栈实现队列”这种抽象题目不要只在脑子里转直接在纸上画两个栈把元素一个个移动画出来。我见过太多人卡壳是因为没画图硬想。画一次之后代码几乎是照着自己画的步骤翻译。第二打日志看每一步。Python里可以直接在循环里加print(stack)观察栈的变化看它和预期是否一致。不要觉得这样很笨调试本来就是试错的过程。等你熟练掌握后自然会去掉这些print。第三用最小用例跑一遍。不要一开始就用很长的测试用例例如“有效的括号”可以先跑()再跑()[]{}然后跑([)]最后跑空字符串。最小用例能快速定位是逻辑错误还是边界错误。我推荐一个小技巧每一步操作后把栈顶和栈大小都打出来通常问题就出现在“栈状态和预想不一致”的瞬间。我在实际训练营带练时发现Day10其实是一个分水岭。有人觉得栈和队列太简单直接跳过去做后面的“单调栈”然后被虐得信心全无有人死记代码过两天再写“删除相邻重复项”又想不起来。我的建议是不要只背模板逼自己说清楚“为什么这题该用栈为什么那题该用队列”。栈就盯住“最近相关”和“相邻消除”队列就盯住“先进先出”和“层序处理”。把这个判断练成本能后面遇到再复杂的变种你也能一眼看出核心结构。如果你卡在这一节别灰心明天part02多半是循环队列和双端队列到时候你会发现今天把两个结构互相实现玩明白了后面全是顺水推舟的事。