Queue

1	public interface Queue<E> extends Collection<E>

作为队列，不一定是FIFO，也可作为优先级队列、LIFO堆栈
没有定义阻塞队列方法，由BlockingQueue接口定义
通常不允许null元素，尽管一些实现如LinkedList不禁止，null会作为poll()的返回值
不实现equals和hashCode 方法，相同元素排序属性可能不同
失败操作：

	抛出异常	返回特定值（ `null`或`false` ）
Insert	`add(e)`	`offer(e)`
Remove	`remove()`	`poll()`
Examine	`element()`	`peek()`

Deque

1	public interface Deque<E> extends Queue<E>

双端队列
不支持索引访问
定义了访问deque两端元素的方法。提供了插入，移除和检查元素的方法，总结如下：

	First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Remove	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Examine	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

作为FIFO队列，和queue方法对比：

Queue Method	Equivalent Deque Method
`add(e)`	`addLast(e)`
`offer(e)`	`offerLast(e)`
`remove()`	`removeFirst()`
`poll()`	`pollFirst()`
`element()`	`getFirst()`
`peek()`	`peekFirst()`

作为LIFO，和Stack方法对比

Stack Method	Equivalent Deque Method
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

ArrayDeque

1 2	public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

特点

可调整大小的数组实现，非线程安全
不允许空元素
作为栈，速度比Stack快；作为队列，速度比LinkedList快
迭代器是fast-fail的
头指针head从内部数组的末尾开始，尾指针tail从0开始，在头部插入数据时，head减一，在尾部插入数据时，tail加一。当head==tail时说明数组的容量满足不了当前的情况，此时需要扩大容量为原来的二倍。
核心思想图：

核心思想图

源码分析

构造函数

//未指定容量时，默认为16
public ArrayDeque() {
    elements = new Object[16];
}
//指定初始容量
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
//指定初始值
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
//指定容量小于8时，返回8
//否则，返回initialCapacity=2^n，2^n越界时，则取2^30
//容量必须为2^n，否则指针移动	head &（elements.length - 1）将出现空位
private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

成员变量

//实际存放元素的数组
 transient Object[] elements; 
 //头指针
 transient int head;
 //尾指针
 transient int tail;
 //默认最小容量
 private static final int MIN_INITIAL_CAPACITY = 8;

核心方法

扩容

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of 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);	//复制head指针右边的数据
    System.arraycopy(elements, 0, a, r, p);	//复制head指针左边的数据
    elements = a;
    head = 0;	//重新初始化head,tail
    tail = n;
}

插入

//在头部插入数据
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;	//head指针从右向左移
    if (head == tail)
        doubleCapacity();
}

//在尾部插入数据
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)	//head指针从左向右移动
        doubleCapacity();
}

删除

//删除头部数据
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) 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;
}

//删除尾部数据
public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

遍历

public Iterator<E> iterator() {
    return new DeqIterator();
}

private class DeqIterator implements Iterator<E> {
    //游标，从head开始遍历
    private int cursor = head;
	//记录tail指针，判断是否结构改变
    private int fence = tail;
	//next()返回的索引
    private int lastRet = -1;

    public boolean hasNext() {
        return cursor != fence;
    }

    public E next() {
        if (cursor == fence)
            throw new NoSuchElementException();
        @SuppressWarnings("unchecked")
        E result = (E) elements[cursor];
        // This check doesn't catch all possible comodifications,
        // but does catch the ones that corrupt traversal
        if (tail != fence || result == null)
            throw new ConcurrentModificationException();
        lastRet = cursor;
        cursor = (cursor + 1) & (elements.length - 1);
        return result;
    }
}

PriorityQueue

1 2	public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

特点

无界队列，最小二叉堆的实现
不允许空元素
迭代器iterator() 不能保证以特定顺序遍历优先级队列，需要有序用Arrays.sort(pq.toArray())
入列、出列方法，offer()、add()、poll()、remove()的时间复杂度为O(log(n))；

检索方法，peek()、element()和size()方法的时间复杂度为O(1)；

remove(Object)和contains(Object)方法时间复杂度为线性，O(n)；
非线程安全，需要线程安全使用PriorityBlockingQueue
不指定容量，则 DEFAULT_INITIAL_CAPACITY = 11

源码分析

成员变量

//queue[n] 子节点为 queue[2*n+1] ， queue[2*(n+1)]
//queue[n] <= queue[2*n+1]， queue[n] <= queue[2*(n+1)]
transient Object[] queue;
//实际元素个数
private int size = 0;
//比较器，自然序为null
private final Comparator<? super E> comparator;
//fast-fail机制
transient int modCount = 0;

核心方法

构建堆操作

//构建堆
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--) //从数组 （size >>> 1) - 1 开始	
        siftDown(i, (E) queue[i]);
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);	//比较器的区别
    else
        siftDownComparable(k, x);
}

//从父节点向下调整堆
//是一个递归操作，一旦发生了父节点和子节点的交换，交换下去的新的子节点可能和该子节点的子节点不满足堆特性，需要调整
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位置赋值成较小值
        k = child;		//指定k为child，进入下一次循环。因为出现了交换，为了保证交换下去的节点也能满足小顶堆，需要继续调整堆
    }
    queue[k] = x;	//重新赋值k
}

offer()

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);	//进行扩容  Double size if small; else grow by 50%
    //newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
    size = i + 1;
    if (i == 0)
        queue[0] = e;	//首元素
    else
        siftUp(i, e);	//向上
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
//递归和父节点比较，最小元素上浮
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;
}

poll()

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;
}

iterator()

iterator只会将元素顺次输出一遍，元素第一位一定是最小元素，并且整体满足堆特性，但是整体并不是严格的从小到大排列。堆只是整体有序，并不是完全有序。

参考

https://blog.csdn.net/lh513828570/article/details/59560771

https://blog.csdn.net/a15501628162/article/details/52291258

https://blog.csdn.net/u011531425/article/details/80697705