栈与队列互换实现及经典算法题解析

1. 项目概述：当数据结构开始玩"角色互换"

最近在刷算法题时遇到一组特别有意思的题目，它们都在玩"数据结构角色互换"的游戏——用栈实现队列、用队列实现栈、括号匹配检测、相邻重复项消除，以及逆波兰表达式求值。这组题目看似基础，实则暗藏玄机，特别适合用来检验对数据结构的理解深度。我在LeetCode上刷到这些题时，一开始觉得简单，实际动手才发现处处是坑，今天就把我的解题思路和踩坑实录分享给大家。

2. 核心数据结构特性解析

2.1 栈与队列的本质区别

栈（Stack）是LIFO（后进先出）结构，就像叠盘子，最后放上去的盘子最先被拿走。队列（Queue）则是FIFO（先进先出）结构，像排队买奶茶，先来的人先被服务。这两种结构的根本差异决定了它们的适用场景：

• 栈适合：函数调用栈、表达式求值、括号匹配、DFS算法
• 队列适合：BFS算法、缓存实现、任务调度

2.2 为什么需要互换实现？

面试中常被问到"用栈实现队列"这类问题，主要考察：

1. 对数据结构本质的理解程度
2. 灵活运用基础数据结构的能力
3. 时空复杂度分析能力

实际工程中虽然很少需要这样互换，但这种思维训练能帮助我们更好地理解抽象数据类型(ADT)与具体实现的关系。

3. 用栈实现队列（LeetCode 232）

3.1 双栈解法思路

队列是FIFO，而栈是LIFO，要用栈模拟队列，需要两个栈配合：

• 输入栈(stack_in)：专门处理push操作
• 输出栈(stack_out)：专门处理pop/peek操作

class MyQueue { private: stack<int> stack_in; stack<int> 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 注意事项

1. 转移条件：只有当输出栈为空时才需要从输入栈转移元素
2. 转移操作：必须一次性转移完输入栈所有元素
3. 空队列判断：需要同时检查两个栈是否都为空

4. 用队列实现栈（LeetCode 225）

4.1 单队列解法

虽然可以用两个队列实现，但单队列更高效。核心思路：每次push后立即将新元素调整到队首。

class MyStack { private: queue<int> 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 为什么不用双队列？

双队列方案需要：

1. 一个主队列和一个辅助队列
2. 每次push时先放入辅助队列
3. 将主队列元素全部转移到辅助队列
4. 交换两个队列的角色

虽然时间复杂度相同，但单队列实现更简洁，内存使用也更高效。

5. 有效的括号（LeetCode 20）

5.1 栈的经典应用

括号匹配是栈的典型应用场景，遇到左括号入栈，遇到右括号检查栈顶是否匹配。

bool isValid(string s) { stack<char> 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 边界条件处理

1. 字符串为空：直接返回true
2. 只有右括号：栈为空时遇到右括号
3. 只有左括号：最后栈不为空
4. 括号类型不匹配：右括号与栈顶左括号不匹配

5.3 优化技巧

可以使用哈希表存储括号对，减少条件判断：

unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} };

6. 删除字符串中所有相邻重复项（LeetCode 1047）

6.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) { vector<pair<char, 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 150）

7.1 什么是逆波兰表达式？

逆波兰表达式（后缀表达式）的特点：

• 操作符在操作数之后
• 不需要括号来指定运算顺序
• 非常适合用栈来计算

示例：

• 中缀：2 + 3 * 4
• 后缀：2 3 4 * +

7.2 栈解法实现

int evalRPN(vector<string>& tokens) { stack<int> 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 注意事项

1. 操作数顺序：减法和除法要注意操作数顺序
2. 字符串转数字：使用stoi()函数
3. 除法处理：题目说明是整数除法，向零取整
4. 栈中最终只会剩一个元素

8. 综合对比与解题套路

8.1 这组题目的共同特点

1. 都涉及栈或队列的基本操作
2. 都需要考虑边界条件
3. 时间复杂度通常为O(n)
4. 空间复杂度通常为O(n)

8.2 解题通用思路

1. 明确题目要求的数据结构特性
2. 选择合适的数据结构（栈/队列）
3. 处理边界条件（空输入、单个元素等）
4. 考虑时空复杂度优化

8.3 常见错误与调试技巧

1. 栈/队列为空时的操作：总是先检查是否为空
2. 元素类型转换：字符串转数字要处理异常
3. 操作顺序：特别是减法和除法
4. 使用IDE调试：逐步跟踪栈/队列状态

9. 扩展练习与变种题目

9.1 推荐练习题目

1. LeetCode 155 最小栈
2. LeetCode 239 滑动窗口最大值
3. LeetCode 316 去除重复字母
4. LeetCode 402 移掉K位数字
5. LeetCode 735 行星碰撞

9.2 实际工程应用场景

1. 浏览器前进后退功能（双栈实现）
2. 线程池任务队列（队列实现）
3. 代码编辑器括号匹配（栈实现）
4. 计算器表达式求值（逆波兰表达式）
5. 文本编辑器撤销操作（栈实现）

10. 个人刷题心得

刷这组题目最大的收获是理解了数据结构的抽象与实现是可以分离的。栈和队列作为抽象数据类型(ADT)，可以用不同的具体数据结构来实现。在实际编码时，我有几点深刻体会：

1. 画图辅助：在纸上画出栈和队列的变化过程能极大帮助理解
2. 测试用例：要覆盖各种边界情况，特别是空结构和单个元素
3. 代码简洁性：有时候简单的实现反而更不容易出错
4. 复杂度分析：不能只看最坏情况，摊还分析也很重要

最后分享一个调试小技巧：在实现这些数据结构时，可以添加一个打印内部状态的辅助函数，这样能直观看到每次操作后数据结构的变化，便于定位问题。