企业官网建设流程全解析

代码随想录刷到第十天，栈和队列这个专题终于上场了。说实话，我当年在学校上《数据结构》的时候，栈和队列是分开两章讲的、分开考的，当时觉得这就是两个毫无关系的小容器：一个后进先出，一个先进先出，背熟定义就能应付考试。但真正按这套算法路线系统刷题之后，我发现这俩东西远比我印象里重要——数组、链表、哈希表、字符串练的是“遍历”和“存储”的直觉，而栈和队列恰恰是给这些直觉定性的关键：一个管逆序回退，一个管顺序排队。

这篇我把代码随想录第十天的核心题目和这些年实际工程里的经验放在一起，专门聊聊栈和队列到底该怎么学、怎么用，顺便把几个特别容易混的概念——数据结构队列、阻塞队列、消息队列、调用栈——一次拆干净。如果你是正在刷代码随想录的读者，这篇文章可以作为第十天的补充笔记；如果你刚学完栈和队列的基础知识，想知道这些题到底在考什么，下面的题目拆解和边界条件也能帮你少踩几个坑。

1. 第十天的学习起点：先搞清楚栈和队列这对“操作受限”的容器

1.1 代码随想录为什么把栈和队列安排在字符串、哈希表之后

我最初以为前几天的内容是“简单数据结构”，栈和队列应该早点讲。但按代码随想录的顺序刷下来才明白，前面的数组、链表、哈希表、字符串，训练的都是“在开放容器上做遍历和修改”的能力。到了第十天，突然出现了两个“操作受限”的线性表：你不能随便访问中间元素，只能从固定的口子进出。

这个“受限”恰恰是它们的价值。数组和链表太自由了，自由到很多问题找不到切入点；而栈和队列把操作限制死了，反而给了你一个明确的解题信号。Carl在代码随想录里反复强调“什么时候想到用栈、什么时候想到用队列”，本质上练的就是这种信号识别能力。后面刷到树的遍历、图的搜索、动态规划优化时，你会发现当时的“受限”反而成了最快的切入角度。

1.2 栈和队列的底层真相：容器适配器、deque与复杂度

先看一眼基础定义：栈是先进后出（LIFO），只在栈顶插入和删除；队列是先进先出（FIFO），队尾插入、队头删除。这个概念太基础了，但有一个底层细节很多人第一次学的时候没注意：

C++ STL 里的std::stack和std::queue并不是独立的数据结构，而是容器适配器。默认底层容器是deque（双端队列），也可以用vector或list。你调push、pop，实际是转调了底层容器的对应操作。所以栈和队列的“限制”是语义层面的限制，不是物理层面的特殊结构。

Python 这边也类似，栈可以直接用list模拟，队列更推荐用collections.deque。注意这里的deque和 C++ 的deque一个意思，都是双端队列，头尾都能 O(1) 进出。面试手写队列时最常翻车的点就是用了list的pop(0)，那会触发整体搬移，复杂度是 O(n)，别这么干。

复杂度上，入栈出栈、入队出队都是 O(1)，但查找元素是无序的 O(n)。这个看似显然的事实，在后面的高频题里非常关键——单调队列能优化到 O(n)，放弃的就是“查找”能力，只保留“两端的最大/最小候选”。

2. 用栈实现队列、用队列实现栈：两道题吃透“出入口”差异

2.1 两个栈倒手实现队列：transfer时机是唯一难点

LeetCode 232 这道题，代码随想录里放在栈和队列的第一道。题目很直接：用两个栈实现一个队列，支持push、pop、peek、empty。

核心思路是“倒手”。准备两个栈inStack和outStack。推入元素时一律进inStack；弹出时，如果outStack为空，把inStack里的所有元素依次弹出再压入outStack，这样outStack的栈顶就是最早进入的元素。

C++ 实现可以这样：

class MyQueue { private: stack<int> inStack, outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); } int pop() { transfer(); int val = outStack.top(); outStack.pop(); return val; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };

这段代码唯一的难点在transfer的判断条件：只有outStack为空时才搬运。如果你每次pop前都搬运，顺序立刻乱掉。我当时第一次写，把条件写成“如果inStack非空就搬运”，结果连续push多个元素后全乱了。画个图模拟一遍就清楚了：第一次pop时倒手一批，后面只要outStack里还有货，就直接从outStack弹出，这批顺序已经被倒置过一次，再倒就反了。

时间复杂度是均摊 O(1)。每个元素最多进inStack一次、出inStack一次、进outStack一次、出outStack一次，4 次 O(1) 操作摊到每次访问上就是常数。用均摊分析，而不是说严格 O(1)，这是我后来面试被追问时补齐的认知。

2.2 一个队列原地转圈实现栈：把新元素“插队”到队头

LeetCode 225 是反过来：用队列实现栈。很多人第一反应是“一个不行，那就用两个队列”。确实可以用两个队列，一个存数据，一个做辅助搬运。但更妙的是一队列方案。

思路是每次push时，先把新元素正常入队，然后把新元素之前的所有元素依次“出队再入队”，相当于让新元素直接插队到队首。这样pop和top都是 O(1)，push是 O(n)。

Python 里写出来特别紧凑：

from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 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.q

手写队列时最容易踩的坑是popleft和pop。deque.pop()默认从尾部弹，popleft()才是从头部弹。用list的话，pop(0)能用但有 O(n) 搬移成本，力扣上数据量小看不出来，真到工程里就现原形了。

2.3 这两道题结束后，我对栈和队列的理解发生了什么变化

这两道题表面是“互相实现”，本质是在逼你理解一个关键差异：栈的出口在尾部，队列的出口在头部。用栈实现队列，靠的是“倒两次顺序”把尾部出口变成头部出口；用队列实现栈，靠的是“每来一个新元素就插队到最前”，让尾部出口变成头部出口。

刷完这两题我最大的收获是：以后看到“顺序反转”，第一反应就是栈；看到“按到达顺序处理”，第一反应就是队列。这种条件反射不是背出来的，是手写两遍之后长在脑子里的。代码随想录把这组题放在章节开头，用意很明显——先通过互相当镜子，把容器的行为模型烙进脑子里，后面再上真实场景题。

3. 括号匹配、相邻重复删除、逆波兰表达式：栈的三大主场

3.1 有效的括号：右括号必须匹配最近的左括号

LeetCode 20 是栈的入门必刷题。给你一串只包含()[]{}的字符串，判断是否有效。有效性规则里最关键的一条是：右括号必须以正确的顺序闭合。什么叫“正确的顺序”？就是它必须匹配最近的一个未匹配左括号。

这不就是栈的先进后出吗？遍历字符串，遇到左括号就入栈；遇到右括号，检查栈顶是否是对应的左括号，是就弹出，不是就说明不匹配；最后再看栈是否为空，不为空说明有左括号落了单。

代码不复杂，但有三个边界值得写进笔记：

• 遇到右括号时栈已经空了，直接返回 false，说明右括号在前。
• 遍历结束后栈不为空，返回 false，说明右括号不够。
• 三种括号混合时，最好用哈希表存配对关系，别写三套 if 嵌套。

bool isValid(string s) { stack<char> st; unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (pairs.count(c)) { if (st.empty() || st.top() != pairs[c]) return false; st.pop(); } else { st.push(c); } } return st.empty(); }

很多人觉得这题简单，扫描一遍就完事了。但面试里它经常被改编成“括号嵌套深度”“删除最少的括号使其合法”等一系列变体，底层都是同一个模型：遇到匹配就抵消。把这道题吃透，等于给后面的动态规划版本打了个地基。

3.2 删除字符串中的所有相邻重复项：字符串上的“消消乐”

LeetCode 1047 和括号匹配长得不像，思路却一模一样。输入abbaca，两个相邻的b消掉之后变成aaca，相邻的a又能消掉，最终结果ca。要处理这种“连锁反应”，最自然的就是栈。

逐字符压栈：当前字符和栈顶相同，就把栈顶弹出（相当于这对字符抵消了）；否则入栈。结束之后栈里剩下的字符拼接起来就是答案。

def removeDuplicates(self, s: str) -> str: stack = [] for ch in s: if stack and stack[-1] == ch: stack.pop() else: stack.append(ch) return ''.join(stack)

这道题的启发是：消消乐不一定只发生在游戏里。很多字符串处理题，看到“相邻”“重复”“回退”这些关键词，都要条件反射地想到栈。注意题目说的是“相邻重复”，如果改成“删除所有重复字符不管位置”，那栈就不好使了，得用哈希表统计。这个区分特别重要：栈管的是“顺序上的相邻抵消”，不管“全局频率统计”。

3.3 逆波兰表达式求值：一个栈就能搞定后缀表达式

LeetCode 150 是栈在表达式求值里的经典应用。逆波兰表达式也叫后缀表达式，运算符跟在操作数后面，比如1 2 +就等于1 + 2。它最大的好处是不需要括号，也不需要优先级规则，光靠一个栈就能从左到右算完。

规则：遇到数字就入栈；遇到运算符就弹出栈顶的两个数字，先弹出的作为右操作数，后弹出的作为左操作数，计算后再把结果压回栈。循环结束后栈顶就是答案。

写成 C++：

int evalRPN(vector<string>& tokens) { stack<int> st; for (string& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int b = st.top(); st.pop(); int a = st.top(); st.pop(); if (t == "+") st.push(a + b); else if (t == "-") st.push(a - b); else if (t == "*") st.push(a * b); else if (t == "/") st.push(a / b); } else { st.push(stoi(t)); } } return st.top(); }

有两个坑我一定要说。第一，减法除法是有顺序的，先弹出的b是右操作数，后弹出的a是左操作数，写成b - a直接全错。第二，整数除法要向零截断。C++ 的整数除法对负数本身就是向零截断，但 Python 的//是向下取整，所以 Python 版本遇到除法要写int(a / b)，不能直接a // b，否则结果为 -1 时会被算成 -2。

为什么计算机喜欢后缀表达式？因为编译器和解释器根本不需要维护运算符优先级和括号嵌套状态，一个栈就搞定了。这也是栈在真实系统里最成功的应用之一，只是我们平时写高亮式子看不到这层而已。

4. 滑动窗口最大值与前K个高频元素：单调队列和优先队列的博弈

4.1 暴力解法的瓶颈：为什么O(nk)撑不住

LeetCode 239 是一道“队列进阶”题：给定一个数组和一个大小为 k 的滑动窗口，窗口每次右移一格，要求输出每个窗口的最大值。

暴力解法很好想：每个窗口里扫一遍找最大值，复杂度 O(nk)。在 k 接近 n 时就是 O(n²)，力扣上直接超时。问题本质在于：窗口滑动时，你既要删除一个左边的元素，又要加入一个右边的元素，同时还要知道当前窗口的最大值。这个动态维护最大值的过程，单靠每次全量扫描肯定浪费。

那能不能用一个“队列”来维护窗口？能。队列天然符合窗口的滑动方式，但普通队列只能保证先进先出，不能保证弹出的永远是最大值。于是需要在队列这个容器上增加规则，这就是单调队列。

4.2 单调队列：淘汰永远不会成为最大值的元素

单调队列的经典做法是用双端队列（deque）维护一个从队头到队尾递减的队列，队头永远是当前窗口的最大值。窗口滑动时做三件事：

• 右端点入队之前，把队尾所有小于当前值的元素弹出，因为它们年纪比新元素大，值还比新元素小，永远不可能再成为窗口最大值，直接淘汰。
• 如果离开窗口的左端点的值恰好等于队头（也就是当前最大值），把队头弹出。
• 队头自然就是当前窗口最大值。

这里最精妙的是“淘汰”过程。每个元素最多入队一次、出队一次，所以整体复杂度是 O(n)，不是 O(nk)。

用下标存储比存值更严谨，这样才能准确判断某个元素是否已经滑出窗口：

class MonotonicQueue { deque<int> dq; // 存下标 vector<int>& nums; public: MonotonicQueue(vector<int>& n) : nums(n) {} void push(int idx) { while (!dq.empty() && nums[dq.back()] < nums[idx]) { dq.pop_back(); } dq.push_back(idx); } void pop(int idx) { if (!dq.empty() && dq.front() == idx) { dq.pop_front(); // 只有离开的恰好是最大值时才弹 } } int max() { return nums[dq.front()]; } };

我第一次写的版本犯了个错：把“左端点离开窗口”无条件写成pop_front()。但左端点可能早就被淘汰了，队列里根本没有它，强行弹出会把更早的、可能还有效的元素弹掉。判断条件必须是“相等才弹”。

单调队列的应用远不止这一题。热词里提到的“单调队列优化 DP”，本质就是在处理形如“求前一个窗口中符合某种条件的极值”时，把 O(k) 的扫描降成均摊 O(1)，很多 DP 题从 O(nk) 优化到 O(n) 靠的就是这个思想。

4.3 前K个高频元素：为什么用小顶堆而不是大顶堆

LeetCode 347 要求返回数组里出现频率最高的前 k 个元素。第一步很常规：哈希表统计每个元素的频率。第二步就有意思了：你有一个频率表，怎么高效提出前 k 个最大的？

最直觉的思路是大顶堆：把所有频率都扔进大顶堆，然后弹出 k 次。这样复杂度是 O(n log n)，能过但不优雅。更优的做法是只维护一个大小为 k 的小顶堆。遍历频率表时：

• 堆里不足 k 个，直接入堆。
• 堆满了，拿当前频率和堆顶比较。堆顶是堆里最小的频率，如果当前频率比堆顶大，就弹出堆顶、把当前频率入堆。

反直觉吧？找“最大的前 k 个”反而用的是小顶堆。原因是小顶堆的堆顶是堆内最小元素，每次用它做门槛，可以随时把最小的踢出去，保证留在堆里的始终是最大的 k 个。最终堆里 k 个元素就是答案。C++ 的priority_queue默认是大顶堆，做这题需要手动指定greater，这也是一个小坑。

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int x : nums) freq[x]++; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小顶堆 for (auto& [val, cnt] : freq) { pq.push({cnt, val}); if (pq.size() > k) pq.pop(); } vector<int> ans; while (!pq.empty()) { ans.push_back(pq.top().second); pq.pop(); } return ans; }

这题一般归在优先队列/堆的范畴，但放在栈和队列章节里也说得通——优先队列本质是一种“带优先级的队列”，出队顺序不再由到达时间决定，而是由优先级决定。理解了这一点，你对“队列”的概念就完成了从数据结构到抽象模型的升级。

5. 别搞混三种“队列”：数据结构队列、阻塞队列、消息队列

5.1 阻塞队列与线程池：任务来了放不下怎么办

刷题时说的队列很简单：FIFO，O(1) 进出。但真实工程里有个更常见的队列——阻塞队列（BlockingQueue）。线程池的workQueue就是典型：一堆线程忙着处理任务，新任务来了先丢进队列排队。但队列容量是有限的，满了怎么办？阻塞队列的做法是让生产者线程阻塞住，等消费者腾出位置再继续。

Java 里常见的ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue，区别主要在于边界和语义。比如SynchronousQueue没有容量，每个插入操作都必须等待另一个线程的移除操作，相当于手递手交接。线程池选哪种队列，直接影响拒绝策略和吞吐量，这是比刷题深得多的“队列”话题。

刷题时理解队列的 FIFO 行为，到并发编程里不会自动迁移，但你至少能问出正确的问题：队列有界还是无界？满了是阻塞还是丢弃？这个“有界 + 阻塞”的设计，在算法题里就是循环队列加满了的变体，在工程里就是背压机制。打好数据结构底子，至少能听懂面试官在问什么。

5.2 消息队列：异步、削峰、解耦里的“队列”不是队列

热词里有一批关于 Kafka、RabbitMQ、RocketMQ 的搜索，我猜你会好奇：这些消息队列和今天学的队列是什么关系？答案很直接：几乎没有结构上的关系。

消息队列（MQ）是分布式系统里的中间件，解决的是“服务间如何可靠地传递消息”的问题。它的核心价值有三个：

• 异步：下单后发短信，丢进 MQ 就返回，短信服务慢慢消费。
• 削峰：秒杀瞬间流量巨大，先全接入 MQ，消费端按自己的节奏处理。
• 解耦：订单系统和库存系统不直接互相调用，都只跟 MQ 打交道，一方挂掉不影响另一方。

这里的“队列”更多是一个通道或缓冲区的代名词，它不一定保证严格的 FIFO，更关心的是消息不丢、不重复、能分区、能水平扩展。所以别拿着数据结构队列的 FIFO 特性去套消息队列，方向就错了。

5.3 Kafka、RabbitMQ、RocketMQ的选择逻辑

很多人第一次接触 MQ 选型就懵了，我直接给一张简化对照表，这是基于工程实践的主观排序，不是官方标准：

选型别只看名气。Kafka 吞吐确实猛，但如果你只是每天几十万条业务消息，运维复杂度完全没必要的；RabbitMQ 轻量易用，功能丰富，中小项目足够；RocketMQ 在可靠性和事务上很能打，Java 生态的团队上手成本低。说白了，选 MQ 就是选场景和运维能力，不是选“最大最强”。这和刷题选数据结构是一个道理：栈能解决的题，别非得用哈希表硬怼。

6. 从刷题回到现实：函数调用栈、栈帧与backtrace

6.1 一次函数调用的栈帧里到底装了什么

刷题天天用栈，但很多人不太清楚“调用栈”这个真实系统里无处不在的栈到底长什么样。当你调用一个函数时，操作系统或运行时会在当前线程的栈上分配一块连续区域，叫做栈帧（stack frame），里面保存着：

• 返回地址：函数执行完要回到哪条指令。
• 函数参数和局部变量。
• 保存的寄存器值，保证函数返回后调用者的状态不丢。
• 一些辅助管理信息，比如上一个栈帧的地址。

递归函数之所以容易爆栈，就是因为每递归一层就要压入一个新栈帧，栈空间是有限的，深度太大自然溢出。这也能解释为什么很多算法题用递归写非常简洁，但 n 一大就栈溢出——你用的栈是操作系统给的运行栈，不是自己管理的堆空间。

6.2 崩溃日志里的backtrace是怎么还原调用链的

热词里有“backtrace栈回溯”“arm调用栈回溯”，这是系统崩溃分析里极其重要的能力。所谓 backtrace，就是把当前线程的调用栈整个翻出来，打印出从最内层到最外层的函数调用链。

GDB 里的bt命令、Linux 程序崩溃时用backtrace()函数和addr2line配合、Android NDK 崩溃日志里的 tombstone 文件，本质都在做同一件事：根据栈帧中保存的返回地址，一层一层往上找，还原出“谁调用了谁”。

你平时如果只是写业务代码，可能很少直接接触这些东西。但一旦遇到线上崩溃、段错误、栈被写坏，能读 backtrace 是最基本的排查能力。理解了栈帧结构，你才看得懂崩溃栈里那些地址和函数名的含义。这也是栈这一节延伸到工程层面的最大价值。

6.3 栈上变量为什么不能返回，堆和栈到底差在哪

C/C++ 初学者最容易踩的一个坑：函数返回局部变量的地址，然后运行结果莫名其妙变了。原因很简单，局部变量存在栈帧里，函数一返回栈帧就销毁，那块内存不再属于你，随时可能被别的内容覆盖。表面上值还在，其实是“悬空指针”。

而全局静态变量就不一样，它存放在静态存储区，生命周期从程序启动到程序结束，不随函数返回而失效。这就是热词里“栈变量、全局静态变量”背后的差异：

• 栈：编译期自动分配释放，空间小（典型几 MB），速度快。
• 堆：运行期手动分配/释放（或 GC），空间大，速度相对慢，有碎片问题。
• 静态区：程序启动分配，直到结束才释放，生命周期全局。

刷题时我们用 Python 的列表模拟栈，用 C++ 的std::stack，完全不用关心这些内存细节。但真实的栈是要吃内存的，递归深度、局部变量大小、函数调用嵌套层数，都会直接影响栈空间够不够。这也是为什么工程上大数组要么放全局、要么放堆的原因。

7. 第十天的避坑清单与我的内化建议

7.1 循环队列的取模、判空判满细节

热词里有一句“假设以数组 q[m] 存放循环队列中的元素，同时以 rear 和 length 分别指示环形队列中的队…”，这明显是循环队列的经典考题。用数组实现队列时，直接尾部追加、头部删除会浪费大量空间，循环队列用取模让front和rear在数组里绕圈：

• 入队：rear = (rear + 1) % m
• 出队：front = (front + 1) % m
• 判空：length == 0
• 判满：length == m

如果不引入length，只用两个指针判断空和满就会撞车——满和空时front == rear都一样。常见解法是牺牲一个存储单元，或者加一个flag标记最近一次操作是入队还是出队。这些细节刷题不一定直接考，但“用数组模拟队列”在面试手写时非常常见，尤其是消息队列、缓存设计之类的题目里会反复出现。

7.2 pop返回void：不同语言里的出队接口差异

栈和队列的基础操作在不同语言里长得不一样，这是个非常影响手写效率的点：

• C++：stack::pop()和queue::pop()都返回 void，必须先top()/front()取值再pop()。
• Java：pop()直接返回被移除的元素，但Deque用poll()和remove()时有空值异常的区别。
• Python：list.pop()默认尾部弹；deque.pop()尾部弹，popleft()头部弹。

这些接口差异在力扣刷题时可能感觉不到，但面试现场白板写代码时，写错一个pop()返回值是很致命的。我自己的习惯是：面试手写前先口头跟面试官确认语言，然后在心里默念一遍该语言的接口签名，再开始写。

7.3 三个建议：模型归类、画图模拟、复杂度说理

刷完第十天的题目，我留下的复习笔记就是三句话，分享给你参考：

第一，建立模型归类。看到“逆序处理”“回退”“最近匹配”“相邻抵消”想栈；看到“按顺序排队”“滑动窗口”“公平调度”想队列。题目永远在变，模型就那几个。

第二，先画图再写代码。栈和队列的题尤其适合画图模拟，尤其是两个栈倒手、单调队列滑动窗口这种，画一遍胜过空想十遍。代码写错了，回头画图定位也快。

第三，把复杂度讲出理来。两个栈模拟队列为什么是均摊 O(1)？单调队列为什么是 O(n)？队列模拟栈为什么 push 是 O(n)？这些“为什么”想清楚了，面试变形题才能接得住，而不是靠背代码。技术面试和工程应用里，能说清楚“为什么这样设计”的人，跟只会“调 API”的人，差别就在这一个层次。

我自己的体会是，栈和队列这个专题像是一道分水岭：前面刷数组、链表，练的是“手速”；从这道开始，练的是“用数据结构的特性去建模问题的能力”。第十天的内容刷完，最值得留下的不是代码，而是那个“看到问题能条件反射地想到 LIFO 或 FIFO”的肌肉记忆。后面学到二叉树、回溯、动态规划时，你再回头看这天的内容，会发现它们的身影到处都是。