尧图网站开发 
1. 栈和队列专题的核心学习思路训练营走到第10天数据结构正式开始从“线性表的变体”切入“操作受限的容器”。Day 10的主题是栈和队列先说个结论这两个结构单独拿出来都不难难的是“什么时候该用栈什么时候该用队列”以及“为什么某些经典场景只能用其中某一个”。这一篇把我在代码随想录栈和队列专题里的整理、踩坑和思考完整写出来。1.1 为什么先学栈再学队列栈和队列在逻辑层面都属于“操作受限的线性表”但它们的受限方式刚好相反栈是后进先出LIFO队列是先进先出FIFO。在刷题层面栈的出场频率远高于队列因为“匹配”“回溯”“递归转迭代”这几个场景天然由栈承接。队列则主要出现在“按层处理”“按序调度”这类场景里。从代码随想录的训练节奏看Day 10 之所以把栈放在队列前面是因为栈的思维模式更贴近递归的逆向展开递归是系统帮我们维护调用栈而手动用栈则是把“系统隐式做的事”显式做一遍。理解了这个对应关系栈相关的题目就从一个一个背套路变成了“递归展开”的自然延伸。1.2 专题覆盖的核心题目全景Day 10 专题里最经典的几道题先列出来大家感受一下分布用栈实现队列用队列实现栈有效的括号删除字符串中的所有相邻重复项逆波兰表达式求值后面还会顺势引出滑动窗口最大值、前 K 个高频元素但Day 10的重点是前三类互相实现、括号类、模拟类。这几道题几乎涵盖了栈和队列在面试里80%的基础考法。这里有个容易被忽略的点用栈实现队列和用队列实现栈表面上是“互相模拟”实际上考的是对两种结构操作时序的精确理解。很多人背了代码但被问到“为什么这里要两个栈”“为什么这两个队列必须这么倒腾”就会卡壳。原因很简单——没有真正理解数据流动的时序。2. 栈和队列的底层原理与容器选型很多人误以为栈和队列是 C STL 里的某种“独立容器”其实在 STL 里std::stack 和 std::queue 本质是容器适配器container adapters。它们不自己存储数据而是包装在底层容器之上封住两端的操作接口只暴露特定的进出方式。2.1 栈的底层实现逻辑C 中 std::stack 默认底层容器是 std::deque双端队列而不是 std::vector。很多人刚知道这点时挺意外因为在直觉里“栈在数组上实现”顺理成章。std::deque 作为默认底层容器原因是栈的尾插尾删操作频繁而 deque 对头部和尾部的插入删除都做了优化扩容成本也比 vector 低。vector 尾部操作虽然也是均摊 O(1)但在频繁扩容时的搬移成本更高而且 vector 的内存连续性在这里并没有额外收益。用代码验证一下底层类型#include iostream #include stack #include queue #include vector #include deque int main() { std::stackint, std::vectorint st_vec; // 可以换成 vector 底层 std::stackint, std::dequeint st_deque; // 默认底层 std::queueint, std::listint q_list; // 队列也可以用 list 做底层 std::cout stack and queue are container adapters\n; return 0; }2.2 队列的底层实现逻辑std::queue 默认底层容器同样是 std::deque。它要求底层容器支持 front()、back()、push_back()、pop_front() 这四个操作vector 因为缺少 pop_front() 所以不能直接作为 queue 的底层容器而 deque 正好全支持。这里补一个知识点在刷题场景里如果只是单纯“用队列”而不涉及中间插入用 std::queue 就行。但如果涉及“从两端操作”比如滑动窗口、双端操作场景需要直接用 std::deque。deque 的随机访问性能虽然不如 vector但在两端增删的场景下非常顺手。2.3 数组模拟栈和队列的高性能方案刷题和竞赛场景里很多人不直接用 STL而是用数组手写栈和队列。性能更好也更容易控制边界。竞赛选手常用这种写法数组模拟栈int stk[100005]; int top 0; // 栈顶指针栈中元素个数 // 入栈 stk[top] value; // 出栈 top--; // 返回栈顶 int topValue stk[top]; // 判断空 if (top 0) { /* 空栈 */ }数组模拟队列int q[100005]; int head 0, tail 0; // 左闭右开 [head, tail) // 入队 q[tail] value; // 出队 head; // 队首 int frontValue q[head]; // 判断空 if (head tail) { /* 空队列 */ } // 队列大小 int size tail - head;这种手写方式在刷题网站上的执行效率更高因为避免了 STL 里的模板实例化开销。但也容易出问题如果出队后 head 不断变大前面被“废弃”的空间无法复用属于一次性队列。循环队列可以解决这个问题但刷题时一般不需要。3. 核心题目拆解与实现细节按代码随想录的节奏这几道题需要按“理解思路→动手实现→对照优化”的顺序吃透。我把每道题的关键拆解写在这里。3.1 用栈实现队列题目要求使用两个栈实现队列的 push、pop、peek、empty 操作。核心思路是双栈倒腾一个栈负责入队input stack一个栈负责出队output stack。入队时直接压入 input出队时如果 output 为空就把 input 里的元素全部弹出并压入 output此时 output 的栈顶就是最早进入的元素。class MyQueue { private: std::stackint inStack; std::stackint outStack; void transfer() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { transfer(); } int result outStack.top(); outStack.pop(); return result; } int peek() { if (outStack.empty()) { transfer(); } return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这里最关键的一点是 transfer 的触发时机只在 outStack 为空时才转移。如果在 outStack 还有元素时就转移会打乱顺序。比如连续 push 了 1、2、3 后 pop 了两次outStack 里剩下 3此时再 push 4如果立即转移顺序就乱了。所以必须“非空不转移、空才全量搬”。我一开始写这道题时犯过一个错误每次 pop 前都转移一次结果把一个简单的 O(1) 摊还操作变成了 O(n)。每次 transfer 后 outStack 里可能有 n 个元素还没出完立刻又转移相当于把前面的搬移全部浪费掉。3.2 用队列实现栈题目要求使用两个队列实现栈的 push、pop、top、empty 操作。这道题有两种主流写法一种是双队列倒腾另一种是单队列倒腾。双队列版本中入栈时把元素放入空队列然后把另一个队列的所有元素依次转移过来保证新元素在队首位置这样出栈时直接取队首即可。单队列实现更简洁也是我推荐优先掌握的版本入栈时先把元素放入队尾然后把队列里前面 n-1 个元素依次取出再放回队尾这样新元素就旋转到了队首。class MyStack { private: std::queueint q; public: MyStack() {} void push(int x) { int size q.size(); q.push(x); while (size--) { q.push(q.front()); q.pop(); } } int pop() { int result q.front(); q.pop(); return result; } int top() { return q.front(); } bool empty() { return q.empty(); } };这个实现有几个细节值得注意push 里的 int size q.size() 必须在 push 新元素之前取因为 push 之后队列 size 变了没法再用 size 表示“原来有几个元素需要旋转到末尾”。我自己第一次写的时候把 size 放在了 push 之后导致每个元素被多旋转了一次结果队首并不是最新元素。3.3 有效的括号这题是栈应用里最基础的匹配类题目。给一个只包含 ( ) [ ] { } 的字符串判断括号是否有效。有效定义是左括号必须用同类型右括号闭合且按正确顺序闭合。核心思路遍历字符串遇到左括号就压栈遇到右括号弹出栈顶检查是否是对应的左括号。class Solution { public: bool isValid(std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { return false; } char top st.top(); st.pop(); if (c ) top ! () return false; if (c ] top ! [) return false; if (c } top ! {) return false; } } return st.empty(); } };这段代码里有个很容易漏的判断遍历完字符串后栈必须为空才说明所有左括号都被匹配掉。如果最终栈里还有残留的左括号说明有未闭合的括号应该返回 false。这个“最后判空”是我见过很多人掉坑的地方。另一个细节是提前剪枝如果字符串长度是奇数直接返回 false因为有效的括号对长度必然是偶数。这个优化虽然不影响复杂度量级但在判断长字符串时能省一半遍历。3.4 删除字符串中的所有相邻重复项这道题的经典解法是用栈模拟删除过程遍历字符串如果当前字符和栈顶相同就弹出栈顶相当于删除这一对相同项否则压入当前字符。遍历结束后把栈里剩余字符拼接成结果返回。class Solution { public: std::string removeDuplicates(std::string S) { std::string result; for (char c : S) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; } };这里有个技巧直接用 std::string 当作栈来用省去了 std::stack 再转字符串的步骤。string 本身就支持 back()、push_back()、pop_back()行为上就是一个字符栈。很多人在写出 std::stack 版本后还多写了一遍“把栈倒出来再 reverse”很没必要。理解了这道题再往深一层就是“删除所有相邻重复项”的进阶版重复 k 次的字符串消除。核心思路是用栈记录“字符 连续出现次数”遇到相同字符时计数加一达到 k 时出栈。这题在不少公司的笔试里出现过本质是相邻项匹配问题的变体。3.5 逆波兰表达式求值逆波兰表达式后缀表达式求值是所有栈应用里最经典的考题。它的好处在于不需要处理括号优先级只需要从左到右扫描遇到数字压栈遇到运算符就弹出两个操作数计算结果后压回栈中。class Solution { public: int evalRPN(std::vectorstd::string tokens) { std::stackint st; for (const std::string token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else if (token /) st.push(a / b); } else { st.push(std::stoi(token)); } } return st.top(); } };这道题最容易踩坑的细节是运算顺序先弹出的是右操作数 b后弹出的是左操作数 a。因为栈是 LIFO 结构先弹出的元素实际上是更靠后的操作数。比如表达式 3 4 -先弹出 4 作为 b再弹出 3 作为 a正确的运算是 3 - 4 -1。如果写反了就会得到 4 - 3 1结果完全错误。另外一个隐藏坑是除法涉及负数的情况。C 里整数除法是向零截断的而很多后台题目的预期是向零截断而不是向下取整所以 a / b 直接写就行。但如果你自己用 Python 刷这题就要小心Python 的 // 是向下取整负数情况会出错需要 int(a / b) 修正一下。4. 栈和队列的高阶应用与进阶延伸Day 10 的基础题吃透之后栈和队列还有两个非常高频的进阶方向单调栈和单调队列。它们虽然不一定出现在 Day 10 的课程里但既然专题是“栈和队列”提前把这两个进阶方向串起来说后边学到时会轻松很多。4.1 单调栈解决“下一个更大元素”类问题单调栈指的是栈内元素按递增或递减顺序排列。它的经典应用是找数组里每个元素右边第一个比它大的元素LeetCode 第 739 题“每日温度”就是这个场景。单调栈的核心思想是遍历数组时把“还没找到答案的元素”的下标压入栈中。当遇到一个新元素大于栈顶元素时说明栈顶元素找到了答案弹出并记录结果。栈内始终保持从栈底到栈顶递减或递增因此称为单调栈。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint result(n, 0); stackint st; for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { int idx st.top(); st.pop(); result[idx] i - idx; } st.push(i); } return result; }这个模板的精髓在于每个元素最多入栈一次、出栈一次所以整体时间复杂度是 O(n)而不是暴力解法的 O(n^2)。我自己的理解方式是单调栈解决的其实是“延迟匹配”的问题。当前元素不知道后面的情况所以只能先存起来当后面的元素出现时它终于可以“兑现承诺”把之前等它的若干元素一次性消化掉。4.2 单调队列解决“滑动窗口最大值”问题滑动窗口最大值是队列专题里最经典的题目。暴力解法在每个窗口内遍历 k 个元素找最大值整体复杂度 O(nk)。单调队列的解法用 O(n) 搞定。思路是维护一个“从队首到队尾递减”的双端队列队首始终是当前窗口的最大值。每次右移窗口时先从队尾弹出比新元素小的元素因为它们在新元素存在期间不可能成为最大值再把新元素入队同时检查队首元素是否已经滑出窗口如果滑出就弹出。class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint result; dequeint dq; for (int i 0; i nums.size(); i) { // 队尾弹出比当前元素小的 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 队首滑出窗口 if (dq.front() i - k) { dq.pop_front(); } // 窗口形成后记录结果 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };这里有一个很核心的细节队列里存的是下标而不是值。存下标的好处是可以同时判断“窗口范围”和“数值大小”只存值的话你无法判断队首是否已滑出窗口。这段代码里 while 弹出队尾的条件是 而不是 。如果用 当两个相同最大值同时出现在窗口里时队列里就会保留两个相同值但靠前的那个在滑动时可能已经被移出窗口却仍然留在队列里造成结果不准确。用 可以保证靠后的新值把旧值顶掉旧值即使还在窗口内也不会影响正确性。4.3 优先队列堆与栈队列的区别优先队列std::priority_queue虽然名字里有“队列”但它和栈、队列完全是两个逻辑层次。栈和队列管的是“进出顺序”优先队列管的是“优先级顺序”每次出队的都是当前元素中优先级最高的那个。优先队列内部实现通常是二叉堆插入和删除的时间复杂度都是 O(log n)。它在解决 Top K 问题、合并 K 个有序链表、任务调度等问题里出镜率极高。比如“前 K 个高频元素”那道经典题做法就是先用哈希表统计频率再用大小为 K 的小顶堆维护出现频率最高的 K 个元素。堆顶是这 K 个里频率最低的遇到新元素时如果频率高于堆顶就替换堆顶并重新调整堆。class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int num : nums) freq[num]; // 小顶堆pair频率, 元素 auto cmp [](pairint, int a, pairint, int b) { return a.first b.first; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) heap(cmp); for (auto p : freq) { heap.push({p.second, p.first}); if (heap.size() k) { heap.pop(); } } vectorint result; while (!heap.empty()) { result.push_back(heap.top().second); heap.pop(); } return result; } };这里特别需要注意优先队列定义时第三个模板参数的写法。C 的 priority_queue 默认是大顶堆第三个模板参数是一个仿函数类型里面用 表示“优先级低”的排在前面构造出小顶堆。很多人第一次写时容易写成 sort 里的比较器习惯搞反方向。5. 刷题踩坑实录与高效编码技巧这一节把我在做这个专题时真正踩过的坑和总结出的经验记录下来很多都是题解里不会写但实战中非常影响效率的细节。5.1 栈的遍历问题C 的 std::stack 没有迭代器不支持范围 for 循环遍历。如果你需要遍历栈中所有元素只能逐个 pop这会破坏栈结构。如果要遍历且保留栈内容需要先把元素复制一份或者改用 deque/vector 自己维护。我在刚开始刷题时经常犯一个毛病想把栈里的内容打印出来调试结果写完发现输出完栈也空了后续逻辑全乱。后来养成一个习惯凡是调试阶段需要看栈内容就用一个临时栈做倒腾输出完再恢复原样。5.2 queue 没有 clear 方法std::queue 没有 clear()。清空一个队列的方法是直接赋值为一个新的空队列std::queueint q; // 清空 q std::queueint();我在写“用队列实现栈”时一度想找 q.clear()结果发现没有还愣了一下。这个细节在面试时突然被问到容易卡壳提前知道能少点尴尬。5.3 循环 vs 递归什么时候用栈替换很多递归代码都可以改成用栈模拟的迭代版本。判断标准是递归里有“先处理子问题再回来自处理”的过程就可以用栈保存“现场”。比如二叉树的前序遍历递归版本非常好理解void preorder(TreeNode* root) { if (!root) return; visit(root); preorder(root-left); preorder(root-right); }改成非递归的栈版本vectorint preorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; if (root) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; }对比一下就能看出递归方法里“先左后右”的访问顺序在栈版本里必须用“先压右再压左”的入栈顺序来保证。因为栈是后进先出右子树先入栈反而会后访问。很多人在简历上写了“熟悉常见数据结构”但一问到“递归转迭代怎么做”就露馅。栈相关的题目练熟之后这类问题就能答得很有底气。5.4 用 string 模拟栈的小技巧前面在“删除相邻重复项”里提到了用 std::string 当字符栈这个技巧可以推广到很多字符串处理场景。比如“简化路径”那道题需要按 / 分割路径片段遇到 . 忽略遇到 .. 弹出上一级目录最后拼接结果。用 vector 或直接 string 当栈处理起来逻辑非常顺。class Solution { public: string simplifyPath(string path) { vectorstring st; // 把 vector 当作栈用 int n path.size(); int i 0; while (i n) { // 跳过斜杠 while (i n path[i] /) i; // 提取片段 string name; while (i n path[i] ! /) { name.push_back(path[i]); i; } if (name ..) { if (!st.empty()) st.pop_back(); } else if (name . || name.empty()) { // 跳过 } else { st.push_back(name); } } string result /; for (int j 0; j st.size(); j) { if (j 0) result /; result st[j]; } return result; } };这里用 vector 模拟栈比 std::stack 好的地方在于可以随机访问方便最后拼接结果。std::stack 只能看栈顶还得把元素倒出来才能拼路径很别扭。这个“用 vector 代替 stack 在特殊场景下更好用”的经验在不少字符串题里都能省事。6. 容器适配器与代码随想录的刷题方法论最后从整体方法论的角度聊聊栈和队列这个专题在代码随想录训练营中的位置以及刷题时值得坚持的几个习惯。6.1 代码随想录的选题逻辑代码随想录的风格是“少而精”每个专题挑出来的题目都是同类题里最能建立典型思维的。栈和队列这个专题选的五道题——用栈实现队列、用队列实现栈、有效的括号、删除相邻重复项、逆波兰表达式求值正好覆盖了“结构互转”“匹配检查”“模拟运算”三大场景。这其实也是面试官最爱考的三种角度结构互转类用栈实现队列等考察对操作时序的精确理解匹配类有效括号等考察栈“后退一步”特性在嵌套场景的应用模拟类逆波兰表达式等考察从抽象规则到具体实现的转换能力把这三类题吃透基本就掌握了栈和队列在面试中的全部基础考点。6.2 刷题过程中的几个务实建议第一别急着看题解。栈和队列的题有一个特点思路懂了之后代码往往不难写难的是“从题目描述到想到用栈”这一步。这个跳跃需要自己尝试过才能形成直觉。我自己的经验是每道题至少逼自己先想15分钟哪怕想错了再去看题解时理解的深度完全不一样。第二写完之后要自己背写一遍。不是背代码而是在不看题解的情况下列出用什么数据结构、进出顺序怎么控制、边界条件有哪些。列出这三项之后代码基本就能写出来。这个方法尤其适合“用栈实现队列”这类逻辑绕的题。第三多思考一题多解。“用队列实现栈”就有双队列和单队列两种解法两种都值得写一遍。双队列版本思路直观适合理解单队列版本代码简洁适合面试时快速写出。两个版本都写一遍能把队列操作理解得更透。第四做完看官方题解是否使用了更优的容器。比如“删除相邻重复项”里用 string 当栈就是一个典型的容器优化。同样是栈的思想换一个载体把代码精简一半。这类优化看得越多对语言的掌握就越深。6.3 栈和队列与系统层面的联系栈和队列不只是刷题用的抽象结构它们在系统底层有非常具体的映射。函数调用时每一次调用都会在“调用栈”上压入一个栈帧包含参数、返回地址、局部变量。函数返回时栈帧被弹出控制权回到调用者。这就是“栈”这个名字在计算机系统里最原始的意义。理解了这一点再回头看“有效的括号”这道题本质就是在模拟嵌套结构的闭合匹配和编译器检查括号配对的过程一模一样。队列则更常出现在“生产者-消费者”场景。操作系统里的任务调度、消息队列里的事件缓冲、网络缓冲区中的数据包排队都是队列的应用。Java 里的阻塞队列、线程池里的任务队列本质上都是在利用 FIFO 保证“先来先服务”的公平性。所以栈和队列不只是算法题里的主角更是理解计算机系统运行机制的一把钥匙。把这两个结构理解透后面学递归、学习系统设计都会更顺畅。我个人在实际操作中的体会是这个专题的题目数量不多但每一道都值得反复咀嚼。尤其是“用栈实现队列”和“用队列实现栈”一正一反两道题把两个结构的操作时序彻底理清了。后面遇到任何队列相关的进阶题比如单调队列、双端队列、优先队列都能快速定位到“队列的核心是先进先出但如何控制进出时机才是解题关键”这个本质上。刷完这个专题再顺手用单调栈、单调队列做两道进阶题整个“栈和队列”的知识体系才算真正闭环。 
1. 栈和队列专题的核心学习思路训练营走到第10天数据结构正式开始从“线性表的变体”切入“操作受限的容器”。Day 10的主题是栈和队列先说个结论这两个结构单独拿出来都不难难的是“什么时候该用栈什么时候该用队列”以及“为什么某些经典场景只能用其中某一个”。这一篇把我在代码随想录栈和队列专题里的整理、踩坑和思考完整写出来。1.1 为什么先学栈再学队列栈和队列在逻辑层面都属于“操作受限的线性表”但它们的受限方式刚好相反栈是后进先出LIFO队列是先进先出FIFO。在刷题层面栈的出场频率远高于队列因为“匹配”“回溯”“递归转迭代”这几个场景天然由栈承接。队列则主要出现在“按层处理”“按序调度”这类场景里。从代码随想录的训练节奏看Day 10 之所以把栈放在队列前面是因为栈的思维模式更贴近递归的逆向展开递归是系统帮我们维护调用栈而手动用栈则是把“系统隐式做的事”显式做一遍。理解了这个对应关系栈相关的题目就从一个一个背套路变成了“递归展开”的自然延伸。1.2 专题覆盖的核心题目全景Day 10 专题里最经典的几道题先列出来大家感受一下分布用栈实现队列用队列实现栈有效的括号删除字符串中的所有相邻重复项逆波兰表达式求值后面还会顺势引出滑动窗口最大值、前 K 个高频元素但Day 10的重点是前三类互相实现、括号类、模拟类。这几道题几乎涵盖了栈和队列在面试里80%的基础考法。这里有个容易被忽略的点用栈实现队列和用队列实现栈表面上是“互相模拟”实际上考的是对两种结构操作时序的精确理解。很多人背了代码但被问到“为什么这里要两个栈”“为什么这两个队列必须这么倒腾”就会卡壳。原因很简单——没有真正理解数据流动的时序。2. 栈和队列的底层原理与容器选型很多人误以为栈和队列是 C STL 里的某种“独立容器”其实在 STL 里std::stack 和 std::queue 本质是容器适配器container adapters。它们不自己存储数据而是包装在底层容器之上封住两端的操作接口只暴露特定的进出方式。2.1 栈的底层实现逻辑C 中 std::stack 默认底层容器是 std::deque双端队列而不是 std::vector。很多人刚知道这点时挺意外因为在直觉里“栈在数组上实现”顺理成章。std::deque 作为默认底层容器原因是栈的尾插尾删操作频繁而 deque 对头部和尾部的插入删除都做了优化扩容成本也比 vector 低。vector 尾部操作虽然也是均摊 O(1)但在频繁扩容时的搬移成本更高而且 vector 的内存连续性在这里并没有额外收益。用代码验证一下底层类型#include iostream #include stack #include queue #include vector #include deque int main() { std::stackint, std::vectorint st_vec; // 可以换成 vector 底层 std::stackint, std::dequeint st_deque; // 默认底层 std::queueint, std::listint q_list; // 队列也可以用 list 做底层 std::cout stack and queue are container adapters\n; return 0; }2.2 队列的底层实现逻辑std::queue 默认底层容器同样是 std::deque。它要求底层容器支持 front()、back()、push_back()、pop_front() 这四个操作vector 因为缺少 pop_front() 所以不能直接作为 queue 的底层容器而 deque 正好全支持。这里补一个知识点在刷题场景里如果只是单纯“用队列”而不涉及中间插入用 std::queue 就行。但如果涉及“从两端操作”比如滑动窗口、双端操作场景需要直接用 std::deque。deque 的随机访问性能虽然不如 vector但在两端增删的场景下非常顺手。2.3 数组模拟栈和队列的高性能方案刷题和竞赛场景里很多人不直接用 STL而是用数组手写栈和队列。性能更好也更容易控制边界。竞赛选手常用这种写法数组模拟栈int stk[100005]; int top 0; // 栈顶指针栈中元素个数 // 入栈 stk[top] value; // 出栈 top--; // 返回栈顶 int topValue stk[top]; // 判断空 if (top 0) { /* 空栈 */ }数组模拟队列int q[100005]; int head 0, tail 0; // 左闭右开 [head, tail) // 入队 q[tail] value; // 出队 head; // 队首 int frontValue q[head]; // 判断空 if (head tail) { /* 空队列 */ } // 队列大小 int size tail - head;这种手写方式在刷题网站上的执行效率更高因为避免了 STL 里的模板实例化开销。但也容易出问题如果出队后 head 不断变大前面被“废弃”的空间无法复用属于一次性队列。循环队列可以解决这个问题但刷题时一般不需要。3. 核心题目拆解与实现细节按代码随想录的节奏这几道题需要按“理解思路→动手实现→对照优化”的顺序吃透。我把每道题的关键拆解写在这里。3.1 用栈实现队列题目要求使用两个栈实现队列的 push、pop、peek、empty 操作。核心思路是双栈倒腾一个栈负责入队input stack一个栈负责出队output stack。入队时直接压入 input出队时如果 output 为空就把 input 里的元素全部弹出并压入 output此时 output 的栈顶就是最早进入的元素。class MyQueue { private: std::stackint inStack; std::stackint outStack; void transfer() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { transfer(); } int result outStack.top(); outStack.pop(); return result; } int peek() { if (outStack.empty()) { transfer(); } return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这里最关键的一点是 transfer 的触发时机只在 outStack 为空时才转移。如果在 outStack 还有元素时就转移会打乱顺序。比如连续 push 了 1、2、3 后 pop 了两次outStack 里剩下 3此时再 push 4如果立即转移顺序就乱了。所以必须“非空不转移、空才全量搬”。我一开始写这道题时犯过一个错误每次 pop 前都转移一次结果把一个简单的 O(1) 摊还操作变成了 O(n)。每次 transfer 后 outStack 里可能有 n 个元素还没出完立刻又转移相当于把前面的搬移全部浪费掉。3.2 用队列实现栈题目要求使用两个队列实现栈的 push、pop、top、empty 操作。这道题有两种主流写法一种是双队列倒腾另一种是单队列倒腾。双队列版本中入栈时把元素放入空队列然后把另一个队列的所有元素依次转移过来保证新元素在队首位置这样出栈时直接取队首即可。单队列实现更简洁也是我推荐优先掌握的版本入栈时先把元素放入队尾然后把队列里前面 n-1 个元素依次取出再放回队尾这样新元素就旋转到了队首。class MyStack { private: std::queueint q; public: MyStack() {} void push(int x) { int size q.size(); q.push(x); while (size--) { q.push(q.front()); q.pop(); } } int pop() { int result q.front(); q.pop(); return result; } int top() { return q.front(); } bool empty() { return q.empty(); } };这个实现有几个细节值得注意push 里的 int size q.size() 必须在 push 新元素之前取因为 push 之后队列 size 变了没法再用 size 表示“原来有几个元素需要旋转到末尾”。我自己第一次写的时候把 size 放在了 push 之后导致每个元素被多旋转了一次结果队首并不是最新元素。3.3 有效的括号这题是栈应用里最基础的匹配类题目。给一个只包含 ( ) [ ] { } 的字符串判断括号是否有效。有效定义是左括号必须用同类型右括号闭合且按正确顺序闭合。核心思路遍历字符串遇到左括号就压栈遇到右括号弹出栈顶检查是否是对应的左括号。class Solution { public: bool isValid(std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { return false; } char top st.top(); st.pop(); if (c ) top ! () return false; if (c ] top ! [) return false; if (c } top ! {) return false; } } return st.empty(); } };这段代码里有个很容易漏的判断遍历完字符串后栈必须为空才说明所有左括号都被匹配掉。如果最终栈里还有残留的左括号说明有未闭合的括号应该返回 false。这个“最后判空”是我见过很多人掉坑的地方。另一个细节是提前剪枝如果字符串长度是奇数直接返回 false因为有效的括号对长度必然是偶数。这个优化虽然不影响复杂度量级但在判断长字符串时能省一半遍历。3.4 删除字符串中的所有相邻重复项这道题的经典解法是用栈模拟删除过程遍历字符串如果当前字符和栈顶相同就弹出栈顶相当于删除这一对相同项否则压入当前字符。遍历结束后把栈里剩余字符拼接成结果返回。class Solution { public: std::string removeDuplicates(std::string S) { std::string result; for (char c : S) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; } };这里有个技巧直接用 std::string 当作栈来用省去了 std::stack 再转字符串的步骤。string 本身就支持 back()、push_back()、pop_back()行为上就是一个字符栈。很多人在写出 std::stack 版本后还多写了一遍“把栈倒出来再 reverse”很没必要。理解了这道题再往深一层就是“删除所有相邻重复项”的进阶版重复 k 次的字符串消除。核心思路是用栈记录“字符 连续出现次数”遇到相同字符时计数加一达到 k 时出栈。这题在不少公司的笔试里出现过本质是相邻项匹配问题的变体。3.5 逆波兰表达式求值逆波兰表达式后缀表达式求值是所有栈应用里最经典的考题。它的好处在于不需要处理括号优先级只需要从左到右扫描遇到数字压栈遇到运算符就弹出两个操作数计算结果后压回栈中。class Solution { public: int evalRPN(std::vectorstd::string tokens) { std::stackint st; for (const std::string token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else if (token /) st.push(a / b); } else { st.push(std::stoi(token)); } } return st.top(); } };这道题最容易踩坑的细节是运算顺序先弹出的是右操作数 b后弹出的是左操作数 a。因为栈是 LIFO 结构先弹出的元素实际上是更靠后的操作数。比如表达式 3 4 -先弹出 4 作为 b再弹出 3 作为 a正确的运算是 3 - 4 -1。如果写反了就会得到 4 - 3 1结果完全错误。另外一个隐藏坑是除法涉及负数的情况。C 里整数除法是向零截断的而很多后台题目的预期是向零截断而不是向下取整所以 a / b 直接写就行。但如果你自己用 Python 刷这题就要小心Python 的 // 是向下取整负数情况会出错需要 int(a / b) 修正一下。4. 栈和队列的高阶应用与进阶延伸Day 10 的基础题吃透之后栈和队列还有两个非常高频的进阶方向单调栈和单调队列。它们虽然不一定出现在 Day 10 的课程里但既然专题是“栈和队列”提前把这两个进阶方向串起来说后边学到时会轻松很多。4.1 单调栈解决“下一个更大元素”类问题单调栈指的是栈内元素按递增或递减顺序排列。它的经典应用是找数组里每个元素右边第一个比它大的元素LeetCode 第 739 题“每日温度”就是这个场景。单调栈的核心思想是遍历数组时把“还没找到答案的元素”的下标压入栈中。当遇到一个新元素大于栈顶元素时说明栈顶元素找到了答案弹出并记录结果。栈内始终保持从栈底到栈顶递减或递增因此称为单调栈。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint result(n, 0); stackint st; for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { int idx st.top(); st.pop(); result[idx] i - idx; } st.push(i); } return result; }这个模板的精髓在于每个元素最多入栈一次、出栈一次所以整体时间复杂度是 O(n)而不是暴力解法的 O(n^2)。我自己的理解方式是单调栈解决的其实是“延迟匹配”的问题。当前元素不知道后面的情况所以只能先存起来当后面的元素出现时它终于可以“兑现承诺”把之前等它的若干元素一次性消化掉。4.2 单调队列解决“滑动窗口最大值”问题滑动窗口最大值是队列专题里最经典的题目。暴力解法在每个窗口内遍历 k 个元素找最大值整体复杂度 O(nk)。单调队列的解法用 O(n) 搞定。思路是维护一个“从队首到队尾递减”的双端队列队首始终是当前窗口的最大值。每次右移窗口时先从队尾弹出比新元素小的元素因为它们在新元素存在期间不可能成为最大值再把新元素入队同时检查队首元素是否已经滑出窗口如果滑出就弹出。class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint result; dequeint dq; for (int i 0; i nums.size(); i) { // 队尾弹出比当前元素小的 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 队首滑出窗口 if (dq.front() i - k) { dq.pop_front(); } // 窗口形成后记录结果 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };这里有一个很核心的细节队列里存的是下标而不是值。存下标的好处是可以同时判断“窗口范围”和“数值大小”只存值的话你无法判断队首是否已滑出窗口。这段代码里 while 弹出队尾的条件是 而不是 。如果用 当两个相同最大值同时出现在窗口里时队列里就会保留两个相同值但靠前的那个在滑动时可能已经被移出窗口却仍然留在队列里造成结果不准确。用 可以保证靠后的新值把旧值顶掉旧值即使还在窗口内也不会影响正确性。4.3 优先队列堆与栈队列的区别优先队列std::priority_queue虽然名字里有“队列”但它和栈、队列完全是两个逻辑层次。栈和队列管的是“进出顺序”优先队列管的是“优先级顺序”每次出队的都是当前元素中优先级最高的那个。优先队列内部实现通常是二叉堆插入和删除的时间复杂度都是 O(log n)。它在解决 Top K 问题、合并 K 个有序链表、任务调度等问题里出镜率极高。比如“前 K 个高频元素”那道经典题做法就是先用哈希表统计频率再用大小为 K 的小顶堆维护出现频率最高的 K 个元素。堆顶是这 K 个里频率最低的遇到新元素时如果频率高于堆顶就替换堆顶并重新调整堆。class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int num : nums) freq[num]; // 小顶堆pair频率, 元素 auto cmp [](pairint, int a, pairint, int b) { return a.first b.first; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) heap(cmp); for (auto p : freq) { heap.push({p.second, p.first}); if (heap.size() k) { heap.pop(); } } vectorint result; while (!heap.empty()) { result.push_back(heap.top().second); heap.pop(); } return result; } };这里特别需要注意优先队列定义时第三个模板参数的写法。C 的 priority_queue 默认是大顶堆第三个模板参数是一个仿函数类型里面用 表示“优先级低”的排在前面构造出小顶堆。很多人第一次写时容易写成 sort 里的比较器习惯搞反方向。5. 刷题踩坑实录与高效编码技巧这一节把我在做这个专题时真正踩过的坑和总结出的经验记录下来很多都是题解里不会写但实战中非常影响效率的细节。5.1 栈的遍历问题C 的 std::stack 没有迭代器不支持范围 for 循环遍历。如果你需要遍历栈中所有元素只能逐个 pop这会破坏栈结构。如果要遍历且保留栈内容需要先把元素复制一份或者改用 deque/vector 自己维护。我在刚开始刷题时经常犯一个毛病想把栈里的内容打印出来调试结果写完发现输出完栈也空了后续逻辑全乱。后来养成一个习惯凡是调试阶段需要看栈内容就用一个临时栈做倒腾输出完再恢复原样。5.2 queue 没有 clear 方法std::queue 没有 clear()。清空一个队列的方法是直接赋值为一个新的空队列std::queueint q; // 清空 q std::queueint();我在写“用队列实现栈”时一度想找 q.clear()结果发现没有还愣了一下。这个细节在面试时突然被问到容易卡壳提前知道能少点尴尬。5.3 循环 vs 递归什么时候用栈替换很多递归代码都可以改成用栈模拟的迭代版本。判断标准是递归里有“先处理子问题再回来自处理”的过程就可以用栈保存“现场”。比如二叉树的前序遍历递归版本非常好理解void preorder(TreeNode* root) { if (!root) return; visit(root); preorder(root-left); preorder(root-right); }改成非递归的栈版本vectorint preorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; if (root) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; }对比一下就能看出递归方法里“先左后右”的访问顺序在栈版本里必须用“先压右再压左”的入栈顺序来保证。因为栈是后进先出右子树先入栈反而会后访问。很多人在简历上写了“熟悉常见数据结构”但一问到“递归转迭代怎么做”就露馅。栈相关的题目练熟之后这类问题就能答得很有底气。5.4 用 string 模拟栈的小技巧前面在“删除相邻重复项”里提到了用 std::string 当字符栈这个技巧可以推广到很多字符串处理场景。比如“简化路径”那道题需要按 / 分割路径片段遇到 . 忽略遇到 .. 弹出上一级目录最后拼接结果。用 vector 或直接 string 当栈处理起来逻辑非常顺。class Solution { public: string simplifyPath(string path) { vectorstring st; // 把 vector 当作栈用 int n path.size(); int i 0; while (i n) { // 跳过斜杠 while (i n path[i] /) i; // 提取片段 string name; while (i n path[i] ! /) { name.push_back(path[i]); i; } if (name ..) { if (!st.empty()) st.pop_back(); } else if (name . || name.empty()) { // 跳过 } else { st.push_back(name); } } string result /; for (int j 0; j st.size(); j) { if (j 0) result /; result st[j]; } return result; } };这里用 vector 模拟栈比 std::stack 好的地方在于可以随机访问方便最后拼接结果。std::stack 只能看栈顶还得把元素倒出来才能拼路径很别扭。这个“用 vector 代替 stack 在特殊场景下更好用”的经验在不少字符串题里都能省事。6. 容器适配器与代码随想录的刷题方法论最后从整体方法论的角度聊聊栈和队列这个专题在代码随想录训练营中的位置以及刷题时值得坚持的几个习惯。6.1 代码随想录的选题逻辑代码随想录的风格是“少而精”每个专题挑出来的题目都是同类题里最能建立典型思维的。栈和队列这个专题选的五道题——用栈实现队列、用队列实现栈、有效的括号、删除相邻重复项、逆波兰表达式求值正好覆盖了“结构互转”“匹配检查”“模拟运算”三大场景。这其实也是面试官最爱考的三种角度结构互转类用栈实现队列等考察对操作时序的精确理解匹配类有效括号等考察栈“后退一步”特性在嵌套场景的应用模拟类逆波兰表达式等考察从抽象规则到具体实现的转换能力把这三类题吃透基本就掌握了栈和队列在面试中的全部基础考点。6.2 刷题过程中的几个务实建议第一别急着看题解。栈和队列的题有一个特点思路懂了之后代码往往不难写难的是“从题目描述到想到用栈”这一步。这个跳跃需要自己尝试过才能形成直觉。我自己的经验是每道题至少逼自己先想15分钟哪怕想错了再去看题解时理解的深度完全不一样。第二写完之后要自己背写一遍。不是背代码而是在不看题解的情况下列出用什么数据结构、进出顺序怎么控制、边界条件有哪些。列出这三项之后代码基本就能写出来。这个方法尤其适合“用栈实现队列”这类逻辑绕的题。第三多思考一题多解。“用队列实现栈”就有双队列和单队列两种解法两种都值得写一遍。双队列版本思路直观适合理解单队列版本代码简洁适合面试时快速写出。两个版本都写一遍能把队列操作理解得更透。第四做完看官方题解是否使用了更优的容器。比如“删除相邻重复项”里用 string 当栈就是一个典型的容器优化。同样是栈的思想换一个载体把代码精简一半。这类优化看得越多对语言的掌握就越深。6.3 栈和队列与系统层面的联系栈和队列不只是刷题用的抽象结构它们在系统底层有非常具体的映射。函数调用时每一次调用都会在“调用栈”上压入一个栈帧包含参数、返回地址、局部变量。函数返回时栈帧被弹出控制权回到调用者。这就是“栈”这个名字在计算机系统里最原始的意义。理解了这一点再回头看“有效的括号”这道题本质就是在模拟嵌套结构的闭合匹配和编译器检查括号配对的过程一模一样。队列则更常出现在“生产者-消费者”场景。操作系统里的任务调度、消息队列里的事件缓冲、网络缓冲区中的数据包排队都是队列的应用。Java 里的阻塞队列、线程池里的任务队列本质上都是在利用 FIFO 保证“先来先服务”的公平性。所以栈和队列不只是算法题里的主角更是理解计算机系统运行机制的一把钥匙。把这两个结构理解透后面学递归、学习系统设计都会更顺畅。我个人在实际操作中的体会是这个专题的题目数量不多但每一道都值得反复咀嚼。尤其是“用栈实现队列”和“用队列实现栈”一正一反两道题把两个结构的操作时序彻底理清了。后面遇到任何队列相关的进阶题比如单调队列、双端队列、优先队列都能快速定位到“队列的核心是先进先出但如何控制进出时机才是解题关键”这个本质上。刷完这个专题再顺手用单调栈、单调队列做两道进阶题整个“栈和队列”的知识体系才算真正闭环。