尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

栈与队列基础及LeetCode经典题解

发布时间：2026/11/2 4:52:11 尧图网站建设
栈与队列基础及LeetCode经典题解

1. 栈与队列基础概念解析

栈和队列是计算机科学中最基础的两种线性数据结构，它们的核心区别在于数据元素的进出顺序。栈遵循后进先出（LIFO）原则，就像餐厅里叠放的餐盘，最后放入的总是最先被取出；而队列遵循先进先出（FIFO）原则，如同排队购票的队伍，先来的人先获得服务。

在内存管理中，栈用于函数调用和局部变量存储，而队列则广泛应用于任务调度、消息传递等场景。理解它们的底层实现机制对编写高效算法至关重要。例如，栈的push/pop操作时间复杂度都是O(1)，而队列的enqueue/dequeue在简单实现中可能涉及数据搬移。

关键理解：栈只允许在顶端操作，队列则在尾端添加、前端移除。这种结构差异决定了它们适用的场景完全不同。

2. LeetCode 232：用栈实现队列

2.1 问题需求分析

题目要求仅使用标准栈操作（push、pop、peek、empty）实现队列的所有功能。队列需要支持push（尾部插入）、pop（头部移除）、peek（获取头部元素）和empty（判空）操作。

直接使用单个栈无法满足需求，因为栈的弹出顺序与队列相反。这就需要我们设计特殊的双栈结构来模拟队列行为。

2.2 双栈解法实现

核心思路是使用两个栈：

  • 输入栈（stack_in）：专门处理新元素入队
  • 输出栈（stack_out）：专门处理元素出队

当需要出队时：

  1. 如果输出栈为空，将输入栈的所有元素依次弹出并压入输出栈
  2. 此时输出栈的栈顶就是队列的头部元素
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 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 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_out

2.3 时间复杂度分析

  • push操作：直接压入输入栈，O(1)
  • pop/peek操作：均摊时间复杂度仍为O(1)。虽然有时需要转移全部元素，但每个元素只会被转移一次

实际工程中，这种实现方式在大多数情况下性能良好，但在高频率交替进行push和pop操作时可能产生性能波动。

3. LeetCode 225：用队列实现栈

3.1 问题需求对比

与前一题相反，这次需要用队列的先进先出特性实现栈的后进先出。队列的基本操作包括push（入队）、pop（出队）、peek（查看队首）和empty（判空）。

3.2 单队列解法

最直观的方法是使用两个队列，但通过巧妙设计，单个队列也能实现：

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.q

3.3 双队列解法

另一种思路是使用主队列和辅助队列：

  1. push时直接加入主队列
  2. pop时将主队列除最后一个元素外全部转移到辅助队列
  3. 交换两个队列的角色
class MyStack: def __init__(self): self.main_q = deque() self.helper_q = deque() def push(self, x: int) -> None: self.main_q.append(x) def pop(self) -> int: while len(self.main_q) > 1: self.helper_q.append(self.main_q.popleft()) val = self.main_q.popleft() self.main_q, self.helper_q = self.helper_q, self.main_q return val def top(self) -> int: return self.main_q[-1] if self.main_q else None def empty(self) -> bool: return not self.main_q

性能对比：单队列解法push操作O(n)，pop操作O(1)；双队列解法则相反。根据使用场景选择合适方案。

4. LeetCode 20：有效的括号

4.1 问题场景分析

这是一个经典的栈应用场景，需要检查字符串中的括号是否匹配且嵌套正确。常见于编译器语法检查、配置文件解析等场景。

4.2 栈解法实现

算法步骤：

  1. 创建空栈和括号映射表
  2. 遍历字符串：
    • 遇到左括号入栈
    • 遇到右括号时检查栈顶是否匹配
  3. 最后检查栈是否为空
def isValid(s: str) -> bool: stack = [] mapping = {')': '(', '}': '{', ']': '['} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping: if not stack or stack[-1] != mapping[char]: return False stack.pop() else: return False # 非法字符 return not stack

4.3 边界情况处理

  • 空字符串：视为有效
  • 只有左括号：无效
  • 只有右括号：无效
  • 括号交叉：如"([)]"无效
  • 包含非括号字符：根据题目要求处理

工程实践：实际开发中可以扩展支持更多括号类型，如HTML标签对。同时应考虑性能优化，如在发现不匹配时立即返回。

5. LeetCode 1047：删除字符串相邻重复项

5.1 问题变形思考

这道题可以看作括号匹配问题的变种，相邻相同字符相当于"自匹配"的括号对。使用栈可以高效解决这类相邻消除问题。

5.2 栈解法实现

算法流程：

  1. 初始化空栈
  2. 遍历字符串：
    • 当前字符与栈顶相同则弹出栈顶
    • 否则压入当前字符
  3. 最后将栈内字符拼接为结果
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)

5.3 算法优化

对于特别长的字符串，可以考虑以下优化：

  1. 使用双指针模拟栈操作，减少内存使用
  2. 预先分配足够大的列表作为栈，避免动态扩容
  3. 并行处理：对于超长字符串可分块处理后再合并
# 双指针优化版 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])

6. 综合应用与进阶思考

6.1 四道题目的内在联系

这组题目共同展示了栈这一数据结构的强大灵活性：

  • 232题：用栈模拟队列，展示数据结构间的相互转换
  • 225题：用队列模拟栈，培养逆向思维能力
  • 20题：经典栈应用，解决嵌套结构问题
  • 1047题：栈在序列处理中的高效应用

6.2 实际工程应用案例

  1. 浏览器前进后退功能：使用双栈实现
  2. 文本编辑器撤销操作：通常采用栈结构记录操作历史
  3. 函数调用栈：程序执行时管理函数调用关系
  4. 消息队列的延迟消费：类似队列实现栈的思路

6.3 复杂度对比与选择建议

题目最优解法时间复杂度空间复杂度
232双栈法O(1)均摊O(n)
225单队列法push:O(n)O(n)
20栈匹配O(n)O(n)
1047栈消除O(n)O(n)

在面试中，面试官通常会期待先看到基础解法，然后再讨论优化方案。建议先实现清晰可读的版本，再考虑性能优化。

7. 常见错误与调试技巧

7.1 栈实现队列的易错点

  1. 没有正确处理连续pop操作：每次pop前都应检查输出栈是否为空
  2. peek实现与pop不一致：应复用pop逻辑避免代码重复
  3. 判空条件不完整：需要同时检查两个栈

7.2 括号匹配的边界情况

  1. 忽略空字符串处理
  2. 未考虑字符串只含单个括号的情况
  3. 混合类型括号交叉时的处理错误
  4. 栈操作后忘记检查是否为空

调试时可使用以下测试用例：

  • "" → true
  • "[" → false
  • "(]" → false
  • "([)]" → false
  • "{[]}" → true

7.3 删除相邻重复项的优化验证

对于优化算法，需要验证：

  1. 结果与原算法一致
  2. 处理超长字符串时的内存使用情况
  3. 特殊字符和Unicode字符的处理
  4. 连续多个重复字符的情况

8. 扩展练习与学习建议

8.1 推荐延伸题目

    1. 最小栈（设计支持获取最小元素的栈）
    1. 字符串解码（栈处理嵌套结构）
    1. 下一个更大元素 II（循环数组处理）
    1. 柱状图中最大的矩形（单调栈应用）

8.2 系统化学习建议

  1. 先掌握每种数据结构的标准实现
  2. 理解它们的操作时间复杂度
  3. 练习基础应用场景题目
  4. 尝试变形和组合问题
  5. 总结常见解题模式

8.3 代码随想录刷题路线

按照代码随想录推荐的顺序学习：

  1. 先掌握栈和队列的基本实现
  2. 然后解决经典应用问题
  3. 最后挑战综合性题目
  4. 每个专题完成后进行总结复盘

我在实际刷题中发现，坚持每天解决2-3道相关题目并写解题笔记，两周内就能显著提升对栈和队列的理解深度。对于容易混淆的操作，建议手动画出内存变化示意图，这对理解数据结构的行为非常有帮助。

网站建设 视觉设计 SEO优化
返回列表