1. 先从标题里的三个关键词说起算法入门阶段栈、队列、双向队列这三个词几乎绕不开。我最早接触它们的时候心里是很不以为然的——“无非就是一个列表限制一下进出顺序”真正开始刷题才发现限制进出顺序这件事本身就是算法设计的核心。很多看起来复杂的题目比如括号匹配、浏览器前进后退、窗口内最大值、任务调度底层抽象出来都是这三个东西在干活。可以说掌握好其中任意一个都能直接解决一批实用场景把三个串起来理解就相当于拿到了算法入门的钥匙。这篇文章就围绕标题展开从原理拆解到 LeetCode 真题精讲再到我实际刷题时踩过的坑完整复盘栈、队列、双向队列怎么用、什么题目用什么结构、代码怎么写才不容易出边界问题。我不打算只贴代码而是把每一道题的思考链路、备选方案、复杂度分析和易错点都讲透适合刚准备系统性刷算法的读者也适合已经刷过一点题但遇到同类题还是卡壳的人。1.1 为什么这三兄弟值得最先攻克先给你吃一颗定心丸栈、队列、双向队列本身都不难难的是“什么时候想到用它们”。这背后其实是一种经验积累就像你学开车倒车入库不难难的是到了陌生停车场能快速判断该用哪种姿势停进去。从数据结构的角度看这三样东西是所有高级算法的地基。树的深度优先遍历本质上是递归和栈的配合树的广度优先遍历本质上是队列的逐层扩展而动态规划、单调栈、滑动窗口这些进阶专题更是直接建立在“用一个维护有序性的结构”这一思想之上。如果你刚开始学算法优先把这三个基础结构吃透收益远大于一开始就啃图论或动态规划。再来聊一个很实际的问题为什么面试和刷题平台这么爱考它们因为这三样东西实现简单、约束清晰很容易把考察点聚焦到“抽象能力和边界处理”上。比如一道有效的括号类型题骨架代码不到二十行但空栈判断、括号顺序、异常输入这些细节全部暴露在明面上。基础结构见得多了你对代码的敏感度是肉眼可见提升的。1.2 这篇实战笔记适合谁看如果你是完全没接触过数据结构的新手也别怕。我会尽量用生活化的口吻把原理讲清楚比如把栈类比成一摞盘子把队列类比成排队打饭。每个概念都会先讲“是什么”再讲“为什么选它”最后落到代码。如果你已经刷过部分题目但总觉得思路混乱那这篇笔记的第四章节和第五章节会更适合你。里面记录了很多我实际排查问题时的习惯比如怎么用极端用例验证、怎么从 O(n²) 的暴力解法过渡到 O(n) 的优化解法、怎么在不同语言里避开底层实现陷阱。这些东西不是教科书上会写的但恰恰是实战中决定成败的细节。2. 三种数据结构的原理拆解与选型思路先花点时间把基础概念过一遍。很多读者可能会觉得这部分多余但根据我的经验十道题里有五道出错根源都是概念细节没咬清。比如“栈顶在哪”“队列头部在哪”“删除时到底该判空还是不判空”这些看似琐碎实则是代码正确性的命门。2.1 栈后进先出最擅长处理嵌套与回溯栈是一种受限的线性表只允许在同一端进行添加和删除操作这个端被称为栈顶另一端叫栈底。它的核心规则只有一句话后进先出。打个比方你往一个开口向上的筒子里塞书先放进去的书会被压在最底下最后放进去的书在筒口。取书的时候只能先把最上面的拿出来。这种“先来后到完全颠倒”的特性在计算机世界里的应用极其广泛。场景为什么用栈函数调用嵌套调用的返回地址需要按逆序恢复括号匹配最近的左括号必须匹配最近的右括号撤销操作撤销的顺序是操作的逆序深度优先遍历需要沿着一个分支走到底再回溯在 Python 里面最简单的栈实现直接用一个 list 就够了。因为 list 自带的 append 和 pop 方法都作用在尾部而尾部就是栈顶。stack [] stack.append(1) # 压栈 stack.append(2) # 压栈 top stack[-1] # 查看栈顶不弹出 value stack.pop() # 弹出栈顶得到 2关键点在于 Python 的 list 尾插尾删是摊还 O(1) 的所以不用担心性能问题。但如果拿 list 当队列用做头部删除操作那就要格外小心了因为这是 O(n) 级别操作原因后面细讲。2.2 队列先进先出天然契合顺序消费队列的规则和栈正好相反添加在队尾删除在队头。谁先来谁就先被服务这和生活中排队买票的直觉完全一致。队列最常见的典型场景包括任务调度、消息队列、树的广度优先遍历、缓存队列。它解决的核心问题是“把无序到达的元素按照到达顺序做公平处理”。在纯 Python 里我建议只用 collections.deque 来实现队列而不是 list。原因很简单list 头部插入或删除需要把后面所有元素整体平移数据量一大性能直接就崩了。from collections import deque q deque() q.append(1) # 队尾入队 q.append(2) head q.popleft() # 队首出队得到 1deque 的底层是双向链表和数组结合实现的头尾增删都能做到 O(1)。正因为如此它才成为 Python 里做队列和双向队列的主流选择。2.3 双向队列栈与队列的缝合怪也是单调队列的载体双向队列也就是双端队列允许在头和尾两端分别进行插入和删除操作。你可以把它理解成“栈和队列的合体”既可以当栈用也可以在两端同时操作。更关键的是它是实现“单调队列”的天然载体。什么叫单调队列就是队列内部元素始终保持单调递增或单调递减。滑动窗口最大值、滑动窗口平均值、移动区间最值等问题都是依赖单调队列在 O(n) 时间内完成的。很多人一开始不理解为什么需要双端队列因为单调队列在滑动窗口运作过程中既要从尾部弹出旧的小值又要从头部移除离开窗口的过期元素。这种“头部淘汰 尾部维护”的双向操作用普通队列根本做不了用两个栈硬模拟又太别扭。所以deque 几乎是这类题目的标准答案。from collections import deque dq deque() dq.append(1) # 右边入 dq.appendleft(2) # 左边入 left dq.popleft() # 左边出 right dq.pop() # 右边出2.4 复杂度对比与选型决策在 Python 里三种结构最直观的选型对照表如下。操作list 栈deque 队列deque 双向队列尾部添加O(1)O(1)O(1)尾部删除O(1)O(1)O(1)头部添加不支持不推荐O(1)头部删除O(n)O(1)O(1)选型原则其实很简单只需要在尾部进出用 list这就是栈。需要在头部出、尾部进用 deque这就是队列。需要在两端都增删也只用 deque。一旦确定了结构算法题的复杂度下限也就基本定了。这也是为什么刷题时我会先问自己一句这个题目里的删除动作发生在哪一端想清楚这问题往往比急着写代码更重要。3. LeetCode 真题精讲与代码实操下面进入这篇文章的重头戏。我挑了四道很有代表性的实战题覆盖三种结构的核心用法。每一道题我都会先讲原始思路再讲优化思路最后给出可运行的代码并标注时间复杂度。这几道题我在不同阶段反复刷过每次都有新体会所以值得细讲。3.1 栈的入门题有效的括号题目背景是这样的给定一个只包含(、)、{、}、[、]的字符串判断字符串是否有效。有效要求是左括号必须用相同类型的右括号闭合并且按正确的顺序闭合。我第一次做这题时第一反应是用计数器。比如数左括号和右括号的数量再比较相等。但很快就发现问题([)]这种字符串左右括号数量是相等的但它并不合法。原因就是括号的嵌套顺序错了。于是我想到了栈这几乎是最自然的解法。遍历字符串时遇到左括号就压栈遇到右括号就检查栈顶是否匹配如果匹配弹出栈顶如果不匹配或者栈为空直接判定非法。遍历结束后栈必须为空否则说明还有未闭合的左括号。def is_valid(s: str) - bool: stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping.values(): # 左括号入栈 stack.append(ch) else: # 右括号必须和栈顶匹配 if not stack or stack[-1] ! mapping[ch]: return False stack.pop() return not stack这里有两个地方特别容易踩坑。第一右括号出现时先判断not stack。有一种情况是输入是])直接以右括号开头此时栈是空的如果不先判空就去访问stack[-1]会直接报错。第二最后一行的return not stack不能写成return True。因为如果输入是(()遍历完之后栈里还残留一个左括号这就是不合法的。很多人第一次都会在这里翻车。时间复杂度是 O(n)空间复杂度最坏也是 O(n)。做完这道题你可以继续去思考一个变种如果允许三种括号互相嵌套但交叉不合法解法完全一样。这也是栈在表达式求值、HTML 标签配对等场景中的基础用途。3.2 栈的进阶题每日温度这道题的要求是给你一个每天温度的列表对于每一天要计算需要等多少天才能等到一个更高的温度。如果之后都没有更高温度结果为 0。最直觉的暴力解法是双重循环对每一天向后扫描找到第一个更大的值。复杂度是 O(n²)一旦数据量上到十万量级基本不可用。我当时想到的优化方案就是单调栈。单调栈是一种特殊的栈栈内元素自底向上保持某种单调性比如依次递减。这道题我们想找的是“右边第一个比当前大的元素”所以维护一个递减栈。具体流程如下遍历温度数组同时把索引压入栈中。每次遇到一个新温度就循环查看栈顶索引对应的温度如果当前温度比栈顶温度高说明栈顶那天等到了升温日于是弹出栈顶并记录间隔否则把当前索引入栈。def daily_temperatures(temperatures: list[int]) - list[int]: n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: prev_index stack.pop() ans[prev_index] i - prev_index stack.append(i) return ans理解这段代码有两点很关键。一是栈存的是索引而不是温度值。为什么存索引因为答案需要间隔天数也就是索引之差如果只存值最后计算答案时还要回头找位置反而麻烦。二是每个元素只会入栈一次、出栈一次所以整体时间复杂度是 O(n)而不是 O(n²)。这也是单调栈最迷人的地方用空间换时间每个元素访问两遍但摊到了线性。这道题还有一个常见变种求“右边第一个比当前元素大的值”。这时候只需要把答案改成temperatures[stack.pop()]即可逻辑完全一样。把单调栈练熟之后直方图最大矩形面积、接雨水、下一个更大元素这类题会有一种豁然开朗的感觉。3.3 队列与栈的配合用两个栈实现队列这道题的要求非常明确仅使用两个栈实现一个先入先出的队列队列支持push、pop、peek、empty四个操作。为什么要用两个栈因为单个栈做不到先入先出。栈后进先出队列先进先出这两个规则是矛盾的但两个栈可以通过来回倒腾抵消这个矛盾。思路是这样的保持一个“入栈”和一个“出栈”。所有入队操作只放到入栈里相当于暂时压着出队操作时如果出栈为空就把入栈里的所有元素一次性倒进出栈这时候元素顺序正好反转最先入栈的元素就跑到了出栈顶部。这碗水倒好了之后后续出队只需要从出栈直接弹出即可。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) - None: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())有个细节值得单独说为什么要判断if not self.out_stack才触发转移因为如果出栈还有余量直接弹出它栈顶的元素就是当前队列最早入队的那一个。此时贸然把入栈元素倒下来反而会把顺序打乱。复杂度方面单看一次pop最坏情况需要把 n 个元素全部倒腾一遍看起来是 O(n)。但摊还下来每个元素最多被压入出栈一次、弹出一次所以平均每次操作都是 O(1)。这种“摊还 O(1)”的思路在动态数组扩容、并查集路径压缩里还会反复出现值得提前适应。做完这道题可以试着反过来思考一下用两个队列实现一个栈。思路也类似但细节更反直觉核心是利用另一个队列做缓冲区。理解这两种“互相模拟”你对数据结构特性的体会会深很多。3.4 双向队列的应用滑动窗口最大值这道题是双向队列的典型题目也是单调队列思想最经典的落地之一。题目描述是给定一个数组和一个窗口大小 k窗口每次向右滑动一格返回每个窗口中的最大值。暴力解法当然简单对每个窗口都扫描 k 个元素复杂度 O(nk)。如果数组有十万个元素k 是五万这种复杂度就直接不可接受了。我的优化思路从“冗余信息”入手窗口向右滑动时如果某个较大的元素比另一个较小的元素晚离开窗口那么这个较小的元素就没有存在价值了因为它永远不可能成为窗口最大值。于是可以在遍历过程中维护一个单调递减的双端队列队列里存的是数组下标并且保证下标对应的值递减。from collections import deque def max_sliding_window(nums: list[int], k: int) - list[int]: dq deque() result [] for i in range(len(nums)): # 新元素从尾部进入先弹掉所有比它小的旧元素 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 移除已经滑出窗口的过期头部 if dq[0] i - k: dq.popleft() # 窗口成形后头部就是当前窗口最大值 if i k - 1: result.append(nums[dq[0]]) return result我要特别讲一下三个细节。第一个细节为什么弹掉所有比当前值小的旧下标因为当前值更大而且位置更新这就意味着那些旧下标在之后任何一个窗口里都不可能成为最大值。留着它们只会增加无用的比较。第二个细节为什么存下标而不是直接存值因为只有存下标才能判断元素是否已经滑出窗口。判断条件用的是dq[0] i - k意思是头部下标已经不在当前的窗口范围内必须弹出。第三个细节为什么这个解法是 O(n)因为每个下标最多入队一次、出队一次全程没有嵌套循环的重复遍历只是每个元素被处理了常数次。这道题做完之后可以顺手把“求每个窗口的最小值”也练一遍只需要把单调递减改成单调递增即可代码逻辑几乎一模一样。单调队列这套思路还能扩展到最大值、最小值混合查询的问题比如两边各维护一个单调队列来同时求最大和最小差。4. 常见问题与排查技巧实录刷算法题最让人沮丧的不是看不懂题解而是明明按题解抄了一遍却还是报错或者看着通过了但完全不知道哪里可能出问题。这一节把我实战中频繁踩过的坑和排查经验整理出来很多都是文档里不会提醒你的。4.1 边界条件与空值处理栈类题目最容易出问题的地方集中在栈为空时的访问。无论是取栈顶、弹栈、还是比较栈顶元素都要先考虑栈是否为空。在我自己调试的过程中列表越界报错占比相当高尤其是有效括号类题目和单调栈类题目。一个比较稳的排查习惯是在代码执行前先列一遍极端输入比如空字符串、单个字符、全部相同元素、目标值在开头或结尾。把这些用例喂进代码如果都没问题再提交一次基本就能过滤掉大部分边界错误。对于滑动窗口类题目还需要额外关注窗口还没成形的那段时间。代码里的if i k - 1就是在处理这个边界窗口没凑满之前不应该产生输出。有时候你忘了这个判断结果数组会多出前 k-1 个窗口答案就会错得莫名其妙。4.2 语言实现上的性能细节用 Python 刷题我一直强调少用 list 做头部操作。list.pop(0)看起来也能用但底层会把后面所有元素向前移一位复杂度是 O(n)。一旦数据量上来超时就是这么来的。另一个常见性能问题是频繁使用len()和切片。比如在栈里用stack[-1]是安全的但如果你为了判断栈顶写了if len(stack) 0 and stack[-1] xxx也行就是略啰嗦更危险的是把列表整个复制一遍比如stack stack[:-1]这种操作会产生新列表性能差很多。要用就用stack.pop()。deque 虽然头尾都是 O(1)但访问中间元素是 O(n)。有些滑动窗口题会试图用dq[0]和dq[-1]以外的方式访问内部元素这在性能上是非常不推荐的。再说一个隐藏细节如果你同时维护多个栈或多个队列要特别注意每个栈的作用域和初始化位置。很多题目需要每一轮循环都重新初始化一个栈比如“每日温度”这类题只需要一个全局栈而“用栈模拟括号拆分”之类的问题可能要每层递归都重新建栈搞混了很容易出现逻辑短路。4.3 我常用的调试与思考路径我现在刷题很少直接写代码而是先花几分钟把题目翻译成三句话输入是什么、输出是什么、过程中的关键操作是什么。然后把关键操作用自然语言描述出来。比如滑窗最大值关键操作就是“加一个、删一个、取最大”。一旦能用自然语言说清楚选什么数据结构就呼之欲出了。拖慢我刷题速度的其实不是写代码而是对“抽象度”的把握。例如有一类括号匹配变种题要求判断合法性看起来复杂但本质上还是“栈 最近配对”。先把题目映射到已知模式再思考有没有变体这是很好的解题习惯。调试时我会在关键位置打印栈或队列的状态。比如每日温度题里打印每一步入栈、出栈后的栈内容很快就能发现是不是温度比较方向写反了或者下标差算错了。等代码运行正确后再把打印语句删掉。这种过程虽然笨拙但对新手非常友好。5. 刷完这些题我想再补几句真把这几类题做过一遍之后我最大的感受是理解数据结构的特性比记住某个题的模板重要得多。栈、队列、双向队列都只是工具工具没有感情关键是你拿它们解决什么问题。我之前在一道非常容易麻痹大意的题上栽过跟头。题目看过去很像有效的括号所以我直接套了配对栈的模板写了二十多行代码结果提交之后发现没有考虑括号的优先级种类不得不推翻重写。这件事之后我就养成了一个习惯拿到题先不要急着写写试试而是先想清楚“它是这一类题的变体还是本质就是这一类题”。前者是分析后者是经验。此外我强烈建议刷完每道题之后隔两天重新做一遍。第一遍是学习第二遍是巩固第三遍才是真正变成自己的。这种“做题-复盘-重做”的循环比大量刷新题更有价值。因为它会让你注意到第一次忽略的边界也会让你察觉到哪些步骤是靠记忆硬写的、哪些是真理解的。如果你是非科班或者刚开始接触数据结构不必求快。一天吃透一道题比一天扫码式过十道题要强得多。等你真正做到两周以后再回头翻这些题你会发现那些当初让你头皮发麻的单调栈、双端队列其实都在同一个框架里转。到那时你的算法基础就算真正打下来了。