[LeetCode] 数据结构 - Deque

Deque

Deque (double ended queue)是一个interface，继承了Queue。这种双向队列即可以支持先进后出，也能支持先进先出的格式，相当于同时实现了Stack和LinkedList，是个双端队列。
public interface Deque<E> extends Queue<E>
它的实现方法有：
ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

ArrayDeque

在LeetCode里面我遇到的都是用ArrayDeque。

ArrayDeque 是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack。ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持为 null 的元素。

API

https://docs.oracle.com/javase/9/docs/api/java/util/Deque.html

头部是First，尾部是Last Deque和Queue对比 Deque和Stack对比

此外，
myDeque.peek() = myDeque.peekFirst()
myDeque.poll() = myDeque.pollFirst() // queue
myDeque.push() = myDeque.addFirst() // stack
myDeque.pop() = myDeque.removeFirst() // stack
myDeque.offer() = myDeque.offerLast() // queue

此外Deque还有的功能：
找到并删除指定元素：boolean removeFirstOccurrence | removeLastOccurrence(E e) // 删除队列中第一个出现的/最后一个出现的e，如果不存在或者空或其它返回false，成功删除（即改变了队列）则返回true

相关题目

99 Recover Binary Search Tree
https://leetcode.com/problems/recover-binary-search-tree/
Iteration的方法用到了Deque。
239 Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum/
其实这题不用Deque也能很好解决。

Deque取代Stack

Java不推荐使用Stack

Stack是JDK1.0的产物。它继承自 Vector，Vector 都不被推荐使用了，你说 Stack 还会被推荐吗？

当初 JDK1.0 在开发时，可能为了快速的推出一些基本的数据结构操作，所以推出了一些比较粗糙的类。比如，Vector、Stack、Hashtable等。这些类中的一些方法加上了 synchronized 关键字，容易给一些程序员在使用上造成一些误解！而且在之前的几个版本中，性能还不怎么好。

基于 Vector 实现的栈 Stack。底层实际上还是数组，所以还是存在需要扩容。Vector 是由数组实现的集合类，它包含了大量集合处理的方法。而 Stack 之所以继承 Vector，是为了复用 Vector 中的方法，来实现进栈（push）、出栈(pop)等操作。这里就是 Stack 设计不好的地方，既然只是为了实现栈，不用链表来单独实现，而是为了复用简单的方法而迫使它继承 Vector，Stack 和 Vector 本来是毫无关系的。这使得 Stack 在基于数组实现上效率受影响，另外因为继承 Vector 类，Stack 可以复用 Vector 大量方法，这使得 Stack 在设计上不严谨。

---

Reference:
https://www.cnblogs.com/cosmos-wong/p/11845934.html