← 返回首页

第九章-队列和栈

第九章：队列和栈 (Queue and Stack)

学习内容

队列和栈是两种重要的线性数据结构，分别遵循先进先出（FIFO）和后进先出（LIFO）的原则。

队列 (Queue)

#### 基本概念


#### 实现方式
1. 数组实现：使用循环数组避免空间浪费
2. 链表实现：使用单链表，维护头尾指针

#### 特殊队列


栈 (Stack)

#### 基本概念


#### 实现方式
1. 数组实现：使用数组和栈顶指针
2. 链表实现：使用单链表，栈顶为链表头部

相互实现

#### 用栈实现队列


#### 用队列实现栈


单调栈和单调队列

#### 单调栈


#### 单调队列


重点和难点

重点


1. 理解队列和栈的基本特性和应用场景
2. 掌握队列和栈的相互实现方法
3. 熟悉单调栈和单调队列的应用

难点


1. 单调栈和单调队列的维护
2. 复杂问题中数据结构的选择
3. 边界条件的处理

练习题

基础题目


1. 用栈实现队列 (Implement Queue using Stacks)
- 题目：使用两个栈实现先入先出队列。
- 解题思路：一个栈用于入队操作，另一个栈用于出队操作。出队时如果输出栈为空，将输入栈所有元素倒入输出栈。
- 注意点：注意处理输出栈为空时的情况。

2. 最小栈 (Min Stack)
- 题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- 解题思路：使用辅助栈记录每个状态下的最小值，或在每个节点中存储当前最小值。
- 注意点：注意处理栈为空时获取最小值的情况。

单调栈题目


1. 每日温度 (Daily Temperatures)
- 题目：请根据每日气温列表 temperatures，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
- 解题思路：使用单调递减栈存储温度的索引，遇到更高温度时计算间隔天数。
- 注意点：注意栈中存储的是索引而非温度值。

2. 柱状图中最大的矩形 (Largest Rectangle in Histogram)
- 题目：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。
- 解题思路：使用单调递增栈，当遇到较小高度时计算以栈顶高度为高的矩形面积。
- 注意点：注意处理边界情况，可以在数组首尾添加哨兵元素简化操作。

单调队列题目


1. 滑动窗口最大值 (Sliding Window Maximum)
- 题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
- 解题思路：使用单调递减双端队列维护窗口中的最大值，队首始终为当前窗口的最大值。
- 注意点：注意维护队列的单调性，及时移除超出窗口范围的元素。

解题思路总结

队列和栈的应用场景


1. 队列：任务调度、广度优先搜索、缓冲区等
2. 栈：函数调用栈、表达式求值、深度优先搜索等

单调栈的解题模板


1. 维护栈的单调性
2. 在破坏单调性时进行计算
3. 栈中通常存储索引而非值

单调队列的解题模板


1. 维护队列的单调性
2. 维护队列的窗口范围
3. 队首始终为最优解

学习时间

建议学习时间：2-3天