1. 栈与队列基础概念回顾
在正式解题之前，我们需要先明确几个核心概念。栈（Stack）是一种后进先出（LIFO）的数据结构，只允许在一端（称为栈顶）进行插入和删除操作。想象一下餐厅里叠放的餐盘，你总是取走最上面的那个，新洗好的盘子也会放在最上面。
队列（Queue）则是先进先出（FIFO）的结构，就像排队买票的队伍，先来的人先得到服务。它有两个基本操作：入队（enqueue）在队尾添加元素，出队（dequeue）从队首移除元素。
在力扣题目中，这两种数据结构经常以各种变形出现：
- 单调栈：栈内元素保持单调递增或递减
- 双端队列：两端都可以进行插入和删除操作
- 优先队列：元素带有优先级，出队顺序由优先级决定
实际面试中，面试官可能会要求你手写这些数据结构的实现。建议至少掌握数组和链表两种实现方式。
2. 栈的经典题目解析
2.1 有效的括号（LeetCode 20）
这是栈结构最经典的入门题。给定一个只包含 '(', ')', '{', '}', '[' 和 ']' 的字符串，判断字符串是否有效。
解题思路：
- 初始化一个空栈
- 遍历字符串：
- 遇到左括号就压栈
- 遇到右括号就检查栈顶是否匹配
- 匹配则弹出栈顶
- 不匹配直接返回false
- 最后检查栈是否为空
def isValid(s: str) -> bool: stack = [] mapping = {')': '(', '}': '{', ']': '['} for char in s: if char in mapping: top = stack.pop() if stack else '#' if mapping[char] != top: return False else: stack.append(char) return not stack常见错误：忘记处理栈为空时pop的情况，或者最后没有检查栈是否为空。
2.2 每日温度（LeetCode 739）
给定一个温度列表，要求返回一个列表，表示需要等待多少天才能等到更暖和的温度。这是单调栈的典型应用。
解法分析：
- 维护一个单调递减栈，存储的是日期索引
- 当当前温度大于栈顶温度时，计算日期差并记录结果
def dailyTemperatures(T: List[int]) -> List[int]: stack = [] res = [0] * len(T) for i in range(len(T)): while stack and T[i] > T[stack[-1]]: prev = stack.pop() res[prev] = i - prev stack.append(i) return res时间复杂度分析：虽然看起来有嵌套循环，但每个元素最多入栈出栈一次，所以是O(n)时间复杂度。
3. 队列的经典题目解析
3.1 用栈实现队列（LeetCode 232）
这道题要求使用栈的FILO特性来实现队列的FIFO特性。关键在于使用两个栈：一个输入栈，一个输出栈。
实现要点：
- 入队时直接压入输入栈
- 出队时：
- 如果输出栈为空，将输入栈所有元素弹出并压入输出栈
- 然后从输出栈弹出元素
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._transfer() return self.out_stack.pop() def peek(self) -> int: self._transfer() return self.out_stack[-1] def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())面试陷阱：面试官可能会追问各个操作的时间复杂度。最好情况O(1)，最坏情况O(n)，但均摊分析仍然是O(1)。
3.2 滑动窗口最大值（LeetCode 239）
这是单调队列的经典应用。给定一个数组和滑动窗口大小k，找出每个窗口中的最大值。
高效解法：
- 使用双端队列存储可能成为窗口最大值的元素索引
- 队列中的元素按从大到小排列
- 当新元素大于队尾元素时，弹出队尾元素（维护单调性）
- 检查队首元素是否还在窗口内
def maxSlidingWindow(nums: List[int], k: int) -> List[int]: from collections import deque q = deque() res = [] for i in range(len(nums)): while q and nums[i] > nums[q[-1]]: q.pop() q.append(i) if q[0] == i - k: q.popleft() if i >= k - 1: res.append(nums[q[0]]) return res时间复杂度：每个元素最多入队出队一次，O(n)时间复杂度。
4. 栈与队列的混合应用
4.1 用队列实现栈（LeetCode 225）
与232题相反，这次要用队列的FIFO特性实现栈的FILO特性。有两种主要实现方式：
方法一：两个队列，push时O(1)，pop时O(n)
- 入栈时直接加入非空队列
- 出栈时将非空队列的前n-1个元素转移到另一个队列，然后弹出最后一个元素
方法二：一个队列，push时O(n)，pop时O(1)
- 入栈时先将新元素入队，然后把前面的元素依次出队再入队
- 出栈时直接出队
# 方法二实现 class MyStack: def __init__(self): self.q = collections.deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft()实际应用中，根据使用场景选择实现方式。如果push操作频繁，选择方法一；如果pop操作频繁，选择方法二。
4.2 逆波兰表达式求值（LeetCode 150）
这是栈在表达式求值中的典型应用。逆波兰表达式（后缀表达式）的特点是操作符在操作数之后。
解题步骤：
- 初始化一个空栈
- 遍历tokens：
- 遇到数字就压栈
- 遇到操作符就弹出栈顶两个元素进行计算，将结果压栈
- 最后栈中剩下的就是结果
def evalRPN(tokens: List[str]) -> int: stack = [] for token in tokens: if token not in '+-*/': stack.append(int(token)) else: 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)) # 注意除法向零取整 return stack[0]特别注意：Python的除法与题目要求可能不同，需要使用int(a/b)而不是a//b，因为//是向下取整。
5. 高级应用与变形题目
5.1 最小栈（LeetCode 155）
设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。
解法思路：
- 使用辅助栈同步记录当前最小值
- 主栈压入元素时，辅助栈压入当前最小值
- 主栈弹出时，辅助栈同步弹出
class MinStack: def __init__(self): self.stack = [] self.min_stack = [float('inf')] def push(self, val: int) -> None: self.stack.append(val) self.min_stack.append(min(val, self.min_stack[-1])) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]空间优化：辅助栈可以不存储所有状态，只在遇到更小值时入栈，等于当前最小值时也入栈。
5.2 接雨水（LeetCode 42）
这道题可以用单调栈、双指针或动态规划多种方法解决。这里展示单调栈解法：
def trap(height: List[int]) -> int: stack = [] res = 0 for i in range(len(height)): while stack and height[i] > height[stack[-1]]: bottom = stack.pop() if not stack: break left = stack[-1] width = i - left - 1 bounded_height = min(height[left], height[i]) - height[bottom] res += width * bounded_height stack.append(i) return res理解要点：
- 栈中存储的是递减的柱子的索引
- 当遇到更高的柱子时，计算前面能接的雨水量
- 雨水量 = 宽度 × (左右边界较小值 - 底部高度)
6. 面试实战技巧与常见错误
6.1 面试中的高频考点
根据力扣和各大公司的面试统计，栈与队列相关题目常考以下类型：
- 基础实现题（用栈实现队列等）
- 括号匹配类问题
- 单调栈应用（接雨水、柱状图最大矩形）
- 滑动窗口问题
- 表达式求值
6.2 常见错误与调试技巧
边界条件处理不足：
- 栈/队列为空时的操作
- 输入为空或只有一个元素的情况
- 数值溢出（特别是Python不需要考虑，但其他语言要注意）
复杂度分析错误：
- 误认为嵌套循环就是O(n²)
- 忽略均摊分析（如用栈实现队列的操作）
调试建议：
- 对于复杂问题，先手动模拟小例子
- 打印栈/队列的状态变化
- 使用assert检查不变式
6.3 性能优化思路
空间换时间：
- 最小栈的辅助栈
- 预处理某些信息（如单调栈问题中预先计算左右边界）
算法选择：
- 滑动窗口问题优先考虑单调队列
- 最近相关性问题（如括号匹配）优先考虑栈
语言特性利用：
- Python中collections.deque比list更适合队列实现
- 某些情况下可以用位运算替代栈操作（如括号匹配可以用计数器）
我在实际面试和刷题中发现，很多同学对栈和队列的理解停留在表面。建议不仅要会做题，还要理解每个操作背后的计算机科学原理。比如函数调用栈、消息队列在实际系统中的应用，这些深度理解会让你在面试中脱颖而出。
