队列相关内容

基础知识

	队列是一种数据结构，最大特点是“先入先出”。java中，队列是一个定义了插入和删除操作的借口Queue。实现了接口Queue的常用类型
由LinkedList、ArrayDeque和PriorityQueue等。但PriorityQueue并不是真正的队列。

Queue常用操作函数

例题解答

1、滑动窗口的平均值

题目

	请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函
数next时都会在滑动窗口中添加一个整数，并返回滑动窗口中所有数字的平均值。

分析

	首先考虑要解决这个问题需要到先入先出的数据结构队列，然后需要保存窗口的大小限制，如果超出限制应该从队列中删除一个元素，
最后考虑怎么高效的计算窗口中所有数字的平均值，直观的方法是每次求总和再除以元素个数；还可以再优化一下，第一次求出总和之后，
其余每次求总和时，都只用原来的总和加上新增的值，然后再减去移除的值。

示例代码

public class MovingAverage{private Queue<Integer> nums;private int capacity;private int sum;public MovingAverage(int size){nums = new LinkedList<>();capacity = size;}public double next(int val){nums.offer(val);sum += val;if(nums.size() > capacity){sum -= nums.poll();}return (double)sum/nums.size();}
}

2、最近请求次数

题目

	请实现如下类型RecentCounter,它是统计过去3000ms内的请求次数的计数器。该类型的构造函数RecentCounter初始化计数器，
请求数初始化为0：函数ping(int t)在时间t添加一个新请求（t表示以毫秒为单位的时间），并返回过去3000ms内（时间范围为[t-
3000,t]）发生的所有请求数。假设每次调用函数ping的参数t都比之前调用的参数值大。

分析

	首先根据题分析需要使用先入先出的数据结构，因此选择队列，将某个时间范围的所有时间看成一个冠以时间的滑动窗口，每当
一个新的请求发生时，该窗口包含一个新的时间。如果某个时间由于太早而超出了时间范围，那么它将滑出该时间窗口。

示例代码

public class RecentCounter{private Queue<Integer> times;private int windowSize;public RecentCounter(){times = new LinkedList<>();windowSize = 3000;}public int ping(int t){times.offer(t);while(times.peek() + windowSize < t){times.poll();}return times.size();}
}

二叉树的广度优先搜索

	通常基于队列来实现二叉树的广度优先搜索。从二叉树的根节点开始，先把根节点放入一个队列之中，然后每次从队列中取出
一个节点遍历，如果该节点有左右子结点，则分别将它们添加到队列当中。重复这个过程，直到所有节点都遍历完为止，此时队列
为空

示例代码

    public List<Integer> bfs(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();if(root != null){queue.offer(root);}List<Integer> result = new ArrayList<>();while(!queue.isEmpty()){TreeNode node = queue.poll();result.add(node.val);if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}return result;}

3、在完全的二叉树中添加节点

题目

	在完全的二叉树中，除最后一层之外其它层的节点都是满的（第n层有2^n-1个节点）。最后一层的节点可能不满，该层所有
的节点尽可能向左边靠拢。* 构造函数CBTInserter(TreeNode root)，用一棵完全二叉树的根节点初始化该数据结构。* 函数insert(int v)在完全二叉树中添加一个值为v的节点，并返回被插入节点的父节点。

分析

	解决这个问题的关键在于理解完全二叉树的特点及在二叉树中添加节点的顺序。根据完全二叉树的定义，在完全二叉树中只
有最下面层可能是不满的，其它层都是满的。如果最下面一层不是满的，则从左到右找到该层的第1个空缺位置并添加新的节点。如果最下面一层是满的，此时再在二叉树中添加新的节点将会再二叉树中添加新的一层，而且在新层的最左边。

示例代码

public class CBTInserter{private Queue<TreeNode> queue;private TreeNode root;public CBTInserter(TreeNode root){this.root = root;queue = new LinkedList<>();queue.offer(root);//将最底层没填满的节点放入队列中while(queue.peek().left != null && queue.peek().right != null){TreeNode node = queue.poll();queue.offer(node.left);queue.offer(node.right);}}public int insert(int v){TreeNode parent = queue.peek();TreeNode node = new TreeNode(v);//由于队列中的节点都是为填满的，所以如果左子节点不为空，那么右子结点必然是空if(parent.left == null){parent.left = node;}else{parent.right = node;//左右节点全部填满，则将该节点从队列中移除queue.poll();//再将该节点的左右子节点添加到队列中queue.offer(parent.left);queue.offer(parent.right);}return parent.val;}public TreeNode get_root(){return this.root;}
}

4、二叉树中每层最大值

题目

	输入一颗二叉树，请找出二叉树中每层的最大值。

分析

	要找出二叉树每层的最大值，那么就要逐层遍历二叉树，按照广度优先的顺序遍历二叉树。

示例代码

//用一个队列实现
public List<Integer> largestValues(TreeNode root){int current = 0;int next = 0;Queue<TreeNode> queue = new LinkedList<>();if(root != null){queue.offer(root);current = 1;}List<Integer> result = new LinkedList<>();int max = Integer.MIN_VALUE;while(!queue.isEmpty()){TreeNode node = queue.poll();current --;max = Math.max(max,node.val);if(node.left != null){queue.offer(node.left);next ++;}if(node.right != null){queue.offer(node.right);next ++;}if(current == 0){result.add(max);max = Integer.MIN_VALUE;current = next;next = 0;}}return result;
}//用两个队列实现
public List<Integer> largestValues(TreeNode root){Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();if(root != null){queue1.offer(root);}List<Integer> result = new LinkedList<>();int max = Integer.MIN_VALUE;while(!queue1.isEmpty()){TreeNode node = queue1.poll();max = Math.max(max,node.val);if(node.left != null){queue2.offer(node.left);}if(node.right != null){queue2.offer(node.right);}if(queue1.isEmpty()){result.add(max);max = Integer.MIN_VALUE;queue1 = queue2;queue2 = new LinkedList<>();}}return result;
}

5、二叉树最低层最左边的值

题目

	如何在一棵二叉树中找出它最低层最左边节点的值？假设二叉树中最少有一个节点。

分析

	分析题目可知，还是通过二叉树的广度优先搜索算法来解决。

示例代码

public int findBottomLeftValue(TreeNode root){Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();queue1.offer(root);int bottomLeft = root.val;while(!queue1.isEmpty()){TreeNode node = queue1.poll();if(node.left != null){queue2.offer(node.left);}if(node.right != null){queue2.offer(node.right);}if(queue1.isEmpty()){queue1 = queue2;queue2 = new LinkedList<>();if(!queue1.isEmpty()){bottomLeft = queue1.peek().val;}}}return bottomLeft;
}

6、二叉树的右侧视图

题目

	给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图。

分析

	二叉树的右侧视图，可以当做求二叉树每层的最右节点值的集合。需要使用广度优先搜索算法遍历树。

示例代码

public List<Integer> rightSideView(TreeNode root){List<Integer> result = new LinkedList<>();Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();if(root != null){queue1.offer(root);}else{return result;}while(!queue1.isEmpty()){TreeNode node = queue1.poll();if(node.left != null){queue2.offer(node.left);}if(node.right != null){queue2.offer(node.right);}if(queue1.isEmpty()){result.add(node.val);queue1 = queue2;queue2 = new LinkedList<>();}}return result;
}

总结

	如果数据符合先入先出的条件，则可以考虑使用队列的数据结构来解决，队列可以用来实现二叉树的广度优先搜索。