Java▲还不懂Java集合框架？看这一篇就够了( 四 ) 飞利浦·斯塔克

如果想实现「普通队列 - 先进先出」的语义，就使用 LinkedList 或者 ArrayDeque 来实现；

如果想实现「优先队列」的语义，就使用 PriorityQueue；

如果想实现「栈」的语义，就使用 ArrayDeque 。

我们一个个来看。
在实现普通队列时，如何选择用 LinkedList 还是 ArrayDeque 呢？
来看一下 StackOverflow[2
上的高票回答：
总结来说就是推荐使用 ArrayDeque ，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。
那 ArrayDeque 和 LinkedList 的区别有哪些呢？
还是在刚才的同一个问题下，这是我认为总结的最好的：

ArrayDeque 是一个可扩容的数组， LinkedList 是链表结构；
ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
ArrayDeque 在内存使用方面更高效。

所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！
那如果是一个很资深的面试官问你，什么情况下你要选择用 LinkedList 呢？

答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。
那最后一个问题，就是关于 Stack 了。
StackStack 在语义上是后进先出（LIFO）的线性数据结构。
有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。
那在 Java 中是怎么实现栈的呢？
虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！
原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。
那么想实现 Stack 的语义，就用 ArrayDeque 吧：
Deque<Integer> stack = new ArrayDeque<>();

Set最后一个 Set ，刚才已经说过了 Set 的特定是无序，不重复的。
就和数学里学的「集合」的概念一致。
Set 的常用实现类有三个：
HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。
LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。
TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。
那每个 Set 的底层实现其实就是对应的 Map：
数值放在 map 中的 key 上， value 上放了个 PRESENT ，是一个静态的 Object ，相当于 place holder ，每个 key 都指向这个 object 。
总结
【Java▲还不懂Java集合框架？看这一篇就够了】再回到开篇的这张图，有没有清楚了一些呢？