JAVA Queue
第一篇博客，希望以后每天坚持
目录：
1.Queue接口
2.Java中Queue接口方法
3.Queue的子类PriorityQueue分析
4.总结
1.Queue接口
数据结构中的队列，先进先出式的数据结构。
主要注意的时，Java中的Queue是比数据结构中理解的Queue更加灵活。这表现在：
a.数据结构中的Queue是按时间顺序的先进先出，即你先插入的元素总是先出的。但是JAVA中的Queue确实运行你实现自己的策略，确定什么元素是“优先”的，如它的value值模拟“它的达到时间”，value越大，则优先级越高，越排在前面。当前你也可以按照自然的常理的时间顺序。（注意：你确定了你的策略之后，就不可变了，不能一会说按照时间顺序，一会按照value倒叙）
b.比通常的queue多了一个方法peek，你可以查看却不删除，根据当前的值，觉得你的操作。
2.Java中Queue接口方法
六个：
a:add(E e):添加一个元素
b:remove():删除一个元素
c:offer(E e):添加一个元素
d:poll(E e):删除一个元素
f: element() ：查看最上一个元素
h:peek():查看最上一个元素
上面六个函数总体上分为两类：安全的会进行容量检查的（add,remove,element）,如果队列没有值，则取元素会抛出IlleaglStatementException异常。不安全的不进行容量控制的(offer,poll,peek )。
既然是这样，为什么要有两条语句相同的一个安全、不个不安全的呢？只提供一套安全的不久可以了么？
我的理解：有时候需要通过抛出异常来判断是容器中包涵null还是没有值。Queue通常不允许插入null值元素。但是有的实现却是允许插入null值的，如LinkedList.
另外，这里的分类不是严格的，并不是说所有queue的子类的add方法都会进行容量检查，然后抛出异常。这是要看容器的特性的，如Priorityqueue是*的，add方法是直接的调用的offer方法。
3.Queue的子类PriorityQueue分析
3.1主要的方法成员
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
private int size = 0;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
private final Comparator<? super E> comparator;
/**
* The number of times this priority queue has been
* <i>structurally modified</i>. See AbstractList for gory details.
*/
transient int modCount = 0; // non-private to simplify nested class access
说明：PriorityQueue使用数组存储数据，基于数组形式的小根堆来做的。
3.2主要方法分析
a.构造方法
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
//数组的大小，直接看用户指定的initialCapacity，没有指定就是默认值11
//区别于Map类型的，是2^n次方。
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
注意：PriorityQueue是在构造函数调用阶段就已经申请了底层数组，而有的容器如HashMap是采用的懒加载机制，在实际的使用的时候，才会真正的去申请底层的数据空间（可能原因：hashmap是一个比较费空间的，因为来避免碰撞，获得较好的性能，则一般需要申请较大的底层数组，所以这种开销大的动作能推迟就推迟，而Queue在默认的没有指定初始容量的时候，只申请了长度为11的数组，开销较小。不过ArrayList在没有指定初始化容量的时候，也是采用的类似懒加载机制，指向一个长度为0的空数组，真正使用的时候才创建底层数组的空间，关于ArrayList其他的容器在以后再说）
b.添加元素
add方法：直接调用offer(E)方法
offer方法：
比较简单，因为priorityQueue是*队列，所以，添加元素不会抛出illegalStateException异常。如果当前数组已满，则会直接扩容。
过程：
a：安全性检查，不运行插入null元素
b：容量检查，如果容量不够，则扩容。扩容原则：如果当前基层数组较小，则扩容时，每次扩展一倍。之后每次扩容时，每次扩展0.5倍
c.如果当前队列为空，则直接插入到queue[0]位置，不需要调整。否则，将元素直接“放到”一个有效位置上，然后调整，不断上浮。
public boolean offer(E e)
{
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
上浮函数：不断的为新节点找位置，最后找到位置后，才赋值一次。
private void siftUpComparable(int k, E x)
{//父亲节点N,孩子节点2*N+1,2(N+1),则孩子节点编号k,父亲节点为(k - 1) >>> 1。0位置
//也是存数据的
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;
}
c.删除元素
remove函数：主要还是调用的poll函数，只是增加了异常处理（属于装饰器模式么？）
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
poll函数：
主要步骤：
a.容量检查
b.size标志减一，同时保存堆顶元素。
c.将最后一个元暂时提到堆顶位置，然后将堆顶元素调整，下移。
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;
}
private void siftDownComparable(int k, E x)
{
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half)
{
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
//C为左右孩子中最小的
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
//如果key小于孩子，则不用调整的，否则，需要下移，孩子上移
if (key.compareTo((E) c) <= 0)
break;
//孩子上移
queue[k] = c;
k = child;
}
queue[k] = key;
}
d.清除元素
特别要注意的地方：要清楚引用，不能只是将size置位0，这样的话会造成内存泄漏
public void clear() {
modCount++;
//清楚引用，不能只是将size置位0，这样的话会造成内存泄漏
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}
3.3其他
a.堆化函数
如果在构造PriorityQueue时，使用一个非priorityqueue集合初始queue，则策略是先将集合中的元素拷贝到底层的数组中，然后调用堆化函数调整元素顺序，使满足堆的性质。
过程：
调整非叶子点[0 , 2/size-1]之间的。
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
4.总结
a:priorityqueue是*队列
b:和其他集合容器一样，构造时，尽量大概估计容器大小
c:不允许null元素