@(JDK)[Queue]
JDK Queue
Queue:队列接口，对于数据的存取，提供了两种方式，一种失败会抛出异常，另一种则返回null或者false。
抛出异常的接口：add，remove，element，分别对应：offer，poll，peek。
整体类结构
PriorityQueue
优先级队列，采用堆来实现，在容量不足，添加元素的时候会自动扩展，对于元素的比较，则实现了两种方式，一种是通过Comparator比较器，另一种是要求对象实现Comparable接口。即如果没有提供Comparator，就会进行强转，并且如果没有实现比较接口，就会导致转换异常。
堆元素上移的方法如下：
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
对于扩容策略，则是采用了在小于一定阈值(64)的时候，快速增长（两倍的速度），而后超过该阈值，则变为每次增加原有的50%。
newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1))
对于index等这些方法，由于堆的性质，还是需要进行线性遍历，耗费O(n)的时间。（注：这个时候的比较则是采用equals方法了）
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
PriorityQueue的迭代器实现
该迭代器的实现和List等的实现有点不一样，是因为堆的问题。当在正常遍历的时候，按数组下标依次访问是没有什么问题的。但是，如果删除了一个元素，如果不是最后一个，那么堆就需要进行调整了，会把最后一个元素拿到当前删除的位置，并进行shitDown或者shitUp，如果是shitDown，那还好说，照常就好了，但是如果是shitUp，那么就会将没有遍历到的元素放到前面，这个时候就需要特殊处理了，JDK采用一个队列来维持放到前面的元素，并在最后进行访问。
注:
在数据结构的书籍上，删除特定位置的元素，大都是通过decreaseKey后再进行deleteMin那样子实现的，这里就会进行两次的操作，一次是shitUp，一次是将最后一个元素拿到根节点并进行shitDown，而且还要在遍历的时候额外判断最后一个元素是否跳到前面去了，防止遍历的时候进行删除，后导致没有遍历到。
这里采用的是：将最后一个元素拿到当前位置，并进行shitDown，如果成功了，说明那个保持了堆的性质，并且迭代器也不用担心该元素跑到前面去了，如果shitDown后还是停留在原有的位置，那么就要进行shitUp了，因为该元素可能比父节点小，并且shitUp成功后，需要返回该元素，因为迭代器需要记录跳到前面的元素，防止没有遍历到。（该算法对删除特定位置优化了，一来提高效率，二来迭代器实现也简单了）
private final class Itr implements Iterator<E> {
private int cursor = 0;
private int lastRet = -1;
// 存放处理上浮后的元素，并在最后进行遍历
private ArrayDeque<E> forgetMeNot = null;
// 保存最后一次通过forgetMeNot返回的元素，用于remove操作
private E lastRetElt = null;
private int expectedModCount = modCount;
public boolean hasNext() {
// 遍历结束的条件除了当前大小，还需要加上上浮后的元素判断
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
public E next() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (cursor < size)
// 先照常遍历
return (E) queue[lastRet = cursor++];
if (forgetMeNot != null) {
// 最后处理上浮的元素
// 这里将lastRet置为-1，也是方便下面进行remove操作时的判断
lastRet = -1;
// 保存下来，为remove预留
lastRetElt = forgetMeNot.poll();
if (lastRetElt != null)
return lastRetElt;
}
throw new NoSuchElementException();
}
public void remove() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (lastRet != -1) {
E moved = PriorityQueue.this.removeAt(lastRet);
lastRet = -1;
if (moved == null)
// 下沉，无需额外处理
cursor--;
else {
// 上浮，需要加到队列中
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) {
// 这里就用到了lastRetElt，删除此次遍历的元素
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
expectedModCount = modCount;
}
}
删除特定位置元素的代码如下：
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
// 这里会将最后一个元素放到当前位置，并进行下沉操作
siftDown(i, moved);
if (queue[i] == moved) {
// 如果当前位置没有改变，则进行一次上浮
siftUp(i, moved);
if (queue[i] != moved)
// 上浮成功，返回上浮后的元素，这是为了在遍历的时候，处理上浮后没有遍历到的元素
return moved;
}
}
return null;
}
ArrayDeque
双端队列，根据JDK里面说明的，如果用作栈，会比Stack快（ArrayDeque非同步），如果作为Queue，则会比LinkedList快，这里个人认为主要是因为LinkedList的节点创建耗费。
其容量会动态扩展，在不足的时候，以2次幂的速度增长，具体方法见allocateElements和doubleCapacity方法，其中doubleCapacity方法用于初次创建的时候，后续直接使用doubleCapacity。
方法：allocateElements
该方法用于保证在数组容量不足的进行重新分配
private static final int MIN_INITIAL_CAPACITY = 8;
// 个人观点：这里保证2次幂，后续也以2次幂的方式增长，后续运算时可以不使用取模，使用&替代，提高运算速度，并且不需要考虑负数的情况，例如：addFirst中，使用了(head-1) & (elements.length-1) <=> (head-1) % elements.length，当head为0时，head-1后-1的补码 & elements.length，则回滚到elements.length-1
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// 如果小于MIN_INITIAL_CAPACITY，则以最小值分配空间
if (numElements >= initialCapacity) {
// 查找大于numElements的最优2次幂，即大于numElements 2次幂中最小的数
initialCapacity = numElements;
// 下面算法等价于 initialCapacity |= (initialCapacity >>> 1) | (initialCapacity >>> 2) | (initialCapacity >>> 3) ... 最终会使得numElements的最高位1以下的二进制位变为1，例如：9的最高位为1000，则会变为->1111
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
// 经过上述变换后，加1，则为2的次幂
initialCapacity++;
// 如果溢出了，即2^31，则需要回退
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = (E[]) new Object[initialCapacity];
}
参考：
最优2次幂 http://stackoverflow.com/questions/5528205/implementation-of-arraydeque-allocateelements-bitwise-operations
取模运算效率 http://www.cnblogs.com/codezhang/archive/2009/06/19/1506532.html
其中有句话：Integer division and modulo operation are particularly costly and should be avoided ...
方法：doubleCapacity
// 只有当队列满的时候才会增扩容，以2次幂速度增长
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
// 右边元素个数
int r = n - p;
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
// 右边元素
System.arraycopy(elements, p, a, 0, r);
// 左边元素
System.arraycopy(elements, 0, a, r, p);
elements = (E[])a;
head = 0;
tail = n;
}
方法：addFirst/addLast/removeFirst等
// 这些运算都采用了&运算替代了%
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
// 队列满后再扩容
doubleCapacity();
}
public E pollFirst() {
int h = head;
E result = elements[h]; // Element is null if deque empty
if (result == null)
return null;
// 这里设置为空，是防止内存泄漏
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
在队列中，主要分为两类方法，一类的返回空结果，另一类是直接抛出异常
|抛异常方法|返回空方法|
|:-|
|E removeFirst()|E pollFirst()|
|E removeLast()|E pollLast()|
|E getFirst()|E peekFirst()|
|E getLast()|E peekLast()|
|E remove()|E poll()|
|E element()|E peek()|
方法 removeFirstOccurrence/delete
// 删除首次出现o的元素
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
E x;
// 从头开始遍历
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
// 删除指定位置的元素
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
delete方法中，front < back有两种情况：
1.h <= i
2.h > i
private boolean delete(int i) {
checkInvariants();
final E[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
// 位于i位置元素前面的元素个数
final int front = (i - h) & mask;
// 位于i位置元素后面的元素个数
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
// 优化：减少元素的移动，即只移动较少元素的一端
if (front < back) {
// 这里删除有两种情况，1.待删除元素循环到前面了，即 i < h，另一种情况是在head后面
if (h <= i) {
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
// 先将前端的front后半部分向后移动，空出[0]位置
System.arraycopy(elements, 0, elements, 1, i);
// 将最后一个元素放到开头
elements[0] = elements[mask];
// 移动后端的front前半部分向后移动
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
// 同理
if (i < t) { // Copy the null tail as well
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
}