1. 项目概述今天继续代码随想录算法训练营第十天的学习内容主要聚焦栈和队列这两种基础数据结构的经典应用。作为训练营的二周目学员我发现重新梳理这些基础算法题能带来全新的理解。本日内容包含四个核心题目用栈实现队列、用队列实现栈、有效的括号判断以及删除字符串中的相邻重复项。对于正在准备算法面试的同学来说这四个题目都是必须掌握的经典题型。它们不仅考察对数据结构特性的理解更训练我们灵活运用基础数据结构解决实际问题的能力。我在第一次刷题时也曾被这些题目困扰但通过反复练习和思考现在能够更清晰地把握其中的关键点。2. 理论基础栈与队列的核心特性2.1 栈的FILO特性栈(Stack)是一种后进先出(LIFO)的数据结构只允许在一端(栈顶)进行插入和删除操作。这种特性使得栈特别适合处理需要回退的场景比如函数调用栈括号匹配检查表达式求值浏览器的前进后退功能栈的基本操作包括push元素入栈pop栈顶元素出栈peek/top查看栈顶元素但不移除isEmpty判断栈是否为空2.2 队列的FIFO特性队列(Queue)是一种先进先出(FIFO)的数据结构允许在一端(队尾)插入元素在另一端(队头)删除元素。队列的典型应用场景包括消息队列打印任务队列广度优先搜索(BFS)缓存实现队列的基本操作包括enqueue元素入队dequeue队首元素出队front查看队首元素isEmpty判断队列是否为空提示理解栈和队列的核心区别是解决今天所有题目的基础。栈是后来居上队列是先来先到。3. 232. 用栈实现队列3.1 问题分析题目要求仅使用栈的基本操作来实现一个队列的所有功能。这意味着我们需要用后进先出的栈来模拟先进先出的队列行为。3.2 双栈解法关键思路是使用两个栈输入栈(inStack)负责接收push操作输出栈(outStack)负责提供pop和peek操作当需要pop或peek时如果outStack为空则将inStack的所有元素依次弹出并压入outStack这样最早进入inStack的元素就到了outStack的顶部class MyQueue: def __init__(self): self.inStack [] self.outStack [] def push(self, x: int) - None: self.inStack.append(x) def pop(self) - int: if not self.outStack: while self.inStack: self.outStack.append(self.inStack.pop()) return self.outStack.pop() def peek(self) - int: if not self.outStack: while self.inStack: self.outStack.append(self.inStack.pop()) return self.outStack[-1] def empty(self) - bool: return not self.inStack and not self.outStack3.3 复杂度分析时间复杂度pushO(1)pop/peek均摊O(1)每个元素最多被压入和弹出各两次空间复杂度O(n)需要两个栈存储所有元素3.4 注意事项只有在outStack为空时才需要转移元素否则直接操作outStack即可转移元素时要确保inStack的所有元素都移动到outStack判断队列为空的条件是两个栈都为空4. 225. 用队列实现栈4.1 问题分析这次需要用队列实现栈的功能即用FIFO结构模拟LIFO行为。相比上一题这题的解法更加多样。4.2 单队列解法核心思路是每次push新元素后将队列中已有的元素依次出队再入队使得新元素位于队首from collections import deque class MyStack: def __init__(self): self.q 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() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.q4.3 双队列解法也可以使用两个队列一个作为主队列另一个作为辅助队列push时直接加入主队列pop/top时将主队列中除最后一个元素外的所有元素转移到辅助队列操作完后再转移回来4.4 复杂度分析单队列解法pushO(n)pop/topO(1)双队列解法pushO(1)pop/topO(n)4.5 经验分享在实际面试中面试官可能会要求比较两种解法的优劣。单队列解法代码更简洁但push操作较慢双队列解法push快但pop慢。可以根据具体场景选择。5. 20. 有效的括号5.1 问题分析给定一个只包含括号字符的字符串判断括号是否有效匹配。这是栈的经典应用场景。5.2 栈解法遍历字符串遇到左括号就压入栈遇到右括号就检查是否与栈顶的左括号匹配最后检查栈是否为空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 stack5.3 边界情况处理空字符串视为有效只有左括号或只有右括号无效括号数量匹配但顺序不对无效5.4 优化技巧提前判断字符串长度是否为偶数奇数长度可以直接返回False使用字典存储括号匹配关系代码更简洁6. 1047. 删除字符串中的所有相邻重复项6.1 问题分析给定一个字符串需要重复删除相邻且相同的字母对直到无法删除为止。这类似于消消乐游戏机制。6.2 栈解法使用栈来模拟删除过程遍历字符串当前字符与栈顶相同则弹出栈顶否则压入当前字符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.3 复杂度分析时间复杂度O(n)每个字符最多被处理一次空间复杂度O(n)最坏情况下需要存储整个字符串6.4 实际应用这种相邻重复项删除的算法可以应用于文本编辑器中的连续空格删除代码格式化工具中的冗余字符清理数据清洗中的重复记录处理7. 综合比较与心得7.1 四道题目的共性虽然题目各不相同但都体现了栈和队列的核心特性用栈实现队列和用队列实现栈考察对两者特性的深入理解有效括号利用栈的LIFO特性处理嵌套结构删除相邻重复项栈的消消乐式应用7.2 刷题建议先理解数据结构的基本操作和特性画图辅助理解特别是栈和队列的转换过程注意边界条件的处理空栈/队列、奇数长度字符串等多思考时间复杂度和空间复杂度的优化空间7.3 个人踩坑记录在用栈实现队列时曾忘记在peek操作中也需处理栈转移有效括号问题中曾忽略只有右括号的情况删除相邻重复项时最初尝试了双指针解法发现不如栈解法直观经过这轮训练我对栈和队列的应用场景有了更深的理解。特别是认识到栈在处理具有最近相关性的问题时的天然优势而队列则更适合处理公平性问题。建议初学者不要只满足于AC而要深入理解每个解法背后的设计思想。