JavaSE集合-Queue入门与详解
Queue用于模拟"队列"这种数据结构(先进先出 FIFO)。队列的头部保存着队列中存放时间最长的元素,队列的尾部保存着队列中存放时间最短的元素。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素,队列不允许随机访问队列中的元素
【1】 PriorityQueue
PriorityQueue并不是一个比较标准的队列实现,PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序,而是按照队列元素的大小进行重新排序,这点从它的类名也可以看出来 。
PriorityQueue的应用之流式数据中计算第K个最大数:
public class KthLargest {
final PriorityQueue<Integer> queue;
final int k;
public KthLargest(int k ,int[] a){
this.k=k;
queue = new PriorityQueue<>();
for (int n:a) {
add(n);
}
}
public int add(int n){
if (queue.size()<k){
queue.offer(n);
}else if(queue.peek()<n){
queue.poll();
queue.offer(n);
}
System.out.println(queue.peek());
return queue.peek();
}
public static int KthLargest1(int k,int[]a){
List<Integer> nums = new ArrayList<Integer>();
for(int n:a){
if(nums.size()<k){
nums.add(n);
}else if (nums.get(0)<n){
nums.remove(0);
nums.add(n);
}
nums.sort((o1, o2) -> o1.compareTo(o2));
System.out.println("当前第 "+k+"大的数为 :"+nums.get(0)+nums);
}
return nums.get(0);
}
public static void main(String[] args){
int[] nums=new int[]{0,1,4,3,5,7,0,5,9,5};
int k=3;
int i = KthLargest1(k, nums);
KthLargest kthLargest = new KthLargest(k, nums);
}
}
【2】Deque
Deque接口代表一个"双端队列",双端队列可以同时从两端来添加、删除元素,因此Deque的实现类既可以当成队列使用、也可以当成栈使用。
【3】 ArrayDeque
是一个基于数组的双端队列,和ArrayList类似,它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素,当集合元素超出该数组的容量时,系统会在底层重新分配一个Object[]数组来存储集合元素。