1. 项目概述栈与队列经典算法实战今天要分享的是数据结构中栈与队列的四个经典算法问题这也是很多技术面试中的高频考点。作为有十年全栈开发经验的工程师我经常在面试中考察候选人对这些基础数据结构的理解程度。看似简单的栈和队列在实际应用中却有着极其重要的地位——从浏览器前进后退功能到消息队列系统再到编译器语法检查它们的影子无处不在。本次要解决的四个问题分别是232题用栈实现队列225题用队列实现栈20题有效的括号1047题删除字符串中的所有相邻重复项这四个问题看似独立实则层层递进。前两题考察我们对数据结构本质的理解后两题则是栈结构的典型应用场景。在解决这些问题的过程中我们会深入探讨栈的LIFO后进先出特性队列的FIFO先进先出特性如何通过组合基本数据结构实现更复杂的行为栈在匹配类问题中的妙用2. 核心数据结构解析2.1 栈与队列的本质区别栈和队列是两种最基础的线性数据结构它们的核心区别在于操作顺序特性栈(Stack)队列(Queue)操作原则LIFO后进先出FIFO先进先出插入操作push压栈enqueue入队删除操作pop弹栈dequeue出队查看操作peek查看栈顶front查看队首典型应用函数调用栈、括号匹配消息队列、打印队列关键理解栈就像一摞盘子最后放上去的盘子最先被拿走队列则像排队买票先来的人先得到服务。2.2 实现方式对比在具体实现上两者都可以用数组或链表来实现# 栈的数组实现示例 class Stack: def __init__(self): self.items [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[-1] if not self.is_empty() else None def is_empty(self): return len(self.items) 0 # 队列的链表实现示例 class Node: def __init__(self, value): self.value value self.next None class Queue: def __init__(self): self.front None self.rear None def enqueue(self, item): new_node Node(item) if self.rear is None: self.front self.rear new_node return self.rear.next new_node self.rear new_node def dequeue(self): if self.front is None: return None temp self.front self.front temp.next if self.front is None: self.rear None return temp.value3. 用栈实现队列232题3.1 问题分析与解法思路题目要求仅使用栈的标准操作push、pop、peek、empty来实现队列的所有操作push、pop、peek、empty。关键难点在于如何用LIFO的栈实现FIFO的队列行为。我的解决思路是使用两个栈输入栈stack_in负责接收push操作输出栈stack_out负责提供pop和peek操作当需要pop或peek时如果输出栈为空则将输入栈的所有元素依次弹出并压入输出栈这样输出栈的栈顶就是最早进入的元素class MyQueue: def __init__(self): self.stack_in [] self.stack_out [] def push(self, x: int) - None: self.stack_in.append(x) def pop(self) - int: if self.empty(): return None if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) - int: if self.empty(): return None if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] def empty(self) - bool: return not self.stack_in and not self.stack_out3.2 时间复杂度分析push操作O(1) - 直接压入输入栈pop/peek操作摊还分析下也是O(1)最坏情况下需要将n个元素从一个栈移动到另一个栈O(n)但每个元素最多被移动两次进一次出一次所以平均下来是O(1)实战技巧在面试中解释摊还分析的概念能展现你的算法功底。可以类比为虽然偶尔需要大扫除但日常维护成本很低。4. 用队列实现栈225题4.1 解法一双队列法与前一题相反这里需要用FIFO的队列实现LIFO的栈行为。我的第一种解法使用两个队列主队列queue_main存储栈中元素辅助队列queue_helper在pop时临时存储元素每次pop时将主队列中除最后一个元素外的所有元素转移到辅助队列弹出并返回最后一个元素交换两个队列的角色from collections import deque class MyStack: def __init__(self): self.queue_main deque() self.queue_helper deque() def push(self, x: int) - None: self.queue_main.append(x) def pop(self) - int: if self.empty(): return None while len(self.queue_main) 1: self.queue_helper.append(self.queue_main.popleft()) item self.queue_main.popleft() self.queue_main, self.queue_helper self.queue_helper, self.queue_main return item def top(self) - int: if self.empty(): return None return self.queue_main[-1] def empty(self) - bool: return len(self.queue_main) 04.2 解法二单队列优化更巧妙的解法是仅使用一个队列。每次push新元素后立即将队列中已有的元素重新排到新元素后面class MyStack: def __init__(self): self.queue deque() def push(self, x: int) - None: n len(self.queue) self.queue.append(x) for _ in range(n): 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 len(self.queue) 0这种方法push操作是O(n)pop操作是O(1)适合读多写少的场景。5. 有效的括号20题5.1 问题分析与栈的应用这是栈的经典应用场景。给定一个只包含(){}[]的字符串判断括号是否有效匹配。关键观察遇到左括号就压栈遇到右括号就检查是否与栈顶的左括号匹配最后栈应该为空def isValid(s: str) - bool: stack [] mapping {): (, }: {, ]: [} for char in s: if char in mapping.values(): # 左括号 stack.append(char) elif char in mapping.keys(): # 右括号 if not stack or stack[-1] ! mapping[char]: return False stack.pop() else: # 非法字符 return False return not stack5.2 边界条件与优化需要注意的特殊情况空字符串是有效的只有左括号或只有右括号是无效的括号类型交叉的情况如([)]是无效的调试技巧在面试中建议先写出几个测试用例()[]{} → True(] → False([)] → False{[]} → True6. 删除字符串中的所有相邻重复项1047题6.1 栈解法这个问题可以看作是括号匹配的变种。我们可以用栈来高效地删除相邻重复项遍历字符串中的每个字符如果栈不为空且栈顶元素等于当前字符弹出栈顶否则压入当前字符最后栈中剩下的就是结果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)6.2 时间复杂度分析时间复杂度O(n)每个字符最多被处理两次压栈和弹栈各一次空间复杂度O(n)最坏情况下需要存储整个字符串这个解法比暴力解法反复扫描字符串的O(n²)效率要高得多。7. 常见问题与调试技巧7.1 栈溢出问题在递归实现栈操作时可能会遇到栈溢出。例如# 错误的递归实现 def pop(self): if len(self.items) 1: return self.items.pop() item self.items.pop() last self.pop() self.items.append(item) return last这种实现会在处理大量数据时导致递归深度过大。应该改用迭代方式。7.2 边界条件处理在实现这些数据结构时特别要注意边界条件空栈/队列时的pop操作初始化状态最后一个元素的处理建议为每个操作都编写单元测试覆盖这些边界情况。7.3 性能优化技巧对于频繁的操作如peek可以缓存结果在栈实现队列时只有当输出栈为空时才进行转移使用collections.deque代替list实现队列因为deque的popleft()是O(1)操作8. 实际应用场景这些基础数据结构在真实项目中有着广泛应用用栈实现队列某些语言如Haskell的纯函数式队列实现限制性环境下的队列需求用队列实现栈线程池的任务调度广度优先搜索的变种实现有效的括号编译器语法检查JSON/XML解析器代码编辑器的大括号匹配删除相邻重复项文本编辑器中的连续空格合并日志文件的重复条目清理数据清洗预处理在大型项目中我经常需要根据具体场景选择合适的数据结构。比如在实现一个消息系统时就混合使用了栈和队列普通消息使用队列保证顺序高优先级消息使用栈实现插队使用括号匹配算法验证消息格式9. 扩展思考9.1 如何实现支持O(1)获取最小值的栈这是栈的一个经典变种问题Leetcode 155题。可以在栈中同时存储元素和当前最小值class MinStack: def __init__(self): self.stack [] # 存储值当前最小值元组 def push(self, x: int) - None: if not self.stack: self.stack.append((x, x)) else: self.stack.append((x, min(x, self.stack[-1][1]))) def pop(self) - None: self.stack.pop() def top(self) - int: return self.stack[-1][0] def getMin(self) - int: return self.stack[-1][1]9.2 如何用栈实现递归函数的调用函数调用栈是栈的另一个重要应用。每次函数调用时将返回地址、参数、局部变量压栈函数返回时弹出栈帧这样就能实现函数的嵌套调用理解这一点对调试递归函数和异常堆栈非常有帮助。9.3 单调栈与单调队列这是栈和队列的高级用法用于解决一些特殊问题单调栈用于解决下一个更大元素类问题单调队列用于滑动窗口最大值问题这些扩展内容值得单独深入探讨建议在掌握基础后继续学习。