Queue完全解析

一 概览

image.png

由上图可知，Queue分成只扩展AbstractQueue的，实现BlockingQueue接口的，实现TransferQueue的，实现BlockingDeque的以及实现Deque接口的五类

二 PriorityQueue

• siftUp

    /**
     * Inserts item x at position k, maintaining heap invariant by
     * promoting x up the tree until it is greater than or equal to
     * its parent, or is the root.
     *
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *
     * @param k the position to fill
     * @param x the item to insert
     */
 @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {  
            int parent = (k - 1) >>> 1;    //不像siftDown那样需要考虑找左右 孩子中的最小节点，siftUp只需要比较key跟parent节点即可
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

• siftDown

    /**
     * Inserts item x at position k, maintaining heap invariant by
     * demoting x down the tree repeatedly until it is less than or
     * equal to its children or is a leaf.
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    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;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];    //如果右孩子更小，则将right赋给child，把queue[right]赋给c
            if (key.compareTo((E) c) <= 0) //如果目标节点值小于等于c，则break，否则，继续循环
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

• offer

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);    //扩容，与map和list的grow类似
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

offer(E e)方法的实现思路如下：
1）首先检查要添加的元素e是否为null，如果为null，则抛空指针异常，如果不为null，则进行2
2）判断数组是否已满，如果已满，则进行扩容，否则将元素加入到数组末尾即可。但是由于这个数组表示的是一个“二叉堆”，因此还需要进行相应的调整操作，使得这个数组在添加元素之后依然保持的是二叉堆的特性。

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

poll 方法的思想为：取出 queue[0] 元素，然后将 queue[size-1] 插入到 queue[0] , 然后向下沉来保持二叉堆的特性。