集合Queue
程序员文章站
2022-03-14 15:05:39
...
Queue用于模拟队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。
PriorityQueue
PriorityQueue保存队列元素的顺序不是按加入队列的顺序,而是按队列元素的大小进行重新排序。因此当调用peek()或pool()方法取出队列中头部的元素时,并不是取出最先进入队列的元素,而是取出队列中的最小的元素。
PriorityQueue的排序方式
PriorityQueue中的元素可以默认自然排序(也就是数字默认是小的在队列头,字符串则按字典序排列)或者通过提供的Comparator(比较器)在队列实例化时指定的排序方式
代码测试
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(1);
queue.add(4);
queue.add(2);
queue.add(3);
while (!queue.isEmpty()){
System.out.print(queue.poll()+",");
}
System.out.println();
Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
};
PriorityQueue<Integer> q2 = new PriorityQueue<>(4,cmp);
q2.add(6);
q2.add(1);
q2.add(4);
q2.add(8);
while (!q2.isEmpty()){
System.out.print(q2.poll()+",");
}
输出结果:
1,2,3,4,
8,6,4,1,
由此可以看出,默认情况下PriorityQueue采用自然排序。指定Comparator的情况下,PriorityQueue采用指定的排序方式。
Dueue接口与ArrayDeque实现类
Dueue接口
Deque接口是Queue接口的子接口,它代表一个双端队列。LinkedList也实现了Deque接口,所以也可以被当作双端队列使用。
ArrayDeque
顾名思义,就是用数组实现的Deque;既然是底层是数组那肯定也可以指定其capacity,也可以不指定,默认长度是16,然后根据添加的元素的个数,动态扩展。ArrayDeque由于是两端队列,所以其顺序是按照元素插入数组中对应位置产生的(下面会具体说明)。