算法思维训练（六）| 队列💭

一、队列基础知识

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。
• 函数get_root()返回完全二叉树的根节点。
  

题目分析

难度： ⭐⭐🐇🐇🐇
思路： 先填充左节点，再填充右节点；然后再填充子节点的左右节点，不难看出填补左右节点时是有顺序的，即从上至下，从左至右填充，这和队列的先进先出有一定的相似性。我们可以利用队列记录填充左右节点的顺序，在添加元素时，去除队首节点，如果左节点为空，新节点为该节点的左子节点，否则右节点同理判断；不同的是，如果是添加到右节点，此时需要将首节点移出队列；最后将新的节点加入到队列。

参考代码

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。

题目分析

难度： 略
思路： 略

参考代码

Tips：2024-09-02 15:05

---

题目四：二叉树的右侧视图

  题目：给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图。例如，图7.6中二叉树的右侧视图包含节点8、节点10和节点7。请写一个函数返回二叉树的右侧视图节点的值。

题目分析

难度： 略
思路： 略

参考代码

Tips：2024-09-02 15:05

---

2. 附加题

队列题目 | 队列 & 栈

题目一：用两个栈实现队列

  用两个栈来实现一个队列，使用n个元素来完成n次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

题目分析

难度： ⭐
思路： 此题很容易想到，入栈时放入stack1，出栈时，借助stack2存入stack1依次出栈的元素，最后出栈第一个元素，再将stack2元素依次入栈stack1中。这个过程中，不难发现，stack2元素依次出栈到stack1的过程是不必要的；stack1用于存放入栈数据，stack2用于出栈数据，当stack2元素出栈完时，再次出栈时将stack1的所有元素出栈到stack2，再由stack2进行出栈操作即可，如此可以省下一定操作次数。

参考代码

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    //入栈操作
    public void push(int node) {
        stack1.push(node);
    }

    //出栈操作
    public int pop() {
        if (stack2.size() <= 0) {
            while (stack1.size() != 0) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

Tips：2024-09-11 18:35

---

题目二：包含min函数的栈

  定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
  此栈包含的方法有：
    1. push(value):将value压入栈中
    2. pop():弹出栈顶元素
    3. top():获取栈顶元素
    4. min():获取栈中最小元素

题目分析

难度： ⭐
思路： 略

参考代码

Tips：2024-09-11 18:39

---

三、章节小结

  略

---