集合_Queue&Deque&LinkedList&ArrayDeque&PriorityQueue详解

1、 Queue与Deque的区别

1）引言：
在研究java集合源码的时候，发现了一个很少用但是很有趣的点：Queue以及Deque；
平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道Queue的作用，于是就直接官方文档好了。

2）Queue和Deque：
Deque是Queue的子接口；
从源码中可以得知：Queue以及Deque都是继承于Collection，Deque是Queue的子接口。
public interface Deque extends Queue {}

Queue——单端队列；Deque——双端队列；
从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端队列，就是可以在首和尾都进行插入或删除元素。
而Queue的解释中，Queue就是简单的FIFO（先进先出）队列。所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。

Queue常用子类——PriorityQueue；Deque常用子类——LinkedList以及ArrayDeque；
Queue有一个直接子类PriorityQueue。
而Deque中直接子类有两个：LinkedList以及ArrayDeque。

1. PriorityQueue：
   我觉得重点就在圈定的两个单词：无边界的，优先级的堆。
   从源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。

2 PriorityQueue源码解读

top k算法的经典实现是大顶堆和小顶堆，而在JAVA中可以用PriorityQueue实现小顶堆，话不多说，直接上代码

public static List<Integer> getTopMapNum(int[] arr, int k) {
    Queue<Integer> priorityQueue = new PriorityQueue();
    List<Integer> topKList = new ArrayList<>();
    if (arr == null || k > arr.length || k <= 0) {
        return topKList;
    }
    for (int i : arr) {
        if (priorityQueue.size() < k) {
            priorityQueue.add(i);
        } else {
            if (priorityQueue.peek() < i) {
                priorityQueue.poll();
                priorityQueue.add(i);
            }
        }
    }
    while (k-- > 0) {
        topKList.add(priorityQueue.poll());
    }
    return topKList;
}

作为程序员，只知道简单的如何实现是不够的，最好能够深入源码，下面我们就来聊一聊PriorityQueue
PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。

Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

leftNo = parentNo2+1
rightNo = parentNo2+2
parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

方法解析（JDK 1.8）
add()和offer
add()方法内部是调用的offer()，所以两个方法没啥区别，都是向队列中插入元素

新加入的元素可能会破坏小顶堆的性质，所以需要进行调整

/**
 * 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
/**
 * The number of elements in the priority queue.
 *队列中元素的个数
 */
private int size = 0;
public boolean add(E e) {
    //add方法内部调用的offer方法
    return offer(e);
}
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;
}
/**
 * Increases the capacity of the array.
 *队列扩容
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    //原始队列容量
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    //如果原始队列容量没有超过64，则翻倍扩容，否则扩容50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    //如果扩容后的队列大小超过了最大队列大小，则需要进行特殊处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
/**
 * 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
 * 元素添加
 */
private void siftUp(int k, E x) {
    //使用构造方法传进来的比较器
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);//使用默认的比较器
}
private void siftUpComparable(int k, E x) {
    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;
}

poll 类似，poll 从上往下进行，然后将左右进行比较，将小的一个和 父节点交换

3 LinkedList以及ArrayDeque：

从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。
而我们还能看到，ArrayDeque作为队列时的效率比LinkedList要高。
而在栈的使用场景下，无疑具有尾结点，不需判空的LinkedList更为高效。
演示ArrayDeque作为队列以及LinkedList作为栈的使用：

private static void usingAsQueue() {
        Deque<Integer> queue=new ArrayDeque<>();
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
        queue.addLast(12);   //添加元素
        System.out.println(queue.peekFirst());   //获取队列首部元素
        System.out.println(queue.pollFirst());   //获取并移除栈顶元素
 }
private static void usingAsStack() {
        //作为栈使用
        Deque<Integer> stack=new LinkedList<>();
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        stack.addFirst(12);//添加元素
        System.out.println(stack.peekFirst());   //获取栈顶元素
        System.out.println(stack.pollFirst());   //获取并移除栈顶元素
    }

小提示：
在Deque中，获取并移除元素的方法有两个，分别是removeXxx以及peekXxx。
存在元素时，两者的处理都是一样的。
但是当Deque内为空时，removeXxx会直接抛出NoSuchElementException，
而peekXxx则会返回null。
所以无论在实际开发或者算法时，推荐使用peekXxx方法。
其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列，以及LinkedList作为栈使用，会是更好的选择。

注意：
ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack。ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持为 null 的元素。
之后，再说为什么建议使用ArrayDeque而不是LinkedList:
链表比数组花费更多空间
链表的随机访问性质比数组差（虽然这个对栈来说问题不大）
链表的每次插入和删除都涉及到一个节点对象的创建和弃用，非常低效和浪费空间，而动态数组几乎是0花费的(数组充满时重新拷贝除外)
链表是非连续的，访问时候不能充分利用cpu cache
个人觉得第三点最重要

所以无论是栈还是队列，JDK都是建议使用ArrayDeque而不是LinkedList实现，ArrayDeque比较复杂的一点就是需要指定初始大小，当然你不指定也行。但是它的效率确实是比LinkedList高的

小结：
PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
ArrayDeque可以作为栈或队列使用，但是栈的效率不如LinkedList高，通常作为队列使用。
LinkedList可以作为栈或队列使用，但是队列的效率不如ArrayQueue高，通常作为栈使用。

Queue和Deque的方法区别：
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用；
而Queue只能作为队列或者依赖于子类的实现作为堆使用。
方法上的区别如下：

add offer add 底层调用offer 无区别
remove 无元素 抛出异常 poll 返回null 删除元素
peek element 不删除元素 ，element 无元素 抛出异常，peek 返回null

LinkedList与ArrayDeque在栈与队列中的使用
LinkedList
增加：
add(E e)：在链表后添加一个元素； 通用方法
addLast(E e)：在链表尾部添加一个元素； 特有方法
offer(E e)：在链表尾部插入一个元素
offerLast(E e)：JDK1.6版本之后，在尾部添加； 特有方法

特点：add 与 addLast 一个有返回值 boolean，一个无
offer 与 add 与 offerLast 一样

addFirst(E e)：在链表头部插入一个元素； 特有方法
offerFirst(E e)：JDK1.6版本之后，在头部添加； 特有方法

特点：offerFirst 有返回值 addFirst无
add(int index, E element)：在指定位置插入一个元素。

删除：
remove() ：移除链表中第一个元素; 通用方法
removeFirst() 移除第一个元素
pollFirst()：删除头； 特有方法
==pop()：和removeFirst方法一致，删除头。 ==
==poll()：查询并移除第一个元素 特有方法 ==

特点：remove 抛异常，poll 返回null pop 与 removeFirst remove一致
remove(E e)：移除指定元素； 通用方法
removeFirst(E e)：删除头，获取元素并删除； 特有方法
removeLast(E e)：删除尾； 特有方法

pollLast()：删除尾； 特有方法
查：
poll()：查询并移除第一个元素 特有方法
pollFirst()：查询并删除头； 特有方法
getFirst()：获取第一个元素； 特有方法
peek()：获取第一个元素，但是不移除； 特有方法
peekFirst()：获取第一个元素，但是不移除；

特点：poll 弹出数据，无数据返回null ：getFirst 无数据 抛出异常, peek 返回数据，无数据返回null
getLast()：获取最后一个元素； 特有方法
peekLast()：获取最后一个元素，但是不移除；
pollLast()：删除尾； 特有方法
get(int index)：按照下标获取元素； 通用方法

ArrayDeque
特点：
ArrayDeque实现了Deque接口。可当作栈来用，效率高于stack。也可当作队列来用，效率高于LinkedList。
底层用可变数组实现，无容量限制。
ArrayDeque是不安全的。

增加:
addFirst(E e)在数组前面添加元素
addLast(E e)在数组后面添加元素
offerFirst(E e)在数组前面添加元素，并返回是否添加成功
offerLast(E e)在数组后添加元素，并返回是否添加成功
push(E e)：与addFirst方法一致
offer(E e)：在链表尾部插入一个元素

删除：
removeFirst()删除第一个元素，并返回删除元素的值，如果为null，将抛出异常
removeLast()删除最后一个元素，并返回删除元素的值，如果为null,将抛出异常
pollFirst()删除第一个元素，并返回删除元素的值，如果为null，将返回null
pollLast()删除最后一个元素，并返回删除元素的值，如果为null,将返回null
==pop()：和removeFirst方法一致，删除头。 ==
poll()：查询并移除第一个元素 特有方法

查：
getFirst()获取第一个元素，如果为null，将抛出异常
getLast()获取最后一个元素，如果为null，将抛出异常
peek()：获取第一个元素，但是不移除； 特有方法

注意
add() 和 offer()的区别
在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false
remove方法和poll方法都是删除队列的头元素，remove方法，队列为空的情况下将抛异常，而poll方法将返回null；
element和peek方法都是返回队列的头元素，但是不删除头元素，区别在与element方法在队列为空的情况下，将抛异常，而peek方法将返回null。