Java-集合第四篇Queue集合

1、什么是Queue

模拟队列数据结构，先进先出（FIFO），从队尾加元素，从队头取元素。

2、Queue接口中定义了如下几个方法：

1》void add(Object o)：将指定元素加入此队列的尾部。

2》Object element()：获取队列头部的元素，但是不删除该元素。

3》boolean offer(Object e)：将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比add(Object e)方法更好。

4》Object peek()：获取队列头部的元素，但是不删除该元素。如果此队列为空，则返回null。

5》Object poll()：获取队列头部的元素，并删除该元素。如果此队列为空，则返回null。

6》Object remove()：获取队列头部的元素，并删除该元素。

3、Queue有一个PriorityQueue实现类，还有一个Deque接口。

Deque代表“双端队列”，双端队列可以同时往两头添加、删除元素，因为Deque既可以当队列使用，也可以当栈使用。Deque提供了ArrayDeque和LinkedList两个实现类。

4、PriorityQueue实现类

该实现类并不遵守先进先出的原则。它保存元素不是按照队列添加的顺序，而是按照队列元素的大小进行重新排序。因此使用peek()或者poll()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。

PriorityQueue不允许插入null元素，他还需要对队列排序：

1》自然排序：集合中的元素必须实现Comparable接口，而且是同一个类的多个实例，否则可能导致强制类型转换异常。

2》定制排序：创建PriorityQueue队列时，传入一个Comparator对象，该对象负责对队列中的所有元素进行排序。定制排序不要求队列元素实现Comparable接口。

5、Deque接口与ArrayDeque实现类

Deque是Queue的子接口，它代表一个双端队列一些操纵双端队列的方法：

Deque提供了一个典型的实现类ArrayDeque，基于数组实现的双端队列，创建Deque时同样可以指定一个numElements参数，该参数用于指定Object[]数组的长度，如果没有指定则默认是16。

6、LinkedList实现类

LinkedList类是List接口和Deque接口的实现类，由于它是List接口的实现类，可以根据索引随机访问集合中的元素。又是Deque接口的实现类，所以又可以当成双端队列使用。

LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色。

7、各种线性表性能分析

List是一个线性表接口，ArrayList、LinkedList又是线性表的两种典型实现：基于数组的线性表和基于链的线性表。

ArrayList是基于数组实现的，存储元素以一片连续的区域保存数组的所有元素，所以数组的随机访问性能最好。LineedList内部以链表作为底层实现，在执行插入、删除操作是有较好的性能。

关于List集合的使用的几点建议：

1》遍历List集合元素，ArrayList、Vector集合采用随机访问方法（get）来遍历集合元素性能更好；对于LinkedList集合，采用迭代器（Iterator）来遍历集合元素更好。

2》需要经常执行插入、删除改变包含大量数据的List集合的大小，可考虑LinkedList集合。ArrayList、Vector集合可能需要经常重新分配内部数组的大小，性能会受影响。

3》有多个线程需要访问List集合中的元素，开发者可以考虑使用Collections将集合包装成线程安全的集合。

巴特西