Queue与Deque的区别

前言

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

正文

概念

从上图看出，Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

下面来看一下官方文档的解释。

A linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”. Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端结束的队列，双端队列，可以在首尾插入或删除元素。而Queue的解释中，Queue就是简单的FIFO队列。

所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。

而在使用上，又有什么差别呢？

使用

从上图我们可以得知，Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。

PriorityQueue

我觉得重点就在圈定的两个单词：无边界的，优先级的堆。然后再看看源码

在第一张图片的源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。

在第二张第三张图片中，可以看到插入元素的时候是需要经过compareTo的处理，那么最常用就是一些范围极值的输出，类似于堆排序的用法。

下面演示一下正反序输出三个元素的使用

private static void negativePrint(int[] nums) {
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int temp:nums){
            queue.add(temp);
        }
        System.out.println();
        System.out.print("倒序输出：");
        for(int i=0;i<3;i++){
            System.out.print(queue.poll()+" ");
        }
    }

    private static void positivePrint(int[] nums){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int temp:nums){
            queue.add(temp);
        }
        System.out.print("正序输出：");
        for(int i=0;i<3;i++){
            System.out.print(queue.poll()+" ");
        }
    }

1 2	正序输出：1 2 3 倒序输出：9 8 8

这个在一些排行榜或者输入第N个最大/小元素会比较常用。

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.isEmpty());   //判断队列是否为空
        System.out.println(queue.peekFirst());   //获取队列首部元素
        System.out.println(queue.pollFirst());   //获取并移除栈顶元素
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
 }

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

栈为空:true
栈为空:false
12
12

栈为空:true

队列为空:true
队列为空:false
12
12
队列为空:true

小提示

在Deque中，获取并移除元素的方法有两个，分别是removeXxx以及peekXxx。

存在元素时，两者的处理都是一样的。但是当Deque内为空时，removeXxx会直接抛出NoSuchElementException，而peekXxx则会返回null。

所以无论在实际开发或者算法时，推荐使用peekXxx方法

其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列以及LinkedList作为栈使用会是更好的选择。

另外，我在leetcode看到有人采用Vector下的Stack，这个同步加锁粒度过大(对象级)，另外我觉得算法中没有线程同步的需要吧。

小结

PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。

ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。

LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

总结

在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。

而由于双端队列的定义，Deque可以作为栈或者队列使用，而Queue只能作为队列或者依赖于子类的实现作为堆使用。

本文首发于cartoon的博客
转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/queue%E4%B8%8Edeque%E7%9A%84%E5%8C%BA%E5%88%AB/