Java集合中的Queue & Deque
Java集合中的Queue & Deque
Queue 是一端进另一端出的线性数据结构；而 Deque 是两端都可以进出的。
Queue
Java 中的 这个 Queue 接口稍微有点坑，一般来说队列的语义都是先进先出（FIFO）的。
但是这里有个例外，就是 PriorityQueue，也叫 heap，并不按照进去的时间顺序出来，而是按照规定的优先级出去，并且它的操作并不是 O(1) 的，时间复杂度的计算稍微有点复杂，我们之后单独开一篇来讲。
那 Queue 的方法官网[1]都总结好了，它有两组 API，基本功能是一样的，但是呢：
- 一组是会抛异常的；
- 另一组会返回一个特殊值。
功能 | 抛异常 | 返回值 |
|---|---|---|
增 | add(e) | offer(e) |
删 | remove() | poll() |
查 | element() | peek() |
为什么会抛异常呢？
- 比如队列空了，那 remove() 就会抛异常，但是 poll() 就返回 null；element() 就会抛异常，而 peek() 就返回 null 就好了。
那 add(e) 怎么会抛异常呢？
有些 Queue 它会有容量的限制，比如 BlockingQueue，那如果已经达到了它最大的容量且不会扩容的，就会抛异常；但如果 offer(e)，就会 return false.
那怎么选择呢？：
- 首先，要用就用同一组 API，前后要统一；
- 其次，根据需求。如果你需要它抛异常，那就是用抛异常的；不过做算法题时基本不用，所以选那组返回特殊值的就好了。
Deque
Deque 是两端都可以进出的，那自然是有针对 First 端的操作和对 Last 端的操作，那每端都有两组，一组抛异常，一组返回特殊值：
功能 | 抛异常 | 返回值 |
|---|---|---|
增 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
删 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
查 | getFirst()/ getLast() | peekFirst()/ peekLast() |
使用时同理，要用就用同一组。
Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度，准确来说是均摊时间复杂度。
实现类
它们的实现类有这三个：
所以说，
- 如果想实现「普通队列 - 先进先出」的语义，就使用 LinkedList 或者 ArrayDeque 来实现；
- 如果想实现「优先队列」的语义，就使用 PriorityQueue；
- 如果想实现「栈」的语义，就使用 ArrayDeque。
我们一个个来看。
在实现普通队列时，如何选择用 LinkedList 还是 ArrayDeque 呢？
总结来说就是推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。
那 ArrayDeque 和 LinkedList 的区别有哪些呢？
- ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
- ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
- ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
- ArrayDeque 在内存使用方面更高效。
所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！
那如果是一个很资深的面试官问你，什么情况下你要选择用 LinkedList 呢？
- 答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。
那最后一个问题，就是关于 Stack 了。
Stack
Stack 在语义上是 后进先出（LIFO） 的线性数据结构。
有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。
那在 Java 中是怎么实现栈的呢？
虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！
原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。
那么想实现 Stack 的语义，就用 ArrayDeque 吧：
Deque<Integer> stack = new ArrayDeque<>();参考：https://mp.weixin.qq.com/s/bVOSat47L0Hskfx9akAN6Q