企业官网建设流程全解析

刚入坑算法刷题的时候，我有一段时间特别迷茫：栈、队列、双向队列三个概念都认识，真到了做题的时候却不知道什么时候用哪个。“有效括号”看着该用栈，“滑动窗口最大值”又说是双向队列，偶尔遇到“用队列实现栈”这种题更是觉得像是在绕口令。后来我把这三种容器放在一起啃了一遍，再把对应的经典真题逐个手写、画状态图、对比复杂度，才算是把这块地基打扎实了。

这篇文章就以栈、队列、双向队列为主线，串联几个我练过很多遍的真题题型，讲清楚三者的运作逻辑、语言层面的实现差异，以及那些容易让人卡半天的边界细节。如果你刚学完基础语法，正准备开始系统性刷题，或者刷了十几道题但遇到同类题还是发怵，这篇文章应该能帮你省不少时间。我不会把题目原封不动抄出来，而是用自己的话讲题目核心，然后给出可直接参考的实现思路和代码。

1. 别急着背模板：三种线性容器到底是干什么的

很多人学数据结构喜欢直接背结论：栈是后进先出，队列是先进先出，双向队列是两头都能进出。背是背下来了，做题还是不会。差别在于缺少一层“这玩意儿对应现实里什么场景”的直觉。我建议先忘掉术语，想清楚三个生活场景。

1.1 栈 = 一摞盘子，最近放的永远先被拿走

栈的核心特征就一个：Last In First Out。你把它想成一摞盘子，洗碗的人把洗好的盘子一个个叠上去，用的时候一定是从最上面拿。后放上去的盘子反而先被拿走，这就是“后进先出”。

计算机里到处都是这种结构。函数调用时的调用栈，每一个函数开辟一个栈帧，当前正在执行的函数永远在栈顶；撤销操作也是一个典型场景，编辑器里记录的是一连串操作，撤销的时候撤销的是最近的一次操作，而不是最开始那次；浏览器的后退键同样是栈，你点击页面A、B、C，后退的时候是先回到B再回到A，而不是直接跳回首页。

刷题时，只要题目里出现“匹配最近的”、“撤销最近一次”、“回退到上一个状态”这类需求，你脑子里第一反应就应该是栈。

1.2 队列 = 只有一个门，先来的人先交费

队列的规则是First In First Out。排队买单，先来的人先出队，后来的人排在队尾。这和栈正好相反，进出不在同一个方向，一头进一头出。

队列映射到工程场景也非常多。打印任务按提交顺序排队；异步任务调度里，消息先到先处理；BFS（广度优先搜索）也是靠队列一层一层往外扩展的，先访问到的节点先被扩展。遇到“按顺序处理”、“一轮一轮来”一类的问题，队列就是顺手的工具。

1.3 双向队列 = 队头和队尾都能排队，也能离队

双向队列英文叫 deque，全称 double-ended queue。它相当于把队列的两个门都打开了，头部和尾部都可以插入元素，也都可以删除元素。

生活中比较接近的例子是“插队”被严格限制的通道：你可以从队伍最前面进入，也可以从最后面进入，离开的时候前后都能走。更常见的类比是某些场景里，新到的任务优先级高，就可以直接放到队头优先处理。

为什么要单独学它？因为很多问题只会用“先进先出”这一个规则搞不定。比如滑动窗口最大值，既要模拟元素按顺序入队出队，又要在队尾把影响结果的“弱者”提前淘汰掉。这种两头都要操作的需求，直接用双向队列比拿栈去拼凑优雅得多。

1.4 一张表区分什么时候想起哪种结构

这个表是我自己整理的，刷题时遇到一个题先别急着写代码，看看题目里的关键词更接近哪一列。比如题目说“栈的压入、弹出序列”，关键词是“栈”，那就围绕栈顶操作来想；题目说“窗口依次移动”，关键词是“滑动”，那大概率往队列、双向队列那边靠。

2. 语言层面怎么选：不同语言的容器实现差异很大

概念清楚了，落到代码层面还有个坑：不同语言提供的“栈”和“队列”实现方式和性能差异不小。我见过不少朋友用C++却习惯先定义一个vector，然后只在尾部push_back、pop_back，这样固然能实现栈语义，但容易让代码看起来更复杂；也见过用Python的list模拟队列，结果pop(0)时间复杂度是O(n)，一跑大数据就崩。这些差异提前知道，能少走很多弯路。

2.1 C++：stack 是容器适配器，别被它的“真身”骗了

C++的std::stack和std::queue本质上是容器适配器，它们自己不存储数据，而是包装了另一个底层容器。

• std::stack默认基于std::deque，也可以指定基于std::vector或std::list。
• std::queue默认也基于std::deque。
• std::deque本身是双端队列，支持两端快速插入删除，随机访问性能不如 vector，但大多数算法场景关心的是头尾操作，这一点正合适。

用的时候记住一个原则：如果你需要栈或队列语义，直接用标准库容器适配器，不要手动用vector去“假装是栈”。适配器把不合适的接口封掉了，你的代码意图更清晰，也不容易误操作。

2.2 Python：list 当栈很方便，deque 才是真双向队列

Python里最常见的错误就是用list当队列。从头部弹出pop(0)是O(n)操作，每次都要把后面所有元素往前挪。但list当栈用没问题，append和pop()都是O(1)摊还复杂度。

需要队列或双向队列语义时，用collections.deque。它底层是块状链表，头部popleft()、appendleft()和尾部的append()、pop()都是O(1)。需要注意两点：

1. deque随机访问不方便，不要拿它当数组遍历。
2. 在deque中间插入元素是O(n)，不要没事往中间插。

写算法题时，我的习惯是：栈用list，队列/双向队列用collections.deque，基本能覆盖绝大部分需求。

2.3 Java：Stack 类有历史包袱，ArrayDeque 更常用

Java 早期提供了java.util.Stack，但这个类继承自Vector，所有方法都加了同步控制，单线程算法题里用纯属“背着重量上考场”。而且它还暴露了get(int)这类不属于栈语义的方法，容易诱导写出不规范代码。

我推荐使用ArrayDeque来同时实现栈和队列。它实现了Deque接口，作为栈时用push/pop，作为队列时用offer/poll，性能也更好。

Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.pop(); Deque<Integer> queue = new ArrayDeque<>(); queue.offer(1); // 入队 queue.poll(); // 出队

2.4 一句话总结语言选型

选容器的核心不是“这门语言有没有栈类”，而是“哪一组的操作复杂度符合我的需求”。头尾操作需要O(1)，选deque系；只操作局部尾部，选list/vector系就行；需要随机按下标访问，老老实实选数组，别硬套栈或队列。

3. 栈的真题精讲：从“有效的括号”到“最小栈”

栈的经典题很多，我挑了三个最能体现栈本质的题来说：括号匹配、最小栈、用栈实现队列。这三个题递进关系很强，前两道是“用栈模拟天然行为”，后一道是“用两个栈互相配合改变顺序”。

3.1 有效的括号：为什么栈天然适合对称匹配

题目大意很好懂：给你一个只包含( ) [ ] { }的字符串，判断它是不是合法的括号序列。比如([]{})合法，而([)]不合法。

暴力做法可能是不断找成对的括号删掉，但效率差。更自然的思路是：扫描字符串时，遇到左括号就“记住”它，遇到右括号就必须和“最近记住的那个左括号”匹配。

注意关键词“最近记住的那个左括号”——这就是栈的典型使用场景。新遇到的右括号需要匹配的一定是最近一个尚未匹配的左括号，这是典型的后进先出。

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

我刚开始写这个题时犯了个低级错误：遇到右括号后没有判断栈是否为空就直接去stack[-1]，结果空栈报错。边界条件“保证栈不为空再接栈顶”在栈类题目里永远要写在前面。return not stack这个收尾也很关键，如果遍历完栈里还有左括号，说明有括号没匹配上。

3.2 最小栈：辅助栈不存状态，存的是“历史最低点”

题目要求设计一个栈，除了常规的push、pop、top，还要支持查询栈内最小元素的getMin，要求所有操作都是O(1)。

如果只用一个普通数组，想要O(1)拿到最小值几乎不可能，因为一旦当前最小值被弹出，你就不知道下一个最小值是多少。除非牺牲空间，额外记一份状态。

思路是：再开一个“辅助栈”，和主栈保持等长。每push一个元素时，辅助栈也push一个元素，这个元素值是“从主栈栈底到当前栈顶这一段里的最小值”。两个栈同步增长、同步弹出，getMin直接看辅助栈的栈顶。

class MinStack: def __init__(self): self.stack = [] self.minStack = [] def push(self, val): self.stack.append(val) if not self.minStack or self.minStack[-1] > val: self.minStack.append(val) else: self.minStack.append(self.minStack[-1]) def pop(self): self.stack.pop() self.minStack.pop() def top(self): return self.stack[-1] def getMin(self): return self.minStack[-1]

这里有个容易纠结的点：辅助栈为什么每次都要跟着压一个值，而不是只在遇到更小值时压一次？因为如果只在更小值出现时压栈，那么弹出时就得比较主栈栈顶和辅助栈栈顶是否相等，决定要不要连辅助栈一起弹。等长同步版本虽然多占一点空间，但逻辑简单不容易错。初学者我建议先写等长版本，理解了之后再尝试压缩版本。

注意：判断条件写成minStack[-1] > val还是>= val都行，区别只在于相同最小值出现时辅助栈压入的是新值还是旧值。推荐用>，配合等长版本时语义最清楚：辅助栈栈顶永远是“当前阶段的最小值”。

3.3 用栈实现队列：两次翻转解决顺序问题

这是一个非常经典的思考题：只有栈的API，却要模拟队列先进先出的效果。栈是后进先出，队列是先进先出，顺序正好相反，那怎么办？

思路是用两个栈：一个inStack专门接收新来的元素，一个outStack专门负责弹出。push时直接往inStack放，pop时如果outStack为空，就把inStack里的所有元素依次弹出并压入outStack，这相当于把顺序翻转了两遍，最后拿到的就是最早进来的元素。

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

你可以手动模拟一遍：连续push(1, 2, 3)，此时in_stack = [1, 2, 3]，栈顶是3；第一次pop时，把in_stack里的元素全部倒进out_stack，out_stack变成[3, 2, 1]，栈顶是1，正好是第一个入队的元素。

这个解法看似每次倒转都要花O(n)，但摊还分析下来是O(1)：每个元素最多被推入in_stack一次、从in_stack弹出一次、压入out_stack一次、再从out_stack弹出一次。真正恍然大悟的点在于：栈的“反转”能力可以用两次反转抵消，得到原来的顺序。这个方法在很多题里都能复用，比如字符串翻转相关的栈操作。

4. 队列的真题精讲：两个方向上的“用队列实现栈”

栈和队列之间经常互相模拟，这本身就是理解两种结构特性的好办法。上一节讲了用栈实现队列，这一节反过来，用队列实现栈，再看一看循环队列的实现细节。这两道题做下来，你对“进出方向”这件事的理解会深一层。

4.1 用队列实现栈：入栈时调整，还是出栈时调整

题目要求：用队列模拟栈，实现push、pop、top、empty。

最容易理解的办法是“入栈时直接调整顺序”。用一个队列，每次push新元素后，把前面已经存在的元素依次挪到队尾，这样新元素就在队头。出栈时直接从队头取即可。

from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x): self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self): return self.q.popleft() def top(self): return self.q[0] def empty(self): return not self.q

这段代码的关键是for _ in range(len(self.q) - 1)这里的循环次数要在append之后立刻取，因为循环过程中队列长度在变化。每次把队头元素弹出再放到队尾，等于把原来的元素全部在队里“转了一圈”，刚入队的x自然就转到了队头。

这里就引出一个很值得记住的感悟：栈和队列的互相模拟，本质上都在调整数据的顺序流向。用两个栈实现队列，是用“两次反转”；用一个队列实现栈，是用“循环搬移”。表面是数据结构题，实际是“顺序重排”思维的训练。

4.2 设计循环队列：边界条件就是这道题的考点

设计循环队列时，常见的坑是“空”和“满”的判断。如果你用两个指针front和rear，队列满时指针会绕一圈回到头，这时候front == rear既可能是空，也可能是满，不额外加标记根本无法区分。

我的解决办法是用一个独立的size字段记录当前元素个数，彻底绕开二义性。数组大小固定，每次插入位置为(head + size) % capacity，每次删除则让head = (head + 1) % capacity，同时更新size。

class MyCircularQueue: def __init__(self, k): self.data = [0] * k self.head = 0 self.size = 0 self.capacity = k def enQueue(self, value): if self.isFull(): return False self.data[(self.head + self.size) % self.capacity] = value self.size += 1 return True def deQueue(self): if self.isEmpty(): return False self.head = (self.head + 1) % self.capacity self.size -= 1 return True def Front(self): return -1 if self.isEmpty() else self.data[self.head] def Rear(self): if self.isEmpty(): return -1 return self.data[(self.head + self.size - 1) % self.capacity] def isEmpty(self): return self.size == 0 def isFull(self): return self.size == self.capacity

写这道题不要担心代码不够“优雅”，核心是别把下标算错。我常用的验证方式：用一个大小为3的循环队列，依次执行 enQueue 4次，断言前3次成功、第4次返回False；再执行 deQueue，断言Front返回第二个入队的元素。这种小用例跑一遍，边界基本就稳了。

4.3 队列的现实映射：任务调度和BFS

如果你觉得设计循环队列偏“造轮子”，那可以看看队列更自然的应用：广度优先搜索（BFS）和任务调度。

BFS遍历二叉树时，先把根节点加入队列，然后每次弹出一个节点，把这个节点的子节点加入队尾。因为队列先进先出，所以第k层的节点一定比第k+1层的节点先被访问，这就是“按层遍历”的由来。

工程里的消息队列就更直接了：生产者往队尾放消息，消费者从队头取消息，天然解耦了生产速度和消费速度。理解这点之后，再看任何“排队处理”的算法题，你会本能地想到队列。

5. deque 的进阶用法：单调队列处理“滑动窗口最大值”

终于到了我最想讲的内容。滑动窗口最大值是deque的最佳教学题，也是我刷题路上第一次感觉到“原来数据结构选对了，解法能这么干净”的题。

5.1 为什么会想到用双向队列

题目大意：给定一个数组和一个窗口大小k，窗口从左往右每次移动一格，求每个窗口内的最大值。

暴力解法很好想：每个窗口都遍历k个数找最大值，复杂度O(nk)。当n和k都到十万级别时，必然超时。

要优化，先看数据流动特征：窗口一直在往前滑动，新元素从右边进入，旧元素从左边离开。这个“一进一出”的过程，本质就是一个队列。可光用普通队列还不够，因为窗口离开时只需要移除“恰好滑出去”的那个元素，但窗口内的最大值在队头，如果有新元素比队尾的元素大，那些“过期弱者”应该提前被淘汰，否则队头永远不一定是最大值。

所以需要一种数据结构：队头能取最大值，队尾能淘汰不可能是未来最大值的元素，两头都能操作——这就是双向队列的用武之地。

5.2 单调队列的核心不变式

我维护一个双向队列，里面存的是数组下标，而不是元素值。为什么存下标？因为窗口滑动时，要判断队头元素是否已经滑出窗口，只有下标才能精确算出来。这个队列从队头到队尾，对应元素值单调递减。

整个算法的核心是三个动作：

1. 队头过期删除：如果队头下标已经小于当前窗口左边界i - k + 1，说明它滑出去了，从队头弹出。
2. 队尾淘汰弱值：当新元素要入队时，把队列里所有值不大于新元素的下标从队尾弹出。因为新元素更靠右，存活时间更长，值也不比它们小，留着它们不可能成为未来窗口的最大值。
3. 插入新下标，然后判断窗口是否完整，完整则记录队头元素值。

from collections import deque def maxSlidingWindow(nums, k): dq = deque() res = [] for i, x in enumerate(nums): # 1. 移除已经滑出左边界的下标 while dq and dq[0] < i - k + 1: dq.popleft() # 2. 队尾淘汰：保留更大的、更靠右的候选 while dq and nums[dq[-1]] <= x: dq.pop() # 3. 当前下标入队 dq.append(i) # 4. 窗口形成后再往结果里写 if i >= k - 1: res.append(nums[dq[0]]) return res

看到这里你会发现，每个元素最多入队一次、出队一次，所以整体复杂度是O(n)，空间O(k)。

5.3 代码实现与三个易错点

说实话，这个解法思路不难理解，但亲手写的时候我还是踩了几个坑。

• 第一个坑：队列里存下标还是存值？如果只存值，窗口滑动时没法知道这个值是不是已经过期了。所以必须存下标，比较大小的时候通过nums[dq[索引]]来取值。
• 第二个坑：队尾淘汰时用<=还是<？我用的是<=，也就是说新元素和队尾元素相等时，旧元素会被弹出。原因是旧元素下标更靠左，比新元素更早过期；既然值一样大，保留新元素可以延长它在队列里的生命周期，同时队列里不会堆积大量等值元素。
• 第三个坑：结果数组什么时候开始记录？窗口还没扫满k个元素时不要记录。我用if i >= k - 1来判断窗口是否已经完整，这比在循环里额外维护一个“窗口计数”更简洁。

这个单调队列的思想不止能用在这一道题上。滑动窗口最小值、长度固定的子数组最大和、一些“区间内需要动态维护极值”的问题，都是同一个套路。把它吃透，后面遇到单调栈，你会觉得思路熟悉很多。

6. 刷到这里的三个收获

写到这里，题目本身都讲得差不多了，我想分享三个我在反复练习之后才悟到的体会，希望能让你少走一点弯路。

6.1 容器类问题的第一步永远是画状态图

我刚开始做“用栈实现队列”这种题时，总觉得凭空想象太抽象。后来改成在纸上画框子：左边画一个入栈，右边画一个出栈，用箭头模拟每一次push和pop，画两三组数据之后，规律自己就浮出来了。

画状态图的意义在于：栈和队列最重要的信息不是“我存了哪些值”，而是“这些值的顺序在当前状态下长什么样”。你盯着代码看很难看出in_stack倒进out_stack时顺序翻转的效果，但一画图就很直观。我现在刷任何容器题，都会先在草稿纸上模拟一个5个元素以内的小用例，再动笔写代码。

6.2 比模板更重要的是边界条件和“最小规模用例”

有位一起刷题的朋友曾问我：为什么他背了很多模板，一遇到变体题还是不会？我的观察是，模板只能解决“这道题”，解决不了“这一类题”。真正能迁移的是边界条件的敏感度。

比如括号匹配，你要主动去想“第一个字符是右括号怎么办”、“全是左括号怎么办”；循环队列，你要想“空队列执行deQueue会怎样”、“满队列执行enQueue会怎样”；滑动窗口，你要想“k等于1”、“k等于数组长度”、“所有元素相同”的情况。把这些最小规模用例在脑子里过一遍，比多背三道题有用。

6.3 数据结构选型决定代码的干净程度

同一个小功能，选错容器往往代码会越写越拧巴。比如在Python里处理滑动窗口最大值，如果不用deque而是用list每次切片，代码要短很多，但复杂度直接退化到O(nk)；经验不足的人可能看不出问题，直到提交超时才回头改。

反过来，如果选对容器，代码的“形状”会非常自然：栈就是push/pop，队列就是offer/poll，deque就是两端进出。读代码的人一眼能看出你在“模拟一个后进先出的过程”还是在“维护一个滑动窗口”。这也是为什么我在刷题时会刻意要求自己先写清数据结构选型，再写逻辑，而不是边写边改。

最后再补一个我个人觉得最值得做的练习：刷完这三类容器题后，别急着继续往下冲，尝试脱离标准库，用数组手写一个栈、一个循环队列、一个带迭代能力的双向队列。手写一遍之后，你会对这些容器的“为什么能O(1)”有肌肉记忆。之后再碰单调栈、单调队列、双向BFS这类进阶题，容错率会明显高很多。数据结构这种东西，看一百遍不如亲手推演一遍。