第7章 队列

队列的应用

剑指offerⅡ41：滑动窗口的平均值

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

class MovingAverage {
    Deque<Integer> queue;
    int capacity;
    int sum;

    public MovingAverage(int size) {
        queue = new LinkedList<>();
        capacity = size;
        sum = 0;
    }

    public double next(int val) {
        queue.offer(val);
        sum += val;
        if (queue.size() > capacity) {
            int num = queue.pollFirst();
            sum -= num;
        }
        return (double) sum / queue.size();
    }
}

剑指offerⅡ42：最近请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

可以考虑请求的顺序是：1，2，3，100000。

class RecentCounter {
    Deque<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<>();
    }

    public int ping(int t) {
        queue.offer(t);
        while (t - queue.getFirst() > 3000) {
            queue.pollFirst();
        }
        return queue.size();
    }
}

二叉树的广度优先搜索

剑指offerⅡ43：往完全二叉树中添加节点

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的根节点。

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：

输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

算法：