JDK源码解析之Queue与其实现类PriorityQueue

前言：

    前文介绍了Stack这种数据结构类型，它符合后进先出（LIFO）的操作顺序。

    今天介绍与其相反操作顺序的一种数据结构，Queue（队列），它符合先进先出（FIFO）的操作顺序

 

    从网络上截一个图（如有侵权，请联系作者），简单表示下队列结构

    a1是最先进入队列的元素，现在排在队头，an是最后入队的元素，排在队尾

    执行出队操作的时候，最先进入队列的a1元素，最先出队

 

1.Queue

    java.util.Queue是一个接口，实现类有以下

/** 
 * @see java.util.Collection
 * @see LinkedList
 * @see PriorityQueue
 * @see java.util.concurrent.LinkedBlockingQueue
 * @see java.util.concurrent.BlockingQueue
 * @see java.util.concurrent.ArrayBlockingQueue
 * @see java.util.concurrent.LinkedBlockingQueue
 * @see java.util.concurrent.PriorityBlockingQueue
 * @since 1.5
 * @author Doug Lea
 * @param  the type of elements held in this collection
 */
public interface Queue extends Collection {

    之前在介绍LinkedList的时候，也能看到其实现了Deque接口，Deque继承了Queue，所以LinkedList实现了Queue接口。

    今天介绍下另一种Queue的实现类，PriorityQueue

 

2.PriorityQueue数据结构分析

    关于PriorityQueue的数据结构，就是堆。

    关于堆的内容笔者不再详述，可以参考：小灰漫画 什么是二叉堆

    笔者之前也有写过类似的博客：https://blog.csdn.net/qq_26323323/article/details/79708103 

 

    借用小灰漫画的图就是：

    二叉堆本质上是一个完全二叉树，它分为两个类型：最大堆和最小堆

    最大堆就是：每一个父节点的值，都大于等于它左右子节点的值，如下所示

    最小堆就是：每一个父节点的值，都小于等于它左右子节点的值，如下所示：

    依据这种堆结构，在堆顶的元素要么是最大的元素，要么是最小的元素，可以快速查找最大最小值

 

3.PriorityQueue结构分析

/**
The elements of the priority queue are ordered according to their
 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
*/
public class PriorityQueue extends AbstractQueue
    implements java.io.Serializable {
    
    // 默认容量是11
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    
    // 使用数组来存储元素
    transient Object[] queue;
    
    // 与ArrayList类似，也有一个size属性
    private int size = 0;
    
    // 如何实现优先级的队列呢，主要就是靠这个比较器
    private final Comparator