- Queue接口
- PriorityQueue类
- Deque与ArrayDeque
- LinkedList
- 各种线性表性能分析
Queue接口
Queue用来模拟队列这种数据结构，遵循先进先出原则（FIFO)。Queue接口中定义了以下通用方法，remove(), element()：获取队头元素，remove(), poll(), peek()：获取队头元素;offer(Object obj)：队尾插入，容量限制时比add()好; add(Object obj);
PriorityQueue
PriorityQueue中的元素会按照自然排序（由元素实现Comparable接口决定排序逻辑）或者定制排序（由集合的实现Comparable接口决定排序逻辑），而不是按照插入顺序排序（从这点来说已经违反队列定义）。元素的顺序在队列构造的时候，由构具体使用的哪个构造函数来决定。PriorityQueue不允许插入null元素。PriorityQueue内部是用数组保存数据的，源码如下，
//JDk源码 private transient Object queue[];
下面说说两种排序方式，
自然排序（元素实现Comparable决定排序逻辑）
元素必须实现了Comparator接口，而且所有元素都是同类型的，否则会抛出异常。下面是一个自然排序的例子，
package collect.Queue;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
class A implements Comparable{
private int age;
public A(int age) {
this.age = age;
}
@Override
public int compareTo(Object o) {
if (this == o) return 0;
A a = (A)o;
return this.age - a.age;
}
public String toString() {
return String.valueOf(this.age);
}
}
public class PriorityQueues {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue();
pq.add(new A(100));
pq.add(new A(50));
pq.add(new A(300));
pq.add(new A(150));
pq.add(new A(-200));
//System.out.println(pq);
Iterator it = pq.iterator();
while(it.hasNext()) {
System.out.println(pq.poll());
}
}
}
注意上面System.out.println(pq)的输出结果元素并不是按大小排序的， 整个执行结果如下，
[-200, 50, 300, 150, 100] ============================ -200 50 100 150 300
据李刚的《疯狂JAVA讲义》的解释说，是因为toString()的返回值的影响，说如果用poll()就能看到大小顺序（确实看到了）。但是网上有博客又说，是因为PriorityQueue底层数据结构的原因，底层是用一个“最小堆”来保持元素顺序的。 至于真正原因是什么，我也还需要进一步研究。
Deque是Queue的子接口，Queue是一个单端队列，而Deque接口是一个双端队列，因此定义了一些允许从两端操作队列的方法，
addFirst, addLast, descendingIterator,getFirst, getLast, offerFirst, offerLast, peekFirst, peekLast, pollFirst, pollLast, pop, poll, push(相当于addFirst),removeFirst, removeLast, removeOccurrenc(Object o)...
注意Deque接口里面同时定义了pop, poll , push等栈容器的方法，所以Deque也可以当作栈来使用，
ArrayDeque是Deque的一个典型的实现类，ArrayDeque是基于动态数组的集合，与ArrayList非常相似，不同点是ArrayList具有链表功能，支持随机访问（get)，而ArrayDeque具有队列和栈功能，下面的例子演示了ArrayDeque的两种典型用法，
package collection.queues;
import java.util.ArrayDeque;
public class ArrayDeques {
public static void main(String[] args) {
ArrayDeque ad = new ArrayDeque();
/*use ArrayDeque as a Queue*/
ad.offer("a");
ad.offer("b");
ad.offer("c");
ad.offer("d");
System.out.println(ad);
//the peek and poll method from Queue interface
System.out.println(ad.peek());
System.out.println(ad.poll());
System.out.println(ad);
/*use ArrayDeque as a Deque*/
//use push and pop method from Deque interface
ad.push("e");
ad.push("f");
System.out.println(ad);
System.out.println(ad.peek());
System.out.println(ad.pop());
System.out.println(ad);
}
}
输出结果，
[a, b, c, d] a a [b, c, d] [f, e, b, c, d] f f [e, b, c, d]
LinkedList
LinkedList同时实现了Deque, Queue, List三个接口，所有具有强大的功能。既能支持随机访问(get)，又能支持队列和栈的属性，下面是LinkedList集合了个种属性的用法，
package collection.queues;
import java.util.LinkedList;
public class LinkedLists {
public static void main(String[] args) {
LinkedList ll = new LinkedList();
//use as a Queue
ll.offer("a");
//use as a Stack(Deque), insert an element from head
ll.push("b");
//use as a Deque, insert an element from tail
ll.offerLast("c");
//use as a List, insert an element in index of 2
ll.add(2, "d");
//travel as a List
for (int i=0; i<ll.size(); i++) {
System.out.print(ll.get(i));
}
System.out.println("
--------------------");
//use as a Deque
System.out.println(ll.peekLast());
System.out.println(ll.pollLast());
System.out.println(ll.pollFirst());
System.out.println("--------------------");
System.out.println(ll);
}
}
执行结果，
badc -------------------- c c b -------------------- [a, d]
各种线性表性能分析
Java的List是一个线性表接口，ArrayList和LinkedList是List的两种典型实现，都提供随机访问功能（get）。只是ArrayList基于数组，随机访问更快；LinkedList基于链表，插入删除更快，且同时还实现了Queue和Deque两个接口，因此同时具有链表，双端队列，栈的三种功能。
Queue是一种队列，而Deque是双端队列，同时具有队列和栈的功能。
虽然ArrayList和LinkedList都支持随机访问，但由于底层数据结构不同，ArrayList的空间分布在连续的内存上，因此随机访问的性能比LinkedList好。所有以数组作为底层数据结构的集合的随机访问性能都更好。而LinkedList因为底层是链表结构，因此插入和删除的性能更好。但是总体上来说，ArrayList的性能要比LinkedList性能好，因此大部分情况下都推荐用ArrayList.
对于List的使用，有如下建议，
- 遍历ArrayList和Vector时，尽量用随机访问方法（get)，这样性能更好。 对于LinkedList，应该用迭代器(iterator)来遍历。
- LinkedList的应用场景：需要经常插入，删除包含大量数据的List集合。ArrayList和Vector需要经常重新分配空间，会影响性能。