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 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/