★ FEATURED ARTICLE 刷到 Day5 栈与队列很多人前面几天还兴致勃勃到这一天突然有点泄气。链表、哈希表好歹能画出结构图栈和队列一眼看去就是两个容器好像什么都讲了又好像什么都没抓住。这篇文章我围绕栈与队列从底层行为、两类容器互转、到括号匹配、相邻重复项消除、逆波兰表达式求值这几个高频场景把原理、代码和容易踩的坑放在一起说清楚。适合刚结束链表和哈希表练习、准备进入容器互转阶段的读者也适合那些模板背得滚瓜烂熟、却说不出“为什么要用两个栈”的人。1. 先把栈和队列的“性格”摸清楚1.1 栈就是一个只能从一端进出的“叠盘子”栈的核心行为就是后进先出英文叫 LIFOLast In First Out。你可以想象厨房里的一摞盘子新洗好的盘子总是放在最上面要用的时候也是先拿走最上面的。栈提供的最关键操作只有几个push把元素放进栈顶pop把栈顶元素移除top只查看栈顶元素不删除。有些语言里叫peek意思一样。为什么这个问题值得单独拎出来讲因为很多人写代码时明明用的是stack脑子里却把它当成vector或者数组来用。栈是一种“受限的线性表”它不是不能存多个元素而是规定你只能从同一端操作。这个限制才是栈的灵魂。如果没有这个限制撤销操作、函数调用、括号匹配这些东西的“最近优先”逻辑就无从谈起。我见过不少初学者纠结一个问题栈底层到底应该用数组还是链表其实在刷题阶段你完全可以直接使用语言自带的标准库实现。C 的std::stack默认底层容器是deque你也可以手动指定为vector或listPython 中可以用普通list模拟Java 里Stack类和Deque接口都能干这活。底层容器不同只会影响内存布局和常数性能不会改变后进先出的语义。栈的常见操作时间复杂度也很漂亮入栈、出栈、查看栈顶都是 O(1)。这里要求的就是“只动尾部”的效率。如果非要去访问栈中间某个元素那就要先把上面所有元素弹出这个成本就是 O(n)。所以刷题时一旦发现自己的代码需要频繁访问栈中间元素大概率是思路错了。1.2 队列就是一个一端进、另一端出的“排队窗口”队列的核心行为是先进先出英文是 FIFOFirst In First Out。最直观的例子就是食堂排队先到的人先打到饭后到的人站在队尾。队列提供的操作也很固定push从队尾加入元素pop从队首移除元素front查看队首元素。C 的std::queue里入队叫push出队叫pop查看队首叫front。很多人第一次写队列时最不习惯的一点是不能像数组那样随心所欲地访问某个下标。队列同样是一种受限容器只不过它把入口和出口分开了。这个特性天然适合任务调度、消息队列、广度优先搜索等场景。你不需要关心队列中间的元素是什么只需要知道谁先来、谁先走。队列的时间复杂度同样很理想入队 O(1)出队 O(1)查看队首 O(1)。C 的std::queue默认也是用deque作为底层容器因此两端操作都高效。这里提醒一句队列的front()和back()可以分别拿到队首和队尾但只有front才是真正“下一个要出去”的元素。面试时会有人把back当front用一跑测试就崩。1.3 很多题考的是“容器的行为”而不是容器内部栈和队列这种结构单独拿出来看真的不难难的是把它们放进具体问题里。你会发现同一道题如果用数组硬模拟也能写出来但代码会变得臃肿而且边界条件特别多。比如后面要讲的括号匹配如果用计数器或者多层if硬写当括号类型变成三种时正确性就很难保证了。而一旦换成栈问题就变成一个非常机械的过程遇到左括号压栈遇到右括号弹栈比较。这不只是“用了栈”而是用栈天然表达了“最近一个未匹配的左括号”这个状态。我在实际刷题过程中还有一个体会栈和队列本身是实现其他抽象结构的“积木”。后面会练习用栈实现队列、用队列实现栈这两道题是 Day5 的灵魂。不要觉得它们只是为了考“你会不会转换容器”它们真正训练的是你对“操作入口”和“数据流动方向”的敏感度。你把这些基础操作玩明白了后面遇到单调栈、优先队列、树的层序遍历才不会觉得莫名其妙。2. 容器互换题是 Day5 的核心用栈实现队列用队列实现栈2.1 用两个栈实现队列核心是“倒一次”题目要求很简单用栈的 API 实现一个队列支持push、pop、peek、empty。只用一个栈肯定不行因为栈的出口和入口都在同一端而队列要求从一端进、另一端出。常规解法是用两个栈一个叫输入栈inStk一个叫输出栈outStk。push的时候直接把元素压入inStk。pop的时候如果outStk非空就直接从outStk弹出栈顶如果outStk为空就把inStk里的所有元素依次弹出并压入outStk。这一步非常关键因为它把元素顺序“倒”了一下inStk的栈顶是最新元素倒进outStk之后outStk的栈顶就变成了最老的元素也就是队首。这个思路很多文章都写过但真正容易忽略的是“为什么要全部倒过去而不是倒一个”。假设inStk里从栈底到栈顶是[1, 2, 3]你希望队列出队顺序是1, 2, 3。如果把inStk全部倒进outStkoutStk从栈底到栈顶是[3, 2, 1]那么outStk.top()就是1。可如果你只倒一个元素outStk栈顶是3直接pop出去就错了。只有全部倒完才能保证“最先进来的元素在栈顶”。class MyQueue { private: stackint inStk; stackint outStk; void transfer() { while (!inStk.empty()) { outStk.push(inStk.top()); inStk.pop(); } } public: void push(int x) { inStk.push(x); } int pop() { if (outStk.empty()) { transfer(); } int val outStk.top(); outStk.pop(); return val; } int peek() { if (outStk.empty()) { transfer(); } return outStk.top(); } bool empty() { return inStk.empty() outStk.empty(); } };这里有个小技巧peek不需要真的“看一眼再塞回去”因为outStk的栈顶就是队首直接返回outStk.top()就行。但要注意先确保outStk非空也就是可能需要先transfer()。复杂度上push是严格的 O(1)。pop看起来最坏是 O(n)因为要搬移所有元素但摊还下来是 O(1)。为什么因为每个元素只会被“倒”一次从inStk弹出一次压入outStk一次最后从outStk弹出一次。这四次操作平摊到整个生命周期里每个元素贡献的代价是常数。面试时如果被问到复杂度不能只答“最坏 O(n)”而要说清楚“均摊 O(1)”。2.2 用一个队列实现栈关键是每次入队后重新排队用队列实现栈这道题经典解法有两个一个是用两个队列一个是只用一个队列。两个队列的做法更直观push时先把元素放进空队列再把另一个队列里的所有元素依次搬过来这样新元素就在队首。但一个队列其实也能做而且代码更短。核心思路是push的时候先把新元素正常入队然后把队列里原来排在它前面的所有元素依次出队再入队。这样一来新元素就“插”到了队首而原来的元素保持相对顺序跟在后面。后面每次pop直接从队首拿就行。class MyStack { private: queueint q; public: void push(int x) { int size q.size(); q.push(x); while (size--) { q.push(q.front()); q.pop(); } } int pop() { int val q.front(); q.pop(); return val; } int top() { return q.front(); } bool empty() { return q.empty(); } };这段代码里push的复杂度是 O(n)因为每次都要把前面的size个元素重新排一遍。pop和top都是 O(1)。相比之前“两个栈实现队列”方向反了过来那里是push便宜、pop摊还便宜这里最直观的解法是push贵、pop便宜。如果你非要用两个队列实现栈也可以push时把元素放入辅助队列然后把主队列所有元素搬进辅助队列再交换两个队列的角色。效果和单队列版本一样代码反而多几行。我个人更推荐大家先把单队列版本想明白因为一旦想明白你就真正理解“队列的顺序是靠不断重排来改变的”这件事。2.3 两种转换放在一起看规律就出来了这两道题经常成对出现不是因为题目长得像而是因为它们在逼你思考同一个问题栈和队列的唯一区别到底是什么栈是“同端进出”队列是“异端进出”。从数据结构的角度看它们都可以用数组实现区别只在操作限制上。所以用栈实现队列本质上是把两个“同端进出”的结构拼成一个“异端进出”的结构用队列实现栈本质上是把“异端进出”的结构通过重排模拟成“同端进出”。刷完这两题我建议你做一个对比表记在自己的笔记里实现目标容器核心操作push 复杂度pop 复杂度empty 判断用两个栈实现队列输入栈 输出栈弹出前先倒数据O(1)摊还 O(1)两个栈都空用一个队列实现栈单个队列入队后整体重排O(n)O(1)队列为空这个表不需要背但一定要自己推一遍。我第一次刷这两道题时过了一周再回来看又忘了为什么pop之前要判空。后来逼自己不看题解把每一步“数据从哪个容器到哪个容器”画出来才算真正记住了。3. 括号匹配、相邻消消乐、逆波兰表达式栈的三次实战3.1 有效的括号匹配问题的核心是“最近的期待”题目是经典中的经典给定一个只包含(、)、[、]、{、}的字符串判断括号是否匹配。最朴素的思路是数括号次数但那只对单一类型括号有效。三种括号嵌在一起时必须记录“最近一个未匹配的左括号是什么”。栈正好干这件事。遇到左括号就把它压入栈顶遇到右括号就和栈顶元素比对。配对成功就弹出不成功就直接返回false。遍历结束后如果栈不为空说明还有左括号没被匹配返回false。bool isValid(string s) { if (s.size() % 2 1) { return false; } stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { return false; } char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }这里有几个容易翻车的细节。第一遇到右括号时栈为空说明出现)(这种非法情况必须立刻返回false。第二三种括号不能只判断数量相等还必须判断类型对应(]就是非法。第三可以先判断字符串长度是奇数就返回false这是一个微小但有效的剪枝。更聪明的写法是用哈希表建立“右括号到左括号”的映射遇到右括号时查表对比。代码会干净一些但核心逻辑完全一样。初学者可以先写if版本理解后再改成映射版本。不要一上来就追求花哨先把“栈顶就是最近期待”这个感觉建立起来。3.2 删除字符串中的所有相邻重复项栈天然适合“消消乐”这道题的描述是这样的给定一个字符串重复地删除相邻且相同的两个字母直到不能再删除为止。比如abbaca先删掉bb剩下aaca再删掉cc最后剩下aa然后再删掉aa结果为空字符串。很多人第一次看会以为只删一轮实际要用“直到不能删”来理解。这个问题的暴力做法是反复扫描但效率太低。用栈的话思路非常顺从左到右扫描每个字符如果栈不为空且栈顶字符等于当前字符就把栈顶弹出相当于“消掉一对”否则把当前字符压入栈。扫描结束后栈里剩下的字符就是答案但要注意顺序是反的需要倒过来。在 C 里有一个小技巧不需要真的用std::stackchar直接用std::string模拟栈操作back()和pop_back()就行。因为字符串本身就支持尾部操作而且最后返回字符串时不需要额外反转。string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; }这段代码的时间复杂度是 O(n)空间复杂度是 O(n)。如果题目允许原地修改也可以把原字符串当作栈用快慢双指针来减小空间占用但在实际笔试中直接用string模拟栈已经足够清晰。这类题目最忌讳的是用“不断删除后重新拼接”的方法每次删除都要复制字符串复杂度会退化到 O(n^2)。这道题和括号匹配有共通点都是需要关注“最近元素”的问题。括号匹配关注的是栈顶的左括号相邻重复项关注的是栈顶的字符。你只要把这个模式识别出来以后看到“相邻”“成对”“匹配”“最近”这些词第一反应就应该是栈。3.3 逆波兰表达式求值后缀表达式用栈算起来很顺手逆波兰表达式又叫后缀表达式运算符写在操作数后面比如[2, 1, , 3, *]对应中缀表达式(2 1) * 3结果是9。面试时它常常以“计算器”的形式出现因为后缀表达式的最大优势是不需要括号也不需要考虑运算符优先级只需要严格从左到右处理。计算过程是这样的遇到数字就压入栈遇到运算符就从栈顶弹出两个操作数先用后弹出的数做左操作数再用先弹出的数做右操作数计算完成后把结果压回栈。最终栈里剩下的唯一元素就是答案。int evalRPN(vectorstring tokens) { stackint st; for (const 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 { st.push(a / b); } } else { st.push(stoi(token)); } } return st.top(); }这里最容易错的点就是减法和除法的操作数顺序。因为栈是先弹出后一个元素再弹出前一个元素所以先弹出来的b是右操作数后弹出来的a是左操作数。写成a - b才对写成b - a就全错了。除法同理a / b才是正确方向。另外要注意除法在 C 里的行为整数除法是向零截断的。大多数在线判题平台都采用这个约定所以直接用st.push(a / b)即可。如果题目要求向下取整那就需要额外处理负数不过那是另一道题了。这三个场景放在一起看你会明白栈的三种典型用途匹配最近状态、消除相邻元素、处理后缀计算。它们和 Day5 目录里的顺序完全一致。刷的时候不要只把代码 AC 了而是试着用自己的话解释“为什么这里要用栈”。解释不清楚就说明还没完全内化。4. 刷题时最容易踩的五个坑4.1 空容器取 top 和 frontC 不会帮你兜底这个问题真的非常常见。很多人在写st.top()或者q.front()之前根本没有判空。在 C 标准库里对一个空容器调用top()或front()是未定义行为也就是说程序可能崩溃也可能返回一个垃圾值完全看运气。刷题时最常见的崩溃场景就是括号匹配里遇到右括号但栈为空以及两个栈实现队列时outStk为空就直接pop。我的习惯是在每一次pop、top、front之前先问自己一个问题“这个容器现在一定非空吗”如果不是就加一个if判断或者提前在逻辑上保证非空。对于用栈实现队列这类题我还会写一个辅助函数来统一处理“从输入栈倒数据”的过程而不是在pop和peek里复制粘贴两遍逻辑。这样能减少不少低级错误。4.2 把“查看栈顶/队首”当成“弹出”导致死循环另一个常见问题是有人写循环时只调用了top()或front()没有调用pop()于是栈顶元素一直不变循环永远结束不了。这种问题最容易出现在“把栈中所有元素转移到另一个栈”这种操作里。正确写法是先记录栈顶值再pop()然后把记录的值压入目标栈。如果漏了pop代码会无限循环。我还见过另一种相反的错误先pop再top。这顺序一错等于丢掉了一个元素然后去读一个新栈顶。逻辑不对结果自然不对。写这种转移代码时建议遵循固定模板while (!st.empty()) { int val st.top(); st.pop(); // 处理 val }这个模板能保证每个元素都被处理且只被处理一次。在以后的许多栈相关题目里它都会反复出现值得形成肌肉记忆。4.3 复杂度分析只说“最坏”没提“均摊”用两个栈实现队列的pop最坏情况下确实需要把inStk里的 n 个元素全部搬到outStk看起来是 O(n)。但如果你直接回答“pop 是 O(n)”面试官通常会追问一句“均摊呢”— 这个问题必须答对。关键理解是每个元素进入输出栈的机会只有一次。它一旦进入outStk后续的pop都是 O(1) 直接弹出。所以连续执行 n 次push和 n 次pop的总代价是 O(n)平均到每次操作仍然是 O(1)。这种摊还分析在数据结构的很多设计中都会遇到。不要因为某一次操作昂贵就误以为整个数据结构低效。4.4 用一堆if硬写括号匹配漏掉类型对应有读者问过我括号匹配能不能用三个计数器分别统计三种括号的数量如果只有一种括号可以但三种括号混合时数量相等并不代表匹配。比如([)]左括号和右括号的数量都是两个但它根本不合法的因为右括号)出现时最近未匹配的左括号是[类型对不上。用if堆逻辑也能写但很容易遗漏情况。我在自己练习时发现最稳妥的办法是先把“当前右括号对应的期望左括号”定义清楚再用统一规则判断。代码里可以用哈希表映射也可以在比较时写成三组判断但规则必须一致。这种问题用栈之后情况就大大简化不需要考虑全局只需要看栈顶。4.5 逆波兰表达式里搞反左右操作数这个坑我在前面已经强调过但值得再单独列一条。很多编程初学者在学栈的题目时第一次接触“弹出两个元素”的场景很容易默认先弹出的元素是左操作数。实际恰好相反后弹出的元素才是表达式中靠前的那个操作数。我用一句话记这个规则后缀表达式的顺序就是“左操作数在前右操作数在后”。入栈时左操作数先入栈所以它在栈底一侧右操作数后入栈所以它在栈顶。弹栈时先把右操作数弹出来再把左操作数弹出来。所以代码里先出栈的是右操作数后出栈的是左操作数。写减法除法时一定要把后弹出的值放在减号或除号左边。5. Day5 之后怎么把这些知识真正留下来5.1 一张表搞定栈和队列的核心差异很多人刷完题过两周再回来栈和队列的行为又混了。我建议你给自己留一张速查表不用很复杂列清楚核心操作和适用场景就行。结构进出方向核心操作典型场景栈同端进出push / pop / top括号匹配、递归调用、撤销操作、逆波兰计算队列一端进另一端出push / pop / front排队任务、BFS、消息队列这张表多看几次再配合几道题基本就不会混淆。如果你发现自己记不住front和back就去想想食堂排队站最前面的front先打到饭后面的back只能等。记忆方法很朴素但管用。5.2 我自己的刷题顺序建议和操作心得如果时间有限我会建议按这个顺序执行而不是把题单从头到尾扫一遍先做“有效的括号”把栈的基本操作和边界判断练熟。再做“删除字符串中的所有相邻重复项”体会“相邻”“最近”这类关键词和栈的对应关系。接着做“逆波兰表达式求值”把“弹出两个数注意顺序”这个动作练成条件反射。最后反过来做“用栈实现队列”和“用队列实现栈”因为它们偏设计需要更强的抽象能力。这个顺序的好处是把简单题放在前面热身把抽象题放在后面脑子和手都能跟上。我自己第一次刷的时候把顺序搞反了先做“用队列实现栈”结果卡了很久。后来把基础题型补上再回头看发现并没有那么难。另外一个小技巧是尽量用带断点调试的方式跑一遍自己写的栈。比如用stackint模拟一个只有三个元素的入栈出栈过程观察每一步top()的值。很多“数据结构好像懂了代码却写不对”的问题通过手动走一遍数据流就能解决。最后再说一下我的个人体会。Day5 的栈与队列表面上是在学两个容器实际是在训练一种思维思考“数据当前最需要被谁处理”。栈负责处理“最近的、刚出现的、还没配对的状态”队列负责处理“最早的、等待最久的数据”。这种思维以后还会用在单调栈、滑动窗口、树的遍历、图的广度优先搜索里。所以这一天值得多花点时间而不是急着把所有题 AC 完就翻篇。
阅读完成 · 觉得有帮助？
