1. 项目概述作为一名参加过多次算法训练营的老学员我清楚地记得第一次面对栈和队列相关题目时的困惑。这次参加代码随想录算法训练营的二周目让我有机会重新梳理这些基础但至关重要的数据结构知识。本篇将详细记录第十天的学习内容包括理论基础和四道经典题目232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047.删除字符串中的所有相邻重复项的解题思路和实现细节。栈和队列是算法面试中的常客看似简单却暗藏玄机。很多同学在面试中遇到用栈实现队列这类题目时虽然知道要用两个栈但总是写不出bug-free的代码。通过这次系统性的训练我总结出了一套可复用的解题模板和调试技巧。2. 理论基础精讲2.1 栈与队列的核心特性栈Stack是一种后进先出LIFO的数据结构只允许在一端称为栈顶进行插入和删除操作。它的核心操作包括push将元素压入栈顶pop弹出栈顶元素peek查看栈顶元素但不弹出isEmpty判断栈是否为空队列Queue则是先进先出FIFO的数据结构允许在一端队尾插入在另一端队头删除。核心操作包括offer/enqueue元素入队poll/dequeue元素出队peek查看队头元素isEmpty判断队列是否为空关键理解栈和队列的根本区别在于元素的出入顺序。栈像是叠盘子最后放上去的盘子最先被拿走队列像是排队先来的人先接受服务。2.2 实现方式对比在Java中Stack是一个类而Queue是一个接口。常见的实现方式数据结构Java实现类时间复杂度栈Stackpush/pop/peek: O(1)队列LinkedList/ArrayDequeoffer/poll/peek: O(1)C中则使用stack和queue模板类#include stack #include queue std::stackint s; std::queueint q;Python中使用list实现栈collections.deque实现队列stack [] queue collections.deque()3. 题目精解与实现3.1 232. 用栈实现队列3.1.1 解题思路这道题要求使用栈的FILO特性来实现队列的FIFO特性。核心思路是使用两个栈输入栈(inStack)负责接收push操作的新元素输出栈(outStack)负责pop和peek操作当需要pop或peek时如果outStack为空将inStack的所有元素依次弹出并压入outStack此时outStack的栈顶元素就是队列的队头元素这样操作后元素的顺序就被反转了两次inStack反转一次outStack再反转一次相当于保持了原始顺序。3.1.2 代码实现class MyQueue { private StackInteger inStack; private StackInteger outStack; public MyQueue() { inStack new Stack(); outStack new Stack(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() outStack.isEmpty(); } }3.1.3 复杂度分析时间复杂度pushO(1)pop/peek均摊O(1)每个元素最多被压入和弹出各两次空间复杂度O(n)需要两个栈存储所有元素注意事项在面试中写这道题时一定要先解释清楚为什么均摊时间复杂度是O(1)。可以类比银行排队场景虽然偶尔需要把整个队伍转移到另一个窗口O(n)操作但每个客户平均只被转移一次。3.2 225. 用队列实现栈3.2.1 解题思路这道题与232题相反需要用队列的FIFO特性实现栈的FILO特性。有两种主要方法双队列法push为O(1)pop为O(n)主队列存储元素辅助队列用于倒腾push时直接入队主队列pop时将主队列的前n-1个元素转移到辅助队列剩下最后一个元素就是栈顶单队列法push为O(n)pop为O(1)每次push新元素后将队列中已有的元素依次出队再入队使新元素位于队头pop时直接出队即可3.2.2 代码实现双队列法from collections import deque class MyStack: def __init__(self): self.main_queue deque() self.helper_queue deque() def push(self, x: int) - None: self.main_queue.append(x) def pop(self) - int: while len(self.main_queue) 1: self.helper_queue.append(self.main_queue.popleft()) res self.main_queue.popleft() self.main_queue, self.helper_queue self.helper_queue, self.main_queue return res def top(self) - int: return self.main_queue[-1] if self.main_queue else None def empty(self) - bool: return not self.main_queue3.2.3 复杂度分析时间复杂度pushO(1)pop/topO(n)空间复杂度O(n)需要两个队列存储元素实战技巧在Python中使用deque的[-1]可以直接访问队尾元素这使得top操作可以在O(1)时间内完成。这是Python特有的优化在其他语言中可能需要完整遍历队列。3.3 20. 有效的括号3.3.1 解题思路这是栈的经典应用场景。算法步骤初始化一个空栈遍历字符串中的每个字符如果是左括号(、[、{将其压入栈如果是右括号检查栈顶元素是否匹配匹配则弹出栈顶不匹配则直接返回false最后检查栈是否为空空栈说明所有括号都匹配非空栈说明有未匹配的左括号3.3.2 代码实现class Solution { public: bool isValid(string s) { stackchar st; unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; 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(); } };3.3.3 复杂度分析时间复杂度O(n)只需遍历一次字符串空间复杂度O(n)最坏情况下需要存储所有左括号常见错误只考虑括号数量匹配而忽略顺序。例如([)]虽然每种括号数量匹配但顺序不正确应该返回false。使用栈结构可以完美解决顺序问题。3.4 1047. 删除字符串中的所有相邻重复项3.4.1 解题思路这道题可以看作是有效的括号的变种同样使用栈来解决初始化空栈遍历字符串如果栈不为空且当前字符等于栈顶字符弹出栈顶表示消除这对重复项否则将当前字符压入栈最后将栈中字符拼接成字符串返回3.4.2 代码实现class Solution { public String removeDuplicates(String s) { StringBuilder stack new StringBuilder(); for (char c : s.toCharArray()) { int len stack.length(); if (len 0 stack.charAt(len - 1) c) { stack.deleteCharAt(len - 1); } else { stack.append(c); } } return stack.toString(); } }3.4.3 复杂度分析时间复杂度O(n)每个字符最多被处理两次压入和弹出空间复杂度O(n)最坏情况下需要存储整个字符串优化技巧使用StringBuilder模拟栈操作避免了频繁的栈对象创建和销毁在Java中性能更好。类似的在Python中可以直接使用listC可以使用string作为栈。4. 常见问题与调试技巧4.1 边界条件处理在实现这些数据结构题目时最容易出错的就是边界条件的处理。以下是一些常见边界情况空输入所有操作都应该能正确处理空栈/空队列的情况连续操作如连续pop或peek时确保内部状态正确大小边界特别是用数组实现时要考虑扩容和缩容4.2 调试技巧可视化跟踪在纸上画出栈和队列的变化过程状态打印在关键操作后打印内部数据结构的状态单元测试针对每个方法编写边界测试用例4.3 面试常见问题面试官可能会追问为什么这种方法的时间复杂度是均摊O(1)如何进一步优化空间使用如果要求线程安全该如何修改实现5. 扩展思考5.1 实际应用场景栈的应用函数调用栈浏览器前进后退撤销操作(Undo)表达式求值队列的应用消息队列打印任务队列广度优先搜索(BFS)缓存实现5.2 变种数据结构双端队列(Deque)两端都可以进行插入和删除优先队列(PriorityQueue)元素按优先级出队单调栈/队列维护栈/队列中元素的单调性5.3 性能优化方向延迟转移在用栈实现队列时可以等到必须转移时才进行批量操作适当合并操作可以减少数据移动次数空间复用合理设计可以节省一个栈/队列的空间通过这次系统的训练我对栈和队列的理解更加深入了。最大的收获是认识到看似简单的数据结构通过巧妙的组合和变形可以解决各种复杂问题。建议大家在掌握这些基础题目后尝试解决一些更复杂的变种问题如155.最小栈、239.滑动窗口最大值等进一步巩固这些技术。