栈与队列：数据结构基础与LeetCode实战

1. 栈与队列基础数据结构中的孪生兄弟栈和队列是算法面试中最常考察的两种基础数据结构它们看似简单却蕴含着精妙的设计思想。栈遵循LIFO后进先出原则就像餐厅里叠放的餐盘最后放上去的总是最先被取用而队列遵循FIFO先进先出原则如同排队购票的队伍先来的人先获得服务。在实际工程中栈的应用场景包括函数调用栈记录函数调用层次浏览器前进后退功能语法解析如括号匹配深度优先搜索DFS的非递归实现队列的典型应用则涵盖消息队列系统解耦广度优先搜索BFS实现打印机任务调度线程池任务管理理解它们的核心区别是解题关键栈只允许在顶部操作push/pop而队列则在尾部添加enqueue、头部移除dequeue。当题目要求反向操作时往往需要考虑这两种数据结构的转换。2. 用栈实现队列的魔法戏法LeetCode 232题要求用栈实现队列这就像用筷子喝汤——需要些技巧。核心思路是使用两个栈stackIn和stackOut来模拟队列的先进先出特性class MyQueue: def __init__(self): self.stackIn [] self.stackOut [] def push(self, x: int) - None: self.stackIn.append(x) def pop(self) - int: if not self.stackOut: while self.stackIn: self.stackOut.append(self.stackIn.pop()) return self.stackOut.pop() def peek(self) - int: if not self.stackOut: while self.stackIn: self.stackOut.append(self.stackIn.pop()) return self.stackOut[-1] def empty(self) - bool: return not self.stackIn and not self.stackOut时间复杂度分析入队操作O(1)出队操作均摊O(1)虽然最坏情况下是O(n)但每个元素最多被压入和弹出各一次关键技巧只有当stackOut为空时才一次性将stackIn的所有元素转移过来。这种延迟转移策略保证了均摊时间复杂度。3. 用队列实现栈的逆向思维LeetCode 225题则反其道而行要求用队列实现栈。这里给出单队列和双队列两种实现方案单队列实现方案class MyStack: def __init__(self): self.q collections.deque() def push(self, x: int) - None: self.q.append(x) # 将前n-1个元素重新入队 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.q双队列实现方案class MyStack: def __init__(self): self.q1 collections.deque() self.q2 collections.deque() def push(self, x: int) - None: self.q2.append(x) while self.q1: self.q2.append(self.q1.popleft()) self.q1, self.q2 self.q2, self.q1 def pop(self) - int: return self.q1.popleft() def top(self) - int: return self.q1[0] def empty(self) - bool: return not self.q1性能对比单队列方案push操作是O(n)pop是O(1)双队列方案push操作也是O(n)但实际运行可能更快取决于语言实现空间复杂度都是O(n)4. 括号匹配的经典栈应用LeetCode 20题是检验括号有效性的经典问题栈的LIFO特性完美匹配括号的嵌套关系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边界情况处理字符串长度为奇数时直接返回False遇到右括号时栈为空的情况最后栈不为空的情况如((())扩展变种带优先级的括号匹配如HTML标签包含其他字符的字符串需过滤多类型括号混合如同时包含小括号和方括号5. 相邻重复项删除的栈解法LeetCode 1047题要求删除字符串中所有相邻重复项这实际上是括号匹配问题的变种基础栈解法def removeDuplicates(s: str) - str: stack [] for char in s: if stack and stack[-1] char: stack.pop() else: stack.append(char) return .join(stack)时间复杂度优化可以使用双指针模拟栈操作将空间复杂度降为O(1)def removeDuplicates(s: str) - str: res list(s) slow fast 0 while fast len(res): res[slow] res[fast] if slow 0 and res[slow] res[slow-1]: slow - 1 else: slow 1 fast 1 return .join(res[:slow])实际应用场景编译器语法检查文本编辑器连续退格功能路径简化如Unix中的..处理6. 单调栈的进阶应用单调栈是处理下一个更大元素类问题的利器其核心是维护一个栈内元素单调递增或递减的顺序。以LeetCode 496题为例def nextGreaterElement(nums1: List[int], nums2: List[int]) - List[int]: stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) return [mapping.get(num, -1) for num in nums1]单调栈的典型应用场景柱状图中最大矩形LeetCode 84接雨水问题LeetCode 42股票跨度问题LeetCode 901算法模板stack [] for 元素 in 列表: while stack and 当前元素 stack[-1]: # 处理栈顶元素与当前元素的关系 stack.pop() stack.append(元素)7. 实战中的常见陷阱与优化在实现这些数据结构时容易踩中以下陷阱栈实现队列时的顺序错误错误在每次操作时都转移元素导致时间复杂度退化正确只在必要时stackOut为空时才批量转移括号匹配时的类型混淆错误未区分三种括号类型简单统计数量正确使用哈希表建立对应关系严格匹配类型相邻项删除的边界条件错误未处理空字符串或全重复的情况正确预先检查长度使用哨兵节点简化逻辑性能优化技巧使用collections.deque替代list实现栈/队列Python中pop(0)是O(n)操作预先分配数组大小如C中的reserve在单调栈问题中存储索引而非值便于计算距离8. 从算法题到工程实践这些基础算法在实际工程中有广泛的应用用栈实现队列的变种消息队列的延迟消费模式操作系统的中断处理机制括号匹配算法的延伸JSON/XML解析器代码编辑器语法高亮配置文件校验相邻项删除的应用数据清洗去除连续重复记录日志压缩合并相同事件版本控制系统中的连续提交合并理解这些基础数据结构的本质能帮助我们在面对复杂系统设计时选择合适的数据组织方式。比如Redis的列表类型既可以用作栈也可用作队列而Kafka的分区设计本质上也是队列思想的延伸。