队列Queue-02

1.什么是 Deque?

Deque，全称为"Double-Ended Queue"，是一种特殊的队列数据结构，它允许在两端进行元素的添加和删除操作。这种数据结构的特点是两端都是开放的，因此可以高效地在队列的前端和后端进行插入和删除操作。

Deque 通常通过数组或链表来实现。在基于数组的实现中，Deque 可以利用数组的两端进行元素的添加和删除，从而避免在中间插入或删除元素时需要移动其他元素的开销。而在基于链表的实现中，Deque 则利用链表的灵活性，在头部和尾部都维护一个指向当前队列的指针，以支持快速的插入和删除操作。

Deque 提供了许多有用的操作，如在队列前端添加元素（addFront）、在队列后端添加元素（addRear）、从队列前端删除元素（removeFront）和从队列后端删除元素（removeRear）。此外，Deque 还支持查看队列前端和后端的元素，以及判断队列是否为空等操作。

Deque 在计算机科学中有着广泛的应用，例如在某些算法中作为栈或队列的替代品，或者在需要双向队列特性的场景中使用。由于其灵活性和高效的操作性能，Deque 成为了一种非常有用的数据结构。

Queue 以及 Deque 都是继承于 Collection，Deque 是 Queue 的子接口。双端队列,可以在首尾插入或删除元素。

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

ArrayDeque 是无初始容量的双端队列，LinkedList 则是双向链表。而我们还能看到，ArrayDeque 作为队列时的效率比 LinkedList 要高，而在栈的使用场景下，无疑具有尾结点不需判空的 LinkedList 较高效。

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

2.双端可用 Deque 接口

Deque 概念： 支持两端元素插入和移除的线性集合。名称deque是双端队列的缩写，通常发音为deck。大多数实现 Deque 的类，对它们包含的元素的数量没有固定的限制的，支持有界和无界。

3.Deque 方法

4.Deque 和 Queue 比较

作为 FIFO 时等价于 Queue 的方法如下表所示：

比如 Queue 的 add 方法和 Deque 的 addLast 方法等价。

5.Deque 和 Stack 比较

• Deque 也可以用作 LIFO（后进先出）栈，这个接口优于传统的 Stack 类。当作为栈使用时，元素被 push 到 deque 队列的头，而 pop 也是从队列的头 pop 出来。
• Stack（栈）的方法正好等同于 Deque 的如下方法：

注意：peek 方法不论是作为栈还是队列，都是从队列的检测队列的头，返回最先加入的元素。比如第一次 put 100，第二次 put 200，则 peek 返回的是 100。

6.Deque 的实现与继承

哪些类实现了Deque接口:

• LinkedList 类
• ArrayDeque 类
• ConcurrentLinkedDeque 类
• LinkedBlockingDeque 类

哪些类继承了Deque接口:

• BlockingDeque 接口

public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {}