栈与队列互转及经典应用解析-平芜编程栈

1. 栈与队列的经典互转：从原理到实现

1.1 用栈实现队列（LeetCode 232）

栈和队列是数据结构中最基础也最重要的两种线性结构。栈遵循后进先出(LIFO)原则，而队列遵循先进先出(FIFO)原则。这道题目要求我们仅用栈的操作来模拟队列的行为，这看似矛盾，实则巧妙。

双栈法的核心思路：

使用两个栈：输入栈(inStack)和输出栈(outStack)
入队操作：直接压入输入栈
出队操作：当输出栈为空时，将输入栈所有元素弹出并压入输出栈，再从输出栈弹出

class MyQueue { public: stack<int> inStack; stack<int> outStack; void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } int res = outStack.top(); outStack.pop(); return res; } int peek() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };

时间复杂度分析：

push操作：O(1)
pop/peek操作：均摊O(1)（虽然最坏情况下是O(n)，但每个元素最多被压入和弹出各两次）

实际工程中这种实现方式并不高效，但在面试中考察的是对数据结构的理解。我在实际编码测试中发现，当队列操作频繁交替时，性能会明显下降。

1.2 用队列实现栈（LeetCode 225）

与上一题相反，这次要用队列实现栈。队列是先进先出的，而栈需要后进先出，这同样是个有趣的挑战。

单队列法的实现技巧：

每次push新元素后，将队列中之前的元素依次出队再入队
这样新元素总是位于队列前端，实现了LIFO特性

class MyStack { public: queue<int> q; void push(int x) { int n = q.size(); q.push(x); for (int i = 0; i < n; 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(); } };

时间复杂度分析：

push操作：O(n)
pop/top操作：O(1)

我在实际项目中使用这种结构时发现，当栈深度较大时，push操作会成为性能瓶颈。因此这种实现更适合栈操作不频繁或栈深度不大的场景。

2. 栈的经典应用：括号匹配与相邻去重

2.1 有效的括号（LeetCode 20）

括号匹配是栈结构的经典应用场景。我们需要检查字符串中的括号是否成对且顺序正确。

算法思路：

遍历字符串，遇到左括号就压栈
遇到右括号时检查栈顶是否匹配
最后检查栈是否为空

class Solution { public: 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(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; } st.pop(); } } return st.empty(); } };

边界条件处理：

字符串为空：返回true
只有左括号：最后栈不为空，返回false
只有右括号：栈为空时遇到右括号，返回false

在真实代码审查中，我经常看到开发者忽略栈为空的检查，这会导致段错误。这是一个典型的防御性编程案例。

2.2 删除相邻重复项（LeetCode 1047）

这个问题要求我们删除字符串中所有相邻的重复字符，直到无法继续删除为止。

栈解法优势：

自然地处理嵌套的重复情况
时间复杂度O(n)，空间复杂度O(n)

class Solution { public: 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; } };

优化技巧：

直接使用字符串作为栈，避免最后反转操作
比较时使用back()而不是top()，更符合字符串操作习惯

在实际文本处理中，这种算法可以用来压缩重复字符。我曾在日志处理系统中使用类似方法减少存储空间。

3. 算法实战中的经验与技巧

3.1 数据结构选择的艺术

在解决这些问题时，我们深刻体会到：

栈适合处理具有嵌套性质的问题（如括号匹配）
队列适合处理需要保持顺序的问题
双栈法可以在特定场景下转换数据结构特性

性能考量：

栈的数组实现通常比链表实现更高效
递归本质上就是使用调用栈，有时可以替代显式栈
在内存受限环境中，需要考虑栈的最大深度

3.2 常见错误与调试技巧

边界条件处理不足：
- 忘记检查容器是否为空就调用top/pop
- 解决方案：养成先判空再操作的习惯
时间复杂度误判：
- 认为双栈法的pop总是O(1)
- 实际是均摊O(1)，最坏O(n)
语言特性陷阱：
- C++中stack的pop不返回值
- 必须先top再pop

3.3 面试中的扩展问题

面试官可能会追问：

如何实现线程安全的栈/队列？
如果数据量很大，如何优化内存使用？
如何设计支持O(1)获取最小值的栈？

对于最小值栈问题，可以这样实现：

class MinStack { stack<int> data; stack<int> min_stack; public: void push(int x) { data.push(x); if (min_stack.empty() || x <= min_stack.top()) { min_stack.push(x); } } void pop() { if (data.top() == min_stack.top()) { min_stack.pop(); } data.pop(); } int top() { return data.top(); } int getMin() { return min_stack.top(); } };