Queue-PriorityQueue源码解析

Queue接口定义的方法：

添加元素接口：

add(E e) -> 往队列添加一个元素，如果队列已满抛出IllegalStateException异常。

offer(E e) -> 往队列添加一个元素，true成功，false失败，和add区别在与不会因为队列已满抛异常。

删除元素接口：

remove() -> 删除队列头元素并返回该元素，如果队列为空抛出NoSuchElementException异常。

E poll() -> 删除队列头元素并返回该元素，如果队列为空返回null（与remove不同）。

获取队列头元素接口：

E element() -> 返回队列头部元素（没有删除），如果队列为空抛出NoSuchElementException异常。

E peek() -> 返回队列头部元素（没有删除），如果队列为空返回null。

Queue常用的实现类

上图中列出的是Queue平时常用的实现类：

ArrayBlockingQueue -> 有边界的数组形式实现的阻塞队列。

LinkedBlockingQueue -> 有边界的链表形式实现的阻塞队列。

PriorityQueue -> 无边界的二叉堆形式实现的优先级队列。

DelayQueue -> 无边界的优先级形式实现的延迟队列。

PriorityQueue

PriorityQueue是基于二叉堆形式实现的无界队列。队列中元素类型必须是可比较的，构造函数如果没有传入Comparator默认是自然排序。

PriorityQueue结构

PriorityQueue继承了AbstractQueue，AbstractQueue实现Queue接口，即PriorityQueue拥有Queue的方法和特征。

Object[] queue：存放队列元素。

int DEFAULT_INITIAL_CAPACITY：默认的队列大小，默认值为11。

int size：PriorityQueue队列中元素个数。

int modCount：PriorityQueue队列修改次数。

Comparator<? super E> comparator：队列元素排序比较器。

int MAX_ARRAY_SIZE：队列最大值(Integer.MAX_VALUE - 8)，VM的保留了8字节的 header words。

PriorityQueue示例 package com.juc.queue; import java.util.PriorityQueue; /** * Created on 2020/5/10 23:29. * @author Griez */ public class PriorityQueueTest { public static final PriorityQueue<Integer> QUEUE = new PriorityQueue<>(); public static void main(String[] args) { for (int i = 10; i > 0 ; i--) { QUEUE.offer(i); } for (int i = 0; i < 10; i++) { System.out.println(QUEUE.poll()); } } }

创建一个存放Integer的PriorityQueue，采用默认的自然排序。并倒序的往PriorityQueue添加10-1。然后从PriorityQueue头部出队列并输出，输出结果是1-10升序。如果是让我们实现应该是入队时用插叙排序好并存放在queue数组中，但是这样实现往queue数组中添加和删除元素移动次数是不是最优的呢？接下来我们看一下Josh Bloch, Doug Lea是怎么样实现的。

PriorityQueue添加元素解析 java.util.PriorityQueue#offer public boolean offer(E e) { if (e == null) //《1》不能为空 throw new NullPointerException(); modCount++; // 《2》修改次数加1 int i = size; if (i >= queue.length) // 默认11 grow(i + 1); // 《3》数组扩容 size = i + 1; if (i == 0) // 《4》直接把e赋值给0下标元素（顶部元素） queue[0] = e; else siftUp(i, e); // 《5》筛选顶部元素 return true; }

《1》添加的元素不能为空，即PriorityQueue队列不可能存在null元素。

《2》修改次数加1。

《3》如果当前PriorityQueue元素数量大于等于数组容量需要对queue进行扩容操作。

《4》如果当前PriorityQueue为空，直接把e赋值给queue数组0下标（顶部元素）。

《5》通过二叉堆，筛选顶部元素。

java.util.PriorityQueue#grow private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% // 《1》根据现有的容量选择增长倍数 int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code // 《2》如果《1》计算出的容量比最大大，则以传入容量为准 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }

《1》根据现有的容量选择增长倍数，如果现在的容量小于64，则容量直接增长一倍再加2；否则增长50%。

《2》如果《1》计算出的容量比最大大，则以传入容量为准。

java.util.PriorityQueue#siftUp private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }