一、队列基础知识
1. 队列概念
队列是一种常用的数据结构，它最大的特点是“先入先出”，即先进入队列中的元素最先出来。由于队列要保证“先入先出”的顺序，因此新的元素只能添加到队列的尾部，同时只能删除位于队列最前面的元素。
2. 本章题目节点类
/**
* 树节点
* @author nepakina
*/
public class TreeNode {
public int val = 0;
public TreeNode left = null;
public TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
二、队列知识扩展
1. 队列的知识
在 Java 中，队列是一个定义了插入和删除操作的接口 Queue。
| 操作 | 抛出异常 | 不抛出异常 | 返回结果 |
|---|---|---|---|
| 插入元素 | add(e) | offer(e) | true / false |
| 删除队首元素 | remove() | poll() | 队首元素 |
| 返回队首元素 | element() | peek() | 队首元素 |
在某些时候调用函数 add、remove 和 element 时可能会抛出异常，但调用函数 offer、poll 和 peek 不会抛出异常。例如，当调用函数 remove 从一个空的队列中删除最前面的元素时，就会抛出异常。但如果调用函数 poll 从一个空的队列中删除最前面的元素，则会返回 null。
在 Java 中实现了接口 Queue 的常用类型有 LinkedList、ArrayDeque 和 PriorityQueue 等，但 PriorityQueue 并不是真正的队列，PriorityQueue 也称优先队列，是有序的队列，不满足先入先出的规则。
队列题目 | 队列的应用
题目一：滑动窗口的平均值
题目描述
请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函数next时都会在滑动窗口中添加一个整数，并返回滑动窗口中所有数字的平均值。
public MovingAverage {
public MovingAverage (int size);
public double next(int val);
}
例如，假设滑动窗口的大小为 3。第 1 次调用next函数时在滑动窗口中添加整数 1，此时窗口中只有一个数字 1，因此返回平均值 1。第 2 次调用 next 函数时添加整数 2，此时窗口中有两个数字 1 和 2，因此返回平均值 1.5。第 3 次调用 next 函数时添加数字 3，此时有 3 个数字 1、2、3，因此返回平均值 2。第 4 次调用 next 函数时添加数字 4，由于受到窗口大小的限制，滑动窗口中最多只能有 3 个数字，因此第 1 个数字 1 将滑 出窗口，此时窗口中包含 3 个数字 2、3、4，返回平均值 3。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 队列的简单应用
参考代码
import java.util.LinkedList;
import java.util.Queue;
/**
* @author nepakina
*/
public class MovingAverage {
private final int size;
private int total = 0;
public Queue<Integer> queue;
public MovingAverage (int size) {
this.size = size;
queue = new LinkedList<>();
}
public double next(int val) {
if (queue.size() == size) {
Integer poll = queue.poll();
if (poll != null) {
total -= poll;
}
}
queue.offer(val);
total += val;
return total * 1.0 / size;
}
}
Tips：2024-06-14 17:02
题目二：最近请求次数
题目描述
请实现如下类型RecentCounter，它是统计过去3000ms内的请求次数的计数器。该类型的构造函数RecentCounter初始化计数器，请求数初始化为0；函数ping(int t)在时间t添加一个新请求（t表示以毫秒为单位的时间），并返回过去3000ms内（时间范围为[t - 3000，t]）发生的所有请求数。假设每次调用函数ping的参数t都比之前调用的参数值大。
public RecentAverage {
public RecentAverage ();
public int ping(int t);
}
例如，在初始化一个RecentCounter计数器之后，ping(1)的返回值是1，因为时间范围[-2999，1]只有1个请求；ping(10)的返回值是2，因为时间范围[-2990，10]有2个请求；ping(3001)的返回值是3，因为时间范围[1，3001]有3个请求；ping(3002)的返回值是3，因为时间范围[2，3002]有3个请求，发生在时间1的请求已经不在这个时间范围内。
题目分析
难度： 略
思路： 略
参考代码
import java.util.LinkedList;
import java.util.Queue;
/**
* @author nepakina
*/
public class RecentAverage {
private final Queue<Integer> queue;
public RecentAverage() {
queue = new LinkedList<>();
}
public int ping(int t) {
// 计算边界
int limit = t - 3000;
while (!queue.isEmpty()) {
Integer peek = queue.peek();
if (peek < limit) {
// 如果超过边界，出列
queue.poll();
} else {
break;
}
}
// 添加到队列
queue.offer(t);
return queue.size();
}
}
Tips：2024-08-06 18:00
队列题目 | 二叉树的广度优先搜索
题目一：在完全二叉树中添加节点
题目描述
在完全二叉树中，除最后一层之外其他层的节点都是满的（第n层有2n - 1个节点）。最后一层的节点可能不满，该层所有的节点尽可能向左边靠拢。例如，图中的 4 棵二叉树均为完全二叉 树。实现数据结构CBTInserter有如下3种方法。
- 构造函数
CBTInserter (TreeNode root)，用一棵完全二叉树的根节点初始化该数据结构。 - 函数
insert (int v)在完全二叉树中添加一个值为 v 的节点，并返回被插入节点的父节点。例如，在如图(a)所示的完全二叉树中添加一个值为7的节点之后，二叉树如图(b)所示，并返回节点3。在如图(b)所示的完全二叉树中添加一个值为8的节点之后，二叉树如图(c)所示，并返回节点4。在如图(c)所示的完全二叉树中添加节点9会得到如图(d)所示的二叉树并返回节点4。 - 函数
getRoot()返回完全二叉树的根节点。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 先填充左节点，再填充右节点；然后再填充子节点的左右节点，不难看出填补左右节点时是有顺序的，即从上至下，从左至右填充，这和队列的先进先出有一定的相似性。我们可以利用队列记录填充左右节点的顺序，在添加元素时，去除队首节点，如果左节点为空，新节点为该节点的左子节点，否则右节点同理判断；不同的是，如果是添加到右节点，此时需要将首节点移出队列；最后将新的节点加入到队列。
参考代码
import nep.akina.algorithm.base.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author nepakina
*/
public class CBTInserter {
private TreeNode node;
private final Queue<TreeNode> queue;
public CBTInserter(TreeNode root) {
if (root == null) {
throw new NullPointerException();
}
this.node = root;
this.queue = new LinkedList<>();
queue.offer(root);
while (queue.peek().left != null && queue.peek().right != null) {
TreeNode temp = queue.poll();
queue.offer(temp.left);
queue.offer(temp.right);
}
}
public TreeNode getRoot() {
return node;
}
public int insert(int val) {
TreeNode newNode = new TreeNode(val);
// 如果元素左右节点都存在子节点，则移除
TreeNode peek = queue.peek();
if (peek.left == null) {
peek.left = newNode;
} else if (peek.right == null) {
peek.right = newNode;
queue.poll();
}
queue.offer(newNode);
return peek.val;
}
}
Tips：2024-08-06 18:16
题目二：二叉树中每层的最大值
题目描述
输入一棵二叉树，请找出二叉树中每层的最大值。例如，输入图中的二叉树，返回各层节点的最大值[3，4，9]。
题目分析
难度： ⭐⭐🐇🐇🐇
思路：
由于要找出二叉树中每层的最大值，因此在遍历时需要知道每层什么时候开始、什么时候结束。如果还是和前面一样只用一个队列来保存尚未遍历到的节点，那么有可能位于不同的两层的节点同时在队列之中。例如，遍历到节点 4 时，就把节点 4 从队列中取出来，此时节点 2 已经在队列中。接下来要把节点 4 的两个子节点（节点 5 和节点 1）都添加到队列中。这个时候第 2 层的节点 2 和第 3 层的节点 5、节点 1 都在队列中。
如果不同层的节点同时位于队列之中，那么每次从队列之中取出节点来遍历时就需要知道这个节点位于哪一层。解决这个问题的一个办法是计数。需要注意的是，当遍历某一层的节点时，会将下一层的节点也放入队列中。因此，可以用两个变量分别记录两层节点的数目，变量 count 记录当前遍历这一层中位于队列之中节点的数目，变量 next 记录下一层中位于队列之中节点的数目。
最开始把根节点插入队列中时，把变量 count 初始化为 1。接下来逐个从队列中取出节点遍历。每当从队列中取出一个节点时，当前层的剩余节点就少了一个，因此变量 count 的数目减 1。如果当前遍历的节点有子节点，那么将子节点插入队列中。由于子节点都位于当前遍历节点的下一层，因此在队列中添加一个子节点，变量 next 的数目将增加 1。
当变量 count 的数值变成0时，表示当前层的所有节点都已经遍历完。可以通过比较当前层的所有节点的值，找出这一层节点的最大值。接下来在开始遍历下一层节点之前，把变量 count 的值设为变量 next 的值，并把变量 next 重新初始化为 0。重复这个过程，直到所有节点都遍历完为止。
也可以使用两个队列实现，一个队列存储当前层元素，另一个队列存储下一层元素。
参考代码
public List<Integer> maxDepthValue(TreeNode root) {
int count = 0, next = 0;
// 初始时，将头节点放入队列
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
count++;
}
List<Integer> res = new ArrayList<>();
int max = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
// 出队列，计数 -1
TreeNode poll = queue.poll();
count--;
max = Math.max(poll.val, max);
// 子节点放入队列，同时记录数量
if (root.left != null) {
next++;
queue.offer(root.left);
}
if (root.right != null) {
next++;
queue.offer(root.right);
}
// 如果计数为 0，表示当前层元素已经遍历完，所以记录最大值
if (count == 0) {
res.add(max);
max = Integer.MIN_VALUE;
count = next;
next = 0;
}
}
return res;
}
Tips：2024-09-02 15:05
题目三：二叉树最低层最左边的值
题目描述
如何在一棵二叉树中找出它最低层最左边节点的值？假设二叉树中最少有一个节点。例如，在如图所示的二叉树中最低层最左边一个节点的值是 5。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 这题类似遇上题，不过使用两个队列的话更容易直接定位所求元素。
参考代码
public int farLeftValue(TreeNode root) {
if (root == null) {
return -1;
}
Queue<TreeNode> qa = new LinkedList<>();
Queue<TreeNode> qb = new LinkedList<>();
qa.offer(root);
int res = root.val;
while (!qa.isEmpty()) {
TreeNode poll = qa.poll();
if (poll.left != null) {
qb.offer(poll.left);
}
if (poll.right != null) {
qb.offer(poll.right);
}
// 交换两个队列
if (qa.isEmpty()) {
qa = qb;
qb = new LinkedList<>();
// 记录左侧元素
if (!qa.isEmpty()) {
res = qa.peek().val;
}
}
}
return res;
}
Tips：2024-09-02 15:05
题目四：二叉树的右侧视图
题目描述
给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图。例如，图 6.4 中二叉树的右侧视图包含节点 8、节点 10 和节点 7。请写一个函数返回二叉树的右侧视图节点的值。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 根据题意，每层取最后一个元素。这和上题几乎一直，可以对上题代码略微调整，在队列为空时，记录当前遍历时的元素即可。
参考代码
public List<Integer> rightElevation(TreeNode root) {
if (root == null) {
return null;
}
List<Integer> res = new ArrayList<>();
Queue<TreeNode> qa = new LinkedList<>();
Queue<TreeNode> qb = new LinkedList<>();
qa.offer(root);
while (!qa.isEmpty()) {
TreeNode poll = qa.poll();
if (poll.left != null) {
qb.offer(poll.left);
}
if (poll.right != null) {
qb.offer(poll.right);
}
// 交换两个队列
if (qa.isEmpty()) {
// 记录每层最后一个元素
res.add(poll.val);
qa = qb;
qb = new LinkedList<>();
}
}
return res;
}
Tips：2024-09-02 15:05
三、章节小结
如果一个数据集合的添加、删除操作满足“先入先出”的特点，即最先添加的数据最先被删除，那么可以用队列来实现这个数据集合。
队列经常被用来实现二叉树的广度优先搜索。首先将二叉树的根节点插入队列。然后每次从队列中取出一个节点遍历。如果该节点有子节点，则将子节点插入队列。重复这个过程，直到队列被清空，此时二叉树所有的节点都已经遍历完。
如果需要区分二叉树不同的层，那么至少有两种方法可以实现。第一种方法是用两个变量来表示当前层和下一层节点的数目。如果当前遍历的层的节点数目变成0，那么这一层所有的节点都已经遍历完，可以开始遍历下一层的节点。第二种方法是用两个队列分别存放当前层和下一层的节点。如果当前层对应的队列被清空，那么该层所有的节点就已经被遍历完，可以开始遍历下一层。