欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

集合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由于是两端队列,所以其顺序是按照元素插入数组中对应位置产生的(下面会具体说明)。

 原文链接

相关标签: Queue