【java提高】---queue集合

java

什么是Queue集合?

答:Queue用于模拟队列这种数据结构。队列通常是指“先进先出(FIFO)”的容器。队列的头部保存在队列中存放时间最长的元素,尾部保存存放时间最短的元素。

新元素插入到队列的尾部,取出元素会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。

 一、认识queue

1、Queue 方法介绍

     从上面来看,Queue(队列)接口继承自Collection,用来表示内部元素具有先后顺序的集合。除了基本的集合操作外,队列还提供了其他插入、删除和检查操作。Queue接口定义如下:

public interface Queue<E> extends Collection<E> {

E element();

boolean offer(E e);

E peek();

E poll();

E remove();

}

       每一个队列相关方法都提供了两种形式:一种如果操作失败抛出异常,另一种如果操作失败返回一个特殊值(null或false)。

 Queue接口结构如下图所示:

操作

抛出异常

返回特殊值

插入

add(e)

offer(e)

移除

remove()

poll()

检查

element()

peek()

(1).add(E), offer(E) 在尾部添加:

       他们的共同之处是建议实现类禁止添加 null 元素,否则会报空指针 NullPointerException;

不同之处在于 add() 方法在添加失败(比如队列已满)时会报 一些运行时错误 错;而 offer() 方法即使在添加失败时也不会奔溃,只会返回 false。

(2)remove(), poll() 删除并返回头部

       当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃,只会返回 null。

(3)element(), peek() 获取但不删除

      当队列为空时 element() 抛出异常;peek() 不会奔溃,只会返回 null。

2、其它

(1)虽然 LinkedList 没有禁止添加 null,但是一般情况下 Queue 的实现类都不允许添加 null 元素,因为 poll(), peek() 方法在异常的时候会返回 null,你添加了 null 以后,当获取时不好分辨究竟是否正确返回。

(2)Queue 一般都是 FIFO 的,但是也有例外,比如优先队列 priority queue(它的顺序是根据自然排序或者自定义 comparator 的);再比如 LIFO 的队列(跟栈一样,后来进去的先出去)。

(3)不论进入、出去的先后顺序是怎样的,使用 remove(),poll() 方法操作的都是 头部 的元素;而插入的位置则不一定是在队尾了,不同的 queue 会有不同的插入逻辑。

 二、PriorityQueue实现类

        PriorityQueue是一个比较标准的队列实现类。PriorityQueue保存队列元素的顺序并不是按加入队列的顺序,而是按队列元素的大小进行重新排列。因此当调用peek()方法或者poll()方法取出队

列中的元素时,并不是取出最先进入队列的元素,而是取出队列中最小的元素。

1、PriorityQueue的排序方式

  PriorityQueue中的元素可以默认自然排序(也就是数字默认是小的在队列头,字符串则按字典序排列)或者通过提供的Comparator(比较器)在队列实例化时指定的排序方式。

(1)小案例

PriorityQueue<Integer> qi = new PriorityQueue<Integer>();

qi.offer(5);

qi.offer(2);

qi.offer(1);

qi.offer(10);

qi.offer(3);

while (!qi.isEmpty()){

System.out.print(qi.poll() + ",");

}

System.out.println();

//采用降序排列的方式,越小的越排在队尾

Comparator<Integer> cmp = new Comparator<Integer>() {

public int compare(Integer e1, Integer e2) {

return e2 - e1;

}

};

//这里是初始容量3,当我们超过3个会自动扩容,所以说它是个无边界容器

PriorityQueue<Integer> q2 = new PriorityQueue<Integer>(3,cmp);

q2.offer(2);

q2.offer(8);

q2.offer(9);

q2.offer(1);

while (!q2.isEmpty()){

System.out.print(q2.poll() + ",");

}

输出结果:

由此可以看出,默认情况下PriorityQueue采用自然排序。指定Comparator的情况下,PriorityQueue采用指定的排序方式。

注意:当PriorityQueue中没有指定Comparator时,加入PriorityQueue的元素必须实现了Comparable接口(即元素是可比较的),否则会导致 ClassCastException。

(比如你放入的是对象,那么必须指定Comparator,因为对象是无法比较的)

2、 PriorityQueue特性 

   (1)队列元素根据自然排序或者根据具体的比较器排序

   (2)实例化时若未指定初始容量,默认容量为11

   (3)自动扩容。如果容量小于64,两倍增长扩容;否则增长50%

   (4)无边界容器

   (5)不支持null元素

   (6)非线程安全

   (7)支持被序列化

   (8)入队出队的时间复杂度O(log(n))

有关Dueue接口与ArrayDeque实现类和LinkedList实现类以后用到了再写他们。

现在只要知道:

(1)Deque接口是Queue接口的子接口,它代表一个双端队列。

(2)LinkedList是List接口的实现类,因此它可以是一个集合,可以根据索引来随机访问集合中的元素。此外,它还是Duque接口的实现类,因此也可以作为一个双端队列,或者栈来使用。

想太多,做太少,中间的落差就是烦恼。想没有烦恼,要么别想,要么多做。少校【13】

以上是 【java提高】---queue集合 的全部内容, 来源链接: utcz.com/z/394046.html

回到顶部