1. 栈与队列基础概念回顾在正式解题之前我们需要先明确几个基本概念。栈Stack是一种后进先出LIFO的数据结构就像我们平时叠放的盘子最后放上去的盘子总是最先被取用。队列Queue则是先进先出FIFO的结构类似于排队买票先来的人先得到服务。栈的两个基本操作push将元素压入栈顶pop从栈顶弹出元素队列的三个基本操作enqueue将元素加入队尾dequeue从队首移除元素peek查看队首元素但不移除2. 经典栈题目解析2.1 有效的括号LeetCode 20这是栈结构最经典的入门题目。题目要求判断一个只包含()[]{}的字符串是否有效即括号是否匹配且嵌套正确。解题思路初始化一个空栈遍历字符串中的每个字符遇到左括号就压入栈遇到右括号就检查栈顶元素是否匹配最后检查栈是否为空def isValid(s: str) - bool: stack [] mapping {):(, ]:[, }:{} for char in s: if char in mapping: top_element stack.pop() if stack else # if mapping[char] ! top_element: return False else: stack.append(char) return not stack2.2 最小栈LeetCode 155设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。关键点在于维护两个栈主栈存储所有元素辅助栈只存储当前最小值class MinStack: def __init__(self): self.stack [] self.min_stack [] def push(self, val: int) - None: self.stack.append(val) if not self.min_stack or val self.min_stack[-1]: self.min_stack.append(val) def pop(self) - None: if self.stack.pop() self.min_stack[-1]: self.min_stack.pop() def top(self) - int: return self.stack[-1] def getMin(self) - int: return self.min_stack[-1]3. 队列经典题目解析3.1 用栈实现队列LeetCode 232这道题要求使用栈的基本操作来实现队列的所有操作push、pop、peek、empty。解题思路 使用两个栈一个输入栈一个输出栈push操作直接压入输入栈pop/peek操作时如果输出栈为空就把输入栈的所有元素弹出并压入输出栈class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x: int) - None: self.in_stack.append(x) def pop(self) - int: self.peek() return self.out_stack.pop() def peek(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self) - bool: return not self.in_stack and not self.out_stack3.2 滑动窗口最大值LeetCode 239给定一个数组和滑动窗口的大小找出所有滑动窗口中的最大值。这道题需要使用单调队列的技巧维护一个双端队列存储可能成为窗口最大值的元素索引队列中的元素按照从大到小排列每次移动窗口时移除不在窗口范围内的元素新元素从队尾开始比较移除所有比它小的元素def maxSlidingWindow(nums: List[int], k: int) - List[int]: from collections import deque q deque() result [] for i, num in enumerate(nums): while q and nums[q[-1]] num: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: result.append(nums[q[0]]) return result4. 栈与队列的综合应用4.1 逆波兰表达式求值LeetCode 150逆波兰表达式后缀表达式的计算是栈的典型应用。表达式中的运算符总是放在操作数之后。解题步骤初始化一个空栈遍历表达式中的每个token遇到数字就压入栈遇到运算符就弹出栈顶两个元素进行计算将结果压回栈最后栈中剩下的就是计算结果def evalRPN(tokens: List[str]) - int: stack [] for token in tokens: if token in -*/: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) else: stack.append(int(token)) return stack[0]4.2 用队列实现栈LeetCode 225这道题与用栈实现队列相反要求使用队列的基本操作来实现栈的所有操作push、pop、top、empty。解题思路 使用两个队列主队列和辅助队列push操作直接加入主队列pop操作时将主队列中除最后一个元素外的所有元素转移到辅助队列然后弹出最后一个元素最后交换两个队列的角色from collections import deque class MyStack: def __init__(self): self.queue deque() def push(self, x: int) - None: self.queue.append(x) for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) def pop(self) - int: return self.queue.popleft() def top(self) - int: return self.queue[0] def empty(self) - bool: return not self.queue5. 单调栈与单调队列进阶5.1 每日温度LeetCode 739给定一个温度列表要求返回一个列表表示需要等待多少天才能等到更暖和的温度。这是单调栈的典型应用维护一个存储索引的单调递减栈遍历温度列表当前温度比栈顶温度高时计算天数差并记录结果将当前索引入栈def dailyTemperatures(T: List[int]) - List[int]: stack [] result [0] * len(T) for i, temp in enumerate(T): while stack and T[stack[-1]] temp: prev stack.pop() result[prev] i - prev stack.append(i) return result5.2 接雨水LeetCode 42给定n个非负整数表示高度图计算下雨后能接多少雨水。可以使用单调栈的解法维护一个存储索引的单调递减栈遍历高度数组当当前高度大于栈顶高度时说明可能形成凹槽可以接水计算接水量并累加def trap(height: List[int]) - int: stack [] water 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] distance i - left - 1 bounded_height min(h, height[left]) - height[bottom] water distance * bounded_height stack.append(i) return water6. 常见错误与优化技巧6.1 栈与队列使用中的常见错误边界条件处理不足栈/队列为空时的pop操作初始化和终止条件的判断时间复杂度分析错误看似O(n^2)的算法可能实际上是O(n)单调栈/队列的均摊时间复杂度分析空间复杂度优化不足不必要的辅助数据结构可以原地修改的情况6.2 性能优化技巧使用双端队列代替列表Python中collections.deque的popleft()是O(1)操作列表的pop(0)是O(n)操作提前分配结果数组空间避免频繁的append操作对于已知大小的结果直接初始化固定大小列表利用语言特性Python中使用列表推导式适当使用生成器表达式减少内存占用7. 实际工程中的应用场景7.1 栈的实际应用函数调用栈程序执行时的函数调用关系递归函数的实现原理浏览器历史记录前进后退功能实现撤销操作实现表达式求值与语法分析编译器的词法分析计算器实现7.2 队列的实际应用消息队列系统任务调度与分发生产者-消费者模型广度优先搜索图的遍历算法最短路径问题请求缓冲高并发系统的请求排队流量控制8. 进阶练习题目推荐为了帮助大家巩固所学知识这里推荐一些进阶练习题栈相关LeetCode 84 - 柱状图中最大的矩形LeetCode 316 - 去除重复字母LeetCode 402 - 移掉K位数字队列相关LeetCode 621 - 任务调度器LeetCode 862 - 和至少为K的最短子数组LeetCode 933 - 最近的请求次数综合应用LeetCode 341 - 扁平化嵌套列表迭代器LeetCode 636 - 函数的独占时间LeetCode 895 - 最大频率栈9. 解题思路总结通过以上题目的练习我们可以总结出一些通用的解题模式栈的典型应用场景匹配问题括号匹配、标签匹配等单调栈寻找下一个更大/更小元素递归转迭代使用栈模拟递归过程队列的典型应用场景BFS相关问题滑动窗口问题任务调度问题混合使用栈和队列用栈实现队列和用队列实现栈多级缓存结构设计复杂状态管理在实际面试中遇到新题目时可以尝试思考是否需要维护某种顺序是否需要快速访问最近/最早的元素是否需要处理嵌套结构这些问题往往能帮助我们快速判断是否应该使用栈或队列结构。