1. 算法训练营DAY10栈与队列基础概念解析作为一名经历过无数次算法面试的老兵我深知栈和队列这两个数据结构在算法题中的分量。今天我们就来彻底拆解这两个看似简单却暗藏玄机的基础数据结构。栈Stack就像我们生活中叠放的盘子遵循后进先出LIFO的原则。在算法题中栈最常见的应用场景包括括号匹配LeetCode 20题表达式求值LeetCode 224题浏览器前进后退功能实现函数调用栈的实现而队列Queue则像是排队买奶茶的队伍遵循先进先出FIFO的原则。它的典型应用包括二叉树的层序遍历LeetCode 102题滑动窗口问题LeetCode 239题消息队列系统设计线程池任务调度提示虽然栈和队列的概念很简单但在实际算法题中它们的组合和变种才是真正的难点。比如单调栈、双端队列、优先队列等变体往往能解决一些看似复杂的问题。2. 栈的实战应用与LeetCode经典题解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 stack关键点解析使用字典存储括号的对应关系避免多层if-else判断遇到右括号时检查栈顶元素是否匹配最后检查栈是否为空防止只有左括号的情况2.2 每日温度LeetCode 739这道题展示了单调栈的典型应用。题目要求对于每一天的温度找出需要等待多少天才能等到更暖和的温度。def dailyTemperatures(T: List[int]) - List[int]: stack [] result [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev_index stack.pop() result[prev_index] i - prev_index stack.append(i) return result单调栈的技巧在于栈中存储的是索引而非温度值维护一个温度单调递减的栈当遇到更高温度时计算天数差并更新结果注意单调栈问题的时间复杂度通常是O(n)因为每个元素最多入栈和出栈一次。这是它相比暴力解法O(n²)的优势所在。3. 队列的实战应用与LeetCode经典题解3.1 用栈实现队列LeetCode 232这道题考察对栈和队列本质区别的理解。题目要求仅使用栈的操作来实现队列的所有操作。class MyQueue: def __init__(self): self.input_stack [] self.output_stack [] def push(self, x: int) - None: self.input_stack.append(x) def pop(self) - int: self.peek() return self.output_stack.pop() def peek(self) - int: if not self.output_stack: while self.input_stack: self.output_stack.append(self.input_stack.pop()) return self.output_stack[-1] def empty(self) - bool: return not self.input_stack and not self.output_stack实现要点使用两个栈一个负责输入一个负责输出只有当输出栈为空时才将输入栈的所有元素转移到输出栈这样保证了最先进入的元素在输出栈的顶部3.2 滑动窗口最大值LeetCode 239这道题展示了双端队列Deque的强大之处。题目要求在数组的滑动窗口中找到最大值。def maxSlidingWindow(nums: List[int], k: int) - List[int]: from collections import deque q deque() result [] 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: result.append(nums[q[0]]) return result双端队列的技巧队列中存储的是索引而非值维护一个单调递减的队列移除超出窗口范围的元素队首元素始终是当前窗口的最大值4. 栈与队列的高级应用与面试技巧4.1 单调栈与单调队列的对比虽然单调栈和单调队列看起来很相似但它们解决的问题类型有所不同特性单调栈单调队列数据结构栈双端队列典型问题下一个更大元素滑动窗口最大值时间复杂度O(n)O(n)空间复杂度O(n)O(k)维护方向单向通常从栈顶双向队首和队尾4.2 面试中的常见陷阱在算法面试中栈和队列相关题目有几个常见的陷阱需要注意边界条件处理空栈/队列时的操作、初始条件的处理等时间复杂度分析看似O(n²)的解法可能通过单调性优化到O(n)空间复杂度优化有些问题可以用O(1)空间解决如括号匹配问题数据结构选择优先队列堆有时比普通队列更适合某些问题4.3 实际工程中的应用栈和队列不仅在算法题中有用在实际工程中也有广泛应用栈的应用浏览器历史记录文本编辑器的撤销操作编译器的语法分析递归函数的调用栈队列的应用消息队列系统Kafka, RabbitMQ任务调度系统网络请求的流量控制打印任务队列我在实际开发中遇到过的一个典型问题是用消息队列处理高并发请求。开始时我们使用简单的FIFO队列但后来发现某些重要请求需要优先处理于是改用优先队列堆实现来确保高优先级任务能及时得到处理。这个经验让我深刻理解了不同队列变体的适用场景。