学习Queue看这篇就够了（源码分析）
Queue
Queue是Java集合框架中的一员，继承于Collection接口。
与List、Set相同的是，Queue也实现了一种数据结构，这就是队列。
队列是计算机中的一种数据结构，保存在其中的数据具有“先进先出（FIFO,First In First Out）”的特性。
在数据结构中，队列不支持从队伍的中间插入和离开，只能从头尾进行。
队列的两种形式
在Java中，队列分为2种形式，一种是单队列，一种是循环队列；
通常，都是使用数组来实现队列。假定数组的长度为6，也就是队列的长度为6；
-
单队列：
第一步，创建一个空数组，有两个变量，分别为front、rear，代表着头指针、尾指针；
第二步，向队列中插入数据；
第三步，移除队头中的数据；
第四步，再次向队列中插数据（此时rear指针指向了一个不存在的角标）；
此时，单队列发生了“假溢出”情况，尾指针指向了一个不存在的数组角标。
如果，要解决该情况的发生，有两种方式-----一，无限扩充数组大小；二，引入循环队列； -
循环队列：
当尾指针超过了数组角标大小，此时我们会判断队列的头部是否有剩余的空间，如果有就把尾指针指向队列的头部；
此时，循环队列就产生了。
其实，循环队列就是将单队列的首位进行相连，形成了一个圆圈，这样就不会发生角标越界的情况了。
在Java中，ArrayDeque、LinkedList、PriorityQueue等类实现了Queue接口，模拟了队列的数据结构。
其中，PriorityQueue是Queue直接子类实现，在原有基础上实现了元素的排序功能。
除此之外，Queue还有一个子接口–Deque，对Queue进行了扩展，定义了头尾操作功能，既可在队头添加(删除)元素，也可在队尾添加(删除)元素，俗称“双端队列”。
Queue源码
//接口Queue：
public interface Queue<E> extends Collection<E> {
//将指定元素插入到队列的尾部（队列满了话，会抛出异常）
boolean add(E e);
//将指定元素插入此队列的尾部(队列满了话，会返回false)
boolean offer(E e);
/返回取队列头部的元素，并删除该元素(如果队列为空，则抛出异常)
E remove();
//返回队列头部的元素，并删除该元素(如果队列为空，则返回null)
E poll();
//返回队列头部的元素,不删除该元素(如果队列为空，则抛出异常)
E element();
//返回队列头部的元素，不删除该元素(如果队列为空，则返回null)
E peek();
}
PriorityQueue源码
作为Queue的直接子类，PriorityQueue实现了Queue定义的方法。
不过，又与传统的队列不相。传统队列实现了“先进先出”数据模型，而PriorityQueue则实现了最小的元素优先出队，剩余元素依次按照大小顺序出队。
这就是所谓的“优先级队列”—元素按照任意的顺序插入，却总是按照顺序进行输出；每次从优先队列中取出来的元素要么是最大值，要么是最小值。接下来，我们来看下PriorityQueue具体是如何实现的：
PriorityQueue成员变量和构造方法：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
//默认初始化数组大小：
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//队列底层数据结构：数组
private transient Object[] queue;
//队列长度：
private int size = 0;
//实现元素排序的比较器：
private final Comparator<? super E> comparator;
//对queue的操作次数：
private transient int modCount = 0;
//默认构造函数：
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//可设置队列长度的构造函数：
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//可设置队列长度、元素比较器的构造函数：
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
PriorityQueue新增元素：
//队列添加元素，底层调用offer:插入失败抛出异常
public boolean add(E e) {
return offer(e);
}
//队列添加元素: 插入失败返回false
public boolean offer(E e) {
//不支持添加为null的元素：
if (e == null)
throw new NullPointerException();
//队列操作数+1：
modCount++;
int i = size;
//队列长度 >= 数组长度时，扩容：
if (i >= queue.length)
grow(i + 1);
//队列长度+1
size = i + 1;
//i==0，在数组角标为0处插入第一个元素：
if (i == 0)
queue[0] = e;
else
//插入的不是第一个元素：
siftUp(i, e);
return true;
}
//对队列底层数组扩容：
private void grow(int minCapacity) {
//现阶段数组长度：
int oldCapacity = queue.length;
//计算新数组的长度：
// 如果 现阶段数组长度<64，则扩容为现阶段长度的2倍+2；
// 如果 现阶段数组>=64，则扩容为现阶段长度的2倍+5；
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//数组复制：得到新数组
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
PriorityQueue获取队列头部元素：
//返回队列头部的元素，不删除该元素(如果队列为空，则返回null)
public E peek() {
if (size == 0)
return null;
return (E) queue[0];
}
//返回队列头部的元素，并删除该元素(如果队列为空，则返回null)
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
PriorityQueue中核心方法：使用了比较器进行元素比较，当插入或者删除的元素后，对PriorityQueue中树的结构进行调整；
private void siftUp(int k, E x) {
//元素比较器不为null：
if (comparator != null)
siftUpUsingComparator(k, x);
else
//元素比较器为null：
siftUpComparable(k, x);
}
//进行堆结构的siftUp运算：使用元素比较器
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
//进行堆结构的siftUp运算：使用自定义元素比较器
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
private void siftDown(int k, E x) {
//元素比较器不为null:
if (comparator != null)
siftDownUsingComparator(k, x);
else
//元素比较器为null：
siftDownComparable(k, x);
}
//进行堆结构的siftDown运算：使用元素比较器
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
//进行堆结构的siftDown运算：使用自定义元素比较器
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
//返回队列中的比较器：
public Comparator<? super E> comparator() {
return comparator;
}
}
从上面的源码中，可以看出，PriorityQueue是由“堆结构”来实现的队列。而“堆结构”又是通过数组形成的一颗完全二叉树。所以，我们在代码中可以看到PriorityQueue最底层数据结构就是数组。
经过上面的源码的分析，对PriorityQueue的总结如下：
1、PriorityQueue是线程不安全的队列；
2、PriorityQueue中不允许插入null元素；
3、PriorityQueue是一个用“堆结构”来实现的队列；
上一篇： 对于HashMap的一些疑问
下一篇： Grails如何引用开发中的插件