栈与队列互相转换：四道题彻底搞懂数据结构本质

1. 栈和队列互相转换练的到底是什么很多人做这四道题的时候第一反应是背题232用两个栈225用一个队列20用栈匹配1047用栈去重。做完就忘考完也不会。我一开始也这样后来反复刷、反复犯错才慢慢意识到这几道题放在同一天是有道理的它们表面上是在教怎么用容器写容器实际上是在逼你理解一个底层问题数据结构的行为接口和它的内部实现是可以完全解耦的。我用一个生活中的例子来类比。队列就像食堂打饭的队伍先到的人先打到饭先进先出FIFO栈就像一摞盘子后放上去的盘子总会先被人拿走后进先出LIFO。232那道题是要求你只用拿盘子的方式栈硬生生模拟出按排队顺序打饭的效果225则是反过来让你用排队的方式队列模拟出后放的盘子先被拿走的效果。这个翻译过程不是没事找事。现实工程里经常出现一类需求你手里的现成组件只提供了A结构的能力但业务层需要的却是B结构的语义。比如解析XML标签时你需要用栈的顺序去校验嵌套关系而任务调度模块里你又需要队列保证公平性。理解如何把一个语义翻译成另一个语义比记住某个容器的API重要得多。而且这两道题还藏了一个更深的问题为什么大家约定俗成都用两个栈来实现队列却可以用一个队列就实现栈这个不对称性背后其实是逻辑上的必然后面我会专门讲。除此之外20题和1047题是把栈用在真实场景里配对、消消乐。它们看起来不再需要模拟容器了用STL里现成的std::stack就能做但如果你只是调包那就错失了这一整组题最宝贵的部分——这两道题会告诉你栈到底擅长什么样的计算模式。第一天的题目练完最好能得出一个自己的判断标准什么信号出现的时候第一反应就该往栈上想我在第6章给出我的答案。2. 232用输入栈加输出栈把一个LIFO翻译成FIFO这题要求实现MyQueue支持push、pop、peek、empty四个操作。队列的语义很简单先进入的元素先出来。栈的特性恰恰相反后进去的先出来。所以直接拿一个栈去当队列肯定不行。两个栈为什么就能行核心逻辑只有一句话数据在第一个栈里进在第二个栈里出中间经过一次倒腾顺序就被翻转了。2.1 为什么倒一次就能翻转顺序先想清楚这个数学事实把一个序列依次push进栈再依次pop出来放进另一个栈整个序列的顺序会被反转两次不一定准确说是这样——原始序列是[1, 2, 3]依次push到栈A后栈A从顶到底依次是3, 2, 1然后把栈A的元素全部pop出来、依次push进栈B栈B从顶到底就变成了1, 2, 3。此时从栈B执行pop得到的顺序是1, 2, 3正好是原始队列出队的顺序。一次全部转移就把顺序翻转回来了。那为什么不每次push都立刻翻转而是等到pop的时候才翻转因为翻转是有成本的每个元素理论上只需要被翻转一次就够了。如果你每次都翻转元素会在两个栈之间来回搬运多次时间复杂度就劣化了。这个懒的思路正是摊还分析的灵魂。2.2 代码实现写出带缓冲的版本我见过的教程多半直接给简化版但实际生产里要考虑更完整的状态。下面这个版本是我在实际刷题和写测试时一直用的比较稳健class MyQueue { private: std::stackint stIn; // 负责接收push进来的元素 std::stackint stOut; // 负责pop和peek时提供元素 public: MyQueue() {} void push(int x) { stIn.push(x); } int pop() { // 只有输出栈为空时才需要从输入栈倒数据 if (stOut.empty()) { while (!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } } int result stOut.top(); stOut.pop(); return result; } int peek() { // 复用pop逻辑然后把元素放回输出栈顶 int result this-pop(); stOut.push(result); return result; } bool empty() { return stIn.empty() stOut.empty(); } };这里最容易被忽略的两个点是peek的实现和pop的前置判断。peek只想知道队头是什么不能真的把元素移出去所以先调用一次pop拿到结果后再把这个值推回stOut队头的身份并不会改变。pop里的前置判断只在输出栈为空时才倒数据是为了保证顺序不错乱如果stOut里还有残留元素说明这些元素已经排好了队必须让它们先出去此时若强行再倒一批进来会把新元素压在老元素上面顺序就乱了。2.3 摊还复杂度为什么整体是O(1)这题面试经常追问时间复杂度第一次见很容易被绕进去。每个元素的生命周期是这样的push进stIn一次转移时进stOut一次出队时pop一次。转移操作虽然是O(n)但它不是每次pop都发生。每个元素只会被转移一次所以把m次操作看成一个整体转移总代价是O(m)单次操作均摊下来就是O(1)。这就是经典的摊还分析amortized analysis。如果你面试时被问到建议把这句话讲清楚接口层的单次操作可能是O(n)但一系列连续操作的总代价是O(n)摊到每一次就是O(1)。头一次体会数据搬移的代价分配就是做这题最大的收获。3. 225用队列实现栈从两队列版本到单队列优化这道题乍看和232是镜像题一个用栈模拟队列一个用队列模拟栈。但写起来你会发现它们完全不是平等的难度——用队列模拟栈其实更简单而且两个队列都不是必须的。很多人死记需要用两个队列其实一个队列就能搞定关键是理解一个简单的操作把队头的元素循环挪到队尾就能改变队列内部的出场顺序。3.1 两个队列版本的直观思路先按常规解法来。定义两个队列que1和que2push时直接入que1pop时把que1中除了队尾那个元素之外的所有元素全部搬进que2然后que1里剩下的唯一元素就是要弹出的栈顶弹出它之后交换que1和que2的指针。为什么要把除队尾外的元素都搬走因为队列是先进先出队头是最早进来的元素而我们要弹的是最近进来的元素也就是队尾。为了拿到队尾只能让前面所有元素让路。这个思路不难但代码里总有两处容易写错一是搬移时的循环边界二是搬完后别忘了交换两个队列。3.2 单队列优化版重新定义队尾就是栈顶后来我在实际练习中发现两个队列版本完全可以优化成一个队列。思路转变很关键不把队列的队头当栈顶而是把队列的队尾当栈顶。push操作直接入队因为新元素总是排在队尾天然就是新的栈顶。那pop怎么办要让队尾元素出队需要先把前面的所有元素依次挪到后面也就是每次取出队头并重新入队循环size - 1次此时原来的队尾元素变成了队头再执行一次pop就拿到了。class MyStack { private: std::queueint que; public: MyStack() {} void push(int x) { que.push(x); } int pop() { int size static_castint(que.size()); size--; // 只需要挪 count-1 个元素 while (size--) { que.push(que.front()); que.pop(); } int result que.front(); que.pop(); return result; } int top() { return que.back(); // 队尾就是栈顶 } bool empty() { return que.empty(); } };你会发现这个版本的top()特别优雅直接返回que.back()因为队尾就是栈顶根本不需要为了看它而挪动任何元素。pop的循环次数里有个坑拿到size后必须自减一次否则会把目标元素自己也挪到队尾去结果弹出来的就是下一个元素了。我第一遍写的时候就是忘了自减导致弹出结果总是不对白白调试了很久。3.3 为什么232需要两个栈225一个队列就够这是很多人做完这两题后最困惑的一点。我的理解是这样栈和队列的不对称性源于它们的基础操作能力不同。队列比栈多一个访问队尾的能力吗并不完全是。更本质的差异是队列允许你从一端出、另一端入相当于你可以把元素在内部循环倒腾而不改变它们的相对线性顺序栈只能在一端操作你没法在不借助外部容器的情况下访问到栈底的元素。用队列实现栈时单队列能通过队头搬队尾的操作把先进队的元素依次挪到后进队的元素后面形成后进先出的效果。这个循环搬运动作只涉及队列自身的pop和push不需要第二个容器。而用栈实现队列时栈没有底部访问的能力你不借助另一个栈就没法拿到最底部的元素所以两个栈是必须的。理解了这个差异以后再遇到类似的互相模拟问题就不会再凭感觉猜要几个容器了。4. 20括号配对是栈的原生主场20题问的是给定一个只包含()[]{}的字符串判断括号是否有效。所谓有效就是三种规则同时满足左括号必须用同类型的右括号闭合左括号必须以正确的顺序闭合不能出现交叉配对比如([)]就是典型反例。这个场景如果不用栈你会发现写起来非常别扭你需要记住最近一个未配对的左括号是什么然后马上检查下一个右括号是否和它匹配。这不就是后进先出吗最近出现的未配对左括号优先级最高必须最先被配对——正好是栈顶元素。所以看到括号匹配第一反应应该是栈这不是套路而是数据结构的性质决定的。4.1 左括号入栈、右括号匹配还是用HashMap预存配对关系比较朴素的做法是遇到左括号就压栈遇到右括号就查看栈顶是不是对应的左括号。判断对应时如果用if-else写三种括号代码会很臃肿而且容易漏。更简洁的方式是用一个哈希表预先存好右括号和左括号的对应关系class Solution { private: std::unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; public: bool isValid(std::string s) { if (s.size() % 2 ! 0) return false; // 奇数长度一定无效 std::stackchar st; 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(); } };这里面有几个细节值得单独说。第一栈空时遇到右括号直接返回false因为没有任何左括号能和它配对。第二遇到右括号时比较的是st.top() ! pairs[c]这里利用了哈希表把右括号映射到它应该配对的左括号一旦不相等就说明出现了交叉嵌套直接失败。第三遍历结束后不能直接返回true必须确认栈是否为空否则会出现()(这种情况——所有括号都配对成功了但最后还有一个落单的左括号。4.2 奇数长度剪枝是不是画蛇添足我第一次看到if (s.size() % 2 ! 0) return false;时觉得没必要多一行代码还影响性能吗后来实测发现这个剪枝不仅仅是微优化。如果输入全是一串左括号(((((((((((((((((且长度是奇数那么遍历完整个字符串要经过一万次循环和压栈最终才发现栈不为空而有了奇数剪枝一条指令就能直接返回。虽然最坏复杂度都是O(n)但常数项差距在极端用例下非常明显。力扣的测试用例里经常有针对纯左括号长串的极端测试这个剪枝能帮你稳定地少跑一大截。还有一类隐藏极深的坑是有些写法用int类型的栈存字符的ASCII码然后拿ASCII码做差值判断。比如判断c - st.top() 1 || c - st.top() 2因为()的ASCII差值是1[]和{}的差值是2。这在单个字符时确实成立但非常不直观而且容易因为阅读者不熟悉ASCII码而埋下隐患。我建议还是用哈希表配对的写法可读性高得多也方便以后扩展到更多配对符。4.3 这题背后的一类算法顺序合法性校验括号匹配不只出现在刷题里。编译器解析代码时、HTML解析器校验标签闭合时、计算带括号的数学表达式时全都在做同样的事情维护一个待闭合的上下文栈遇到开启符就压栈遇到闭合符就查找栈顶。比如你在浏览器里写HTMLdiv标签相当于左括号/div相当于右括号浏览器解析DOM树时用的就是这套栈式校验。所以这题的面试变体特别多比如判断XML是否合法、校验简单的Markdown标记是否闭合核心解法完全一样。理解到这一层20题就不再是一道孤立的题而是整个上下文匹配算法家族的第一课。5. 1047删除相邻重复项用String本身当栈1047题要求给出字符串abbaca每次删除相邻且相同的两个字符并重复这个操作最终返回没有相邻重复项的字符串。示例里abbaca经过两次删除变成ca过程是abbaca - aaca删除bb再到ca删除aa。注意这个删除完之后之前的字符会和后面的字符形成新的相邻关系还要继续删除这种连续反应式的消除正是栈最擅长的场景。5.1 标准做法把字符一个个压栈相同就抵消最直觉的解法是维护一个栈遍历每个字符如果栈顶和当前字符相同说明它俩是相邻重复项配对成功直接弹出栈顶否则把当前字符压入栈。最终栈里剩下的字符就是消除全部相邻重复项后的结果。string removeDuplicates(string s) { stackchar st; for (char c : s) { if (!st.empty() st.top() c) { st.pop(); } else { st.push(c); } } // 从栈中取出结果 string result; while (!st.empty()) { result.push_back(st.top()); st.pop(); } reverse(result.begin(), result.end()); return result; }这个写法有两个小细节。第一判断条件必须写成!st.empty() st.top() c顺序不能换否则栈空时st.top()会触发未定义行为。第二最后从栈里取元素时出栈顺序是反的必须reverse一次才能得到正确的字符串。很多人在这一步栽跟头因为着急把结果return出来结果发现顺序全反了。5.2 更常用的技巧用String本身当栈省掉最后反转上面那段代码虽然功能正确但到需要拼结果的时候还得单独reverse不够干净。我在刷题时发现一个特别常用的技巧直接把结果字符串当成栈来用用result.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; }这一版没有任何多余的栈和逆转操作result本身即是栈又是输出代码量直接减了一半。这个字符串当栈的技巧在后续很多字符串处理题里都非常好用尤其是涉及删除、替换、回退的场景。它不会改变复杂度依然是一次遍历O(n)但省掉了栈到字符串的搬运过程实际跑起来快很多。5.3 进阶原地双指针把空间复杂度降到O(1)如果你认真分析过上面的代码会发现空间复杂度是O(n)最坏情况字符串完全没有重复项栈要承载所有字符。那么能不能连这个额外的空间都省掉直接在原字符串上修改答案是可以用双指针。思路是这样的把原字符串切成两个区域左区域是处理后放入的字符右区域是还没遍历到的字符。我们用一个slow指针表示处理区目前的有效长度fast指针负责往前遍历。每次fast指向一个字符就检查它和slow - 1指向的字符是否相同相同则抵消slow--回退一步不同则放入处理区s[slow] s[fast]。string removeDuplicates(string s) { int slow 0; for (int fast 0; fast s.size(); fast) { if (slow 0 s[slow - 1] s[fast]) { slow--; } else { s[slow] s[fast]; } } s.resize(slow); return s; }这个写法的关键在于slow回退那一步。比如处理abba时遍历完前三个字符a, b, b之后slow会经历0-1放a、1-2放b、2-1第二个b和第一个b抵消此时slow指向的位置其实是原本第二个b的存储位置下一个字符a到来时会放在slow指向的位置上相当于把第一个a的位置也覆盖了——因为第一个a和下一个a又构成了新的相邻重复。这种回退覆盖其实就是栈顶弹出的等价操作只不过是在同一个数组上完成的。我最初写这段时总是忘记slow 0这个前置条件导致slow回退成负数程序直接崩溃。这类原地栈的写法一定要警惕指针下限问题。5.4 为什么这题和栈的关系很多人看不出来1047题不像232、225那样明摆着要模拟容器很多人会误以为它是字符串处理题应该用erase之类的方法硬删。硬删的问题在于每次删除后erase要移动后面所有字符最坏情况下会退化成O(n^2)。而且你很难处理删除后又产生新的相邻重复这种连锁反应因为每次删除后你的遍历位置都得重新调整。栈解法之所以干净是因为栈自动帮你维护了当前序列的末尾状态新字符只需要和末尾比较不需要回头扫描。所以这道题的真正考点不是字符串而是你能不能把需要维护最近状态的问题识别成栈模型。6. 四道题做完我对栈和队列的理解发生了哪些变化四道题刷完我最大的感受不是我会用栈和队列了而是我终于搞清楚了一个问题什么时候该优先想到栈什么时候该想到队列。6.1 一张表看清四道题的本质我把四道题放在一起整理过它们的共性其实非常明显题目数据结构核心操作应用场景一句话本质232stack输入栈输出栈倒腾用LIFO模拟FIFO两次翻转抵消225queue队头反复搬队尾用FIFO模拟LIFO循环旋转暴露队尾20stack压栈、匹配、弹出括号配对、上下文校验最近状态优先闭合1047stack压栈、抵消、弹出相邻重复删除、消消乐末尾状态连续更新第四列的应用场景看起来都不沾边但第三列的核心操作高度统一都是在某个线性序列之上维护一个最近需要处理的状态。20题里最近未配对的左括号优先级最高1047题里最近放入的字符可能是下一个要被抵消的字符232和225则是在状态维护的基础上多了一层接口翻译。6.2 我自己总结的两个判断信号刷完这些题我给自己总结了两条看到题就往对应结构上想的信号需要保持输入顺序、先到先得的场景比如按时间顺序处理任务、广度优先搜索的节点遍历优先想队列需要回退、撤销、就近匹配的场景比如括号闭合、括号内容校验、路径回退、编辑器的撤销操作优先想栈。这两条信号你可以记下来以后看到新题型先问自己一句这个问题的优先级是哪端说了算如果最近进来的元素优先级最高、要先处理它那十有八九是栈如果最早进来的元素优先级最高、应该被先处理那就是队列。6.3 第一次交作业时最容易暴露的问题最后说一个我自己调试过程中最容易被藏起来的问题测试用例的规模越大越要小心递归或栈溢出但刷这些题时真正的坑其实在空容器访问。232的peek里如果先pop但忘了把栈顶放回去后续调用pop时会多弹掉一个元素225的top直接访问back()时如果队列为空会未定义行为所以题目最好保证不会对空栈调用top和pop但自己在写测试代码时也得记得做保护。我在实际练习中用到的自测方法是准备一组随机push和pop的指令序列同时用一个真实的std::queue或std::stack做对照每执行一步就比对结果是否一致。这个对照策略很简单但特别有效我建议你每次做完这类模拟题都用和标准容器对照跑随机操作的方式验证一遍比在脑内模拟一百遍都管用。四道题里我做错最多的是225的单队列版本每次都在size--那一步翻车后来我把操作序列打印出来才看到循环次数多转了一次目标元素被转移到了队列尾部导致弹出错误。这类边界问题刷题时多踩几次印象反而比看别人总结深刻得多。四道题刷完再回头看第一天的自己那时候我只知道栈是后进先出、队列先进先出这两句口号真到用的时候完全不知道该怎么选。现在至少有了一个明确的分析框架先确认题目维护的状态到底是最近优先还是最先优先再决定用哪种结构最后才去考虑是否需要额外容器做平移和翻转。这个思考顺序比任何题解都值得先建立起来。