栈和队列问题

目的与范围

本文档涵盖了使用栈和队列数据结构的常见面试问题。它概述了典型的问题模式、示例问题、解决方案方法和实现细节。有关数据结构基础的通用信息，请参阅线性数据结构。

栈和队列基础

栈概述

栈是一种后进先出（LIFO）的数据结构，支持两种主要操作：

push: 将元素添加到栈顶
pop: 从栈顶移除元素

其他操作包括：

peek/top: 查看栈顶元素但不移除它
isEmpty: 检查栈是否为空

来源：leetcode/stack/ExclusiveTimeOfFunctions.java, leetcode/stack/DailyTemperatures.java

队列概述

队列是一种先进先出（FIFO）的数据结构，支持两种主要操作：

enqueue/add: 将元素添加到队列尾部
dequeue/remove: 从队列头部移除元素

其他操作包括：

peek/front: 查看队列头部元素但不移除它
isEmpty: 检查队列是否为空

常见问题模式

栈问题模式

模式	描述	示例问题
单调栈	保持元素递增或递减顺序的栈	每日温度
表达式求值	计算算术表达式	计算器，逆波兰表示法
括号匹配	验证匹配的括号或方括号	有效的括号
函数调用模拟	使用栈模拟函数调用	函数的独占时间
最小/最大栈	带额外最小/最大操作的栈	最小栈

队列问题模式

模式	描述	示例问题
BFS 遍历	图/树的层序遍历	层序遍历
任务调度	调度和处理任务	任务调度器
滑动窗口	维护一个元素窗口	移动平均，滑动窗口最大值

示例问题

问题 1：最小栈

问题： 设计一个栈，支持 push、pop、top 操作，并能在常数时间内检索到最小元素。

方法示意图

实现细节

栈中的每个节点存储：
- 实际值（data）
- 截至此节点的栈中最小值（min）
- 指向下一个节点的引用（next）
getMin() 操作简单地返回栈顶节点的 min 值
时间复杂度：所有操作均为 O(1)

示例流程

来源：leetcode/design/MinStack.java:15-55

问题 2：每日温度

问题： 给定一个每日温度数组，对于每一天，找出你需要等待多少天才能等到一个更温暖的温度。

方法示意图

实现细节

使用单调栈来跟踪温度的索引
当找到更高的温度时，计算天数差
时间复杂度：O(n)，其中 n 是温度的数量
空间复杂度：最坏情况下 O(n)

示例： 输入：[73, 74, 75, 71, 69, 72, 76, 73] 输出：[1, 1, 4, 2, 1, 1, 0, 0]

来源：leetcode/stack/DailyTemperatures.java:7-21

问题 3：函数的独占时间

问题： 给定格式为 id:start/end:timestamp 的函数执行日志，计算每个函数的独占执行时间。

方法示意图

关键实现点

使用栈来跟踪当前正在执行的函数
对于“start”日志，更新之前运行函数的耗时
对于“end”日志，计算完成函数的耗时
时间复杂度：O(n)，其中 n 是日志的数量
空间复杂度：O(m)，其中 m 是函数调用的最大深度

示例： 对于日志：["0:start:0", "1:start:2", "1:end:5", "0:end:6"] 输出：[3, 4]（函数 0 运行 3 个时间单位，函数 1 运行 4 个时间单位）

来源：leetcode/stack/ExclusiveTimeOfFunctions.java:30-55