栈与队列经典题目解析：实现与应用

1. 栈与队列经典题目解析今天要分享的是《代码随想录》Day10的四道经典题目232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047.删除字符串中的所有相邻重复项。这几道题都是栈和队列这一章节的核心题目也是面试中的高频考点。1.1 栈与队列基础回顾栈Stack和队列Queue是两种最基础的数据结构。栈遵循LIFO后进先出原则而队列遵循FIFO先进先出原则。在大多数编程语言的标准库中都提供了这两种数据结构的实现。栈的基本操作包括push将元素压入栈顶pop弹出栈顶元素peek/top查看栈顶元素但不弹出isEmpty判断栈是否为空队列的基本操作包括enqueue将元素加入队尾dequeue从队首移除元素front查看队首元素isEmpty判断队列是否为空理解这些基本操作是解决今天这几道题目的基础。2. 232. 用栈实现队列2.1 问题描述请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty。2.2 解题思路用栈实现队列的关键在于如何利用两个栈来模拟队列的FIFO特性。我们可以将一个栈作为输入栈另一个作为输出栈当执行push操作时直接将元素压入输入栈当执行pop或peek操作时如果输出栈为空则将输入栈的所有元素依次弹出并压入输出栈然后从输出栈弹出或查看栈顶元素这样做的原理是将输入栈的元素转移到输出栈后元素的顺序就被反转了正好符合队列的FIFO特性。2.3 代码实现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_out2.4 复杂度分析时间复杂度push操作O(1)pop/peek操作摊还时间复杂度O(1)虽然最坏情况下是O(n)但每个元素最多被压入和弹出各一次空间复杂度O(n)需要两个栈存储所有元素2.5 注意事项在pop和peek操作时一定要先检查队列是否为空只有当输出栈为空时才需要将输入栈的元素全部转移到输出栈这种实现方式下peek和pop操作有重复代码可以提取公共逻辑3. 225. 用队列实现栈3.1 问题描述请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop和empty。3.2 解题思路用队列实现栈的关键在于如何让最后入队的元素最先出队。有两种主要方法方法一使用两个队列主队列和辅助队列push操作将新元素加入辅助队列然后将主队列的所有元素依次出队并入队到辅助队列交换主队列和辅助队列的角色pop操作直接从主队列出队方法二使用一个队列push操作将新元素加入队列然后将队列中除最后一个元素外的所有元素依次出队并重新入队pop操作直接出队这里我们展示方法一的实现因为它更容易理解。3.3 代码实现from collections import deque class MyStack: def __init__(self): self.queue1 deque() self.queue2 deque() def push(self, x: int) - None: self.queue2.append(x) while self.queue1: self.queue2.append(self.queue1.popleft()) self.queue1, self.queue2 self.queue2, self.queue1 def pop(self) - int: return self.queue1.popleft() def top(self) - int: return self.queue1[0] def empty(self) - bool: return not self.queue13.4 复杂度分析时间复杂度push操作O(n)需要将所有元素从一个队列转移到另一个队列pop/top操作O(1)空间复杂度O(n)需要两个队列存储所有元素3.5 注意事项每次push操作后queue1中元素的顺序就是栈的顺序使用双端队列deque可以更高效地进行队列操作方法二虽然只需要一个队列但push操作的时间复杂度仍然是O(n)4. 20. 有效的括号4.1 问题描述给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合4.2 解题思路这是一个经典的栈应用问题。我们可以遍历字符串遇到左括号时将其压入栈遇到右括号时如果栈为空返回False弹出栈顶元素检查是否匹配最后检查栈是否为空4.3 代码实现class Solution: def isValid(self, 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 stack4.4 复杂度分析时间复杂度O(n)只需遍历一次字符串空间复杂度O(n)最坏情况下需要存储所有左括号4.5 注意事项使用字典存储括号匹配关系可以使代码更简洁处理右括号时一定要先检查栈是否为空最后必须检查栈是否为空否则可能漏掉未匹配的左括号5. 1047. 删除字符串中的所有相邻重复项5.1 问题描述给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。在 S 上反复执行重复项删除操作直到无法继续删除。返回最终字符串。5.2 解题思路这个问题同样可以使用栈来解决遍历字符串中的每个字符如果栈不为空且栈顶元素等于当前字符则弹出栈顶元素表示删除这对相邻重复项否则将当前字符压入栈最后将栈中剩余字符拼接成字符串返回5.3 代码实现class Solution: def removeDuplicates(self, s: str) - str: stack [] for char in s: if stack and stack[-1] char: stack.pop() else: stack.append(char) return .join(stack)5.4 复杂度分析时间复杂度O(n)只需遍历一次字符串空间复杂度O(n)最坏情况下需要存储整个字符串5.5 注意事项这个问题类似于括号匹配问题都是栈的典型应用使用栈可以避免字符串的频繁修改提高效率最后需要将栈中的字符拼接成字符串返回6. 总结与心得通过这四道题目我们可以深入理解栈和队列这两种基础数据结构的特点和应用场景栈和队列可以互相模拟但时间复杂度会有所不同栈特别适合处理对称性、匹配性问题如括号匹配、相邻重复项删除在实际编程中选择合适的数据结构可以大大简化问题的解决方案在实际面试中这几道题目都是高频考点特别是用栈实现队列和有效的括号这两题。建议熟练掌握它们的实现思路和代码并能够分析时间复杂度和空间复杂度。在刷题过程中我发现以下几点特别重要理解每种数据结构的基本特性和适用场景学会用简单的数据结构组合实现更复杂的功能注意边界条件的处理如空栈、空队列等情况多思考时间复杂度和空间复杂度的优化空间最后建议在完成这些题目后可以尝试LeetCode上栈和队列章节的其他题目如150.逆波兰表达式求值、239.滑动窗口最大值等进一步巩固相关知识。