Queue与Deque的区别

一， 引言：

在研究java集合源码的时候，发现了一个很少用但是很有趣的点：Queue以及Deque；

平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道Queue的作用，于是就直接官方文档好了。

二，Queue和Deque：

1，Deque是Queue的子接口；

从源码中可以得知：Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

public interface Deque<E> extends Queue<E> {}

2，Queue——单端队列；Deque——双端队列；

从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端队列，就是可以在首和尾都进行插入或删除元素。

而Queue的解释中，Queue就是简单的FIFO（先进先出）队列。所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。​​​​​​​

3，Queue常用子类——PriorityQueue；Deque常用子类——LinkedList以及ArrayDeque；

Queue有一个直接子类PriorityQueue。

而Deque中直接子类有两个：LinkedList以及ArrayDeque。

三，PriorityQueue：

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

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

四，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作为栈使用，会是更好的选择。

五，小结：

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

六，Queue和Deque的方法区别：

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

而由于双端队列的定义，Deque可以作为栈或者队列使用；

而Queue只能作为队列或者依赖于子类的实现作为堆使用。

方法上的区别如下：