1. 项目概述当数据结构开始玩角色互换最近在刷算法题时遇到一组特别有意思的题目它们都在玩数据结构角色互换的游戏——用栈实现队列、用队列实现栈、括号匹配检测、相邻重复项消除以及逆波兰表达式求值。这组题目看似基础实则暗藏玄机特别适合用来检验对数据结构的理解深度。我在LeetCode上刷到这些题时一开始觉得简单实际动手才发现处处是坑今天就把我的解题思路和踩坑实录分享给大家。2. 核心数据结构特性解析2.1 栈与队列的本质区别栈Stack是LIFO后进先出结构就像叠盘子最后放上去的盘子最先被拿走。队列Queue则是FIFO先进先出结构像排队买奶茶先来的人先被服务。这两种结构的根本差异决定了它们的适用场景栈适合函数调用栈、表达式求值、括号匹配、DFS算法队列适合BFS算法、缓存实现、任务调度2.2 为什么需要互换实现面试中常被问到用栈实现队列这类问题主要考察对数据结构本质的理解程度灵活运用基础数据结构的能力时空复杂度分析能力实际工程中虽然很少需要这样互换但这种思维训练能帮助我们更好地理解抽象数据类型(ADT)与具体实现的关系。3. 用栈实现队列LeetCode 2323.1 双栈解法思路队列是FIFO而栈是LIFO要用栈模拟队列需要两个栈配合输入栈(stack_in)专门处理push操作输出栈(stack_out)专门处理pop/peek操作class MyQueue { private: stackint stack_in; stackint stack_out; public: MyQueue() {} void push(int x) { stack_in.push(x); } int pop() { if(stack_out.empty()) { while(!stack_in.empty()) { stack_out.push(stack_in.top()); stack_in.pop(); } } int res stack_out.top(); stack_out.pop(); return res; } int peek() { int res this-pop(); stack_out.push(res); return res; } bool empty() { return stack_in.empty() stack_out.empty(); } };3.2 时间复杂度分析Push操作直接压入输入栈O(1)Pop/PeeK操作摊还分析下也是O(1)最坏情况当输出栈为空时需要将输入栈所有元素转移O(n)但每个元素最多被转移一次均摊下来仍是O(1)3.3 注意事项转移条件只有当输出栈为空时才需要从输入栈转移元素转移操作必须一次性转移完输入栈所有元素空队列判断需要同时检查两个栈是否都为空4. 用队列实现栈LeetCode 2254.1 单队列解法虽然可以用两个队列实现但单队列更高效。核心思路每次push后立即将新元素调整到队首。class MyStack { private: queueint q; public: MyStack() {} void push(int x) { int size q.size(); q.push(x); for(int i 0; i size; i) { q.push(q.front()); q.pop(); } } int pop() { int res q.front(); q.pop(); return res; } int top() { return q.front(); } bool empty() { return q.empty(); } };4.2 时间复杂度分析Push操作O(n)因为需要调整队列顺序Pop/Top操作O(1)直接操作队首元素4.3 为什么不用双队列双队列方案需要一个主队列和一个辅助队列每次push时先放入辅助队列将主队列元素全部转移到辅助队列交换两个队列的角色虽然时间复杂度相同但单队列实现更简洁内存使用也更高效。5. 有效的括号LeetCode 205.1 栈的经典应用括号匹配是栈的典型应用场景遇到左括号入栈遇到右括号检查栈顶是否匹配。bool isValid(string s) { 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 ! () || (c ] top ! [) || (c } top ! {)) { return false; } } } return st.empty(); }5.2 边界条件处理字符串为空直接返回true只有右括号栈为空时遇到右括号只有左括号最后栈不为空括号类型不匹配右括号与栈顶左括号不匹配5.3 优化技巧可以使用哈希表存储括号对减少条件判断unordered_mapchar, char pairs { {), (}, {], [}, {}, {} };6. 删除字符串中所有相邻重复项LeetCode 10476.1 栈解法这题是括号匹配的变种用栈可以高效处理相邻重复项。string removeDuplicates(string s) { string res; // 用字符串模拟栈 for(char c : s) { if(!res.empty() res.back() c) { res.pop_back(); } else { res.push_back(c); } } return res; }6.2 时间复杂度分析时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况下需要存储整个字符串6.3 进阶问题如果要求删除重复项直到无法删除为止如LeetCode 1209需要记录字符计数string removeDuplicates(string s, int k) { vectorpairchar, int st; // 字符计数 for(char c : s) { if(!st.empty() st.back().first c) { st.back().second; } else { st.push_back({c, 1}); } if(st.back().second k) { st.pop_back(); } } string res; for(auto p : st) { res.append(p.second, p.first); } return res; }7. 逆波兰表达式求值LeetCode 1507.1 什么是逆波兰表达式逆波兰表达式后缀表达式的特点操作符在操作数之后不需要括号来指定运算顺序非常适合用栈来计算示例中缀2 3 * 4后缀2 3 4 * 7.2 栈解法实现int evalRPN(vectorstring tokens) { stackint st; for(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(); }7.3 注意事项操作数顺序减法和除法要注意操作数顺序字符串转数字使用stoi()函数除法处理题目说明是整数除法向零取整栈中最终只会剩一个元素8. 综合对比与解题套路8.1 这组题目的共同特点都涉及栈或队列的基本操作都需要考虑边界条件时间复杂度通常为O(n)空间复杂度通常为O(n)8.2 解题通用思路明确题目要求的数据结构特性选择合适的数据结构栈/队列处理边界条件空输入、单个元素等考虑时空复杂度优化8.3 常见错误与调试技巧栈/队列为空时的操作总是先检查是否为空元素类型转换字符串转数字要处理异常操作顺序特别是减法和除法使用IDE调试逐步跟踪栈/队列状态9. 扩展练习与变种题目9.1 推荐练习题目LeetCode 155 最小栈LeetCode 239 滑动窗口最大值LeetCode 316 去除重复字母LeetCode 402 移掉K位数字LeetCode 735 行星碰撞9.2 实际工程应用场景浏览器前进后退功能双栈实现线程池任务队列队列实现代码编辑器括号匹配栈实现计算器表达式求值逆波兰表达式文本编辑器撤销操作栈实现10. 个人刷题心得刷这组题目最大的收获是理解了数据结构的抽象与实现是可以分离的。栈和队列作为抽象数据类型(ADT)可以用不同的具体数据结构来实现。在实际编码时我有几点深刻体会画图辅助在纸上画出栈和队列的变化过程能极大帮助理解测试用例要覆盖各种边界情况特别是空结构和单个元素代码简洁性有时候简单的实现反而更不容易出错复杂度分析不能只看最坏情况摊还分析也很重要最后分享一个调试小技巧在实现这些数据结构时可以添加一个打印内部状态的辅助函数这样能直观看到每次操作后数据结构的变化便于定位问题。
