Queue 和 Deque 有什么区别？为什么用 ArrayDeque 而不是 Stack 和 LinkedList？

简化版

Queue 是单端队列（一端进、另一端出，FIFO）；Deque（双端队列）两端都能进出，既能当队列也能当栈。实现上首选 ArrayDeque：它基于循环数组，两端操作都是均摊 O(1)，没有链表的节点开销和缓存不友好问题。当栈用比 Stack 好——Stack 继承自 Vector，每个方法都加 synchronized，单线程白白付出锁开销，还暴露了一堆按下标访问的「非栈」方法；当队列用比 LinkedList 好——省去每个节点的指针内存，内存连续更快。

详细版

Queue（队列）：offer/poll/peek 三组方法，FIFO。核心实现有 LinkedList（链表）、ArrayDeque（数组）、PriorityQueue（堆，按优先级出队）、并发场景的 ArrayBlockingQueue/LinkedBlockingQueue。

Deque（双端队列）：继承 Queue，两端都能操作，一套方法覆盖队列和栈：

操作	队首	队尾
加入	`addFirst/offerFirst`	`addLast/offerLast`
移除	`removeFirst/pollFirst`	`removeLast/pollLast`
查看	`getFirst/peekFirst`	`getLast/peekLast`

当栈用：push（= addFirst）、pop（= removeFirst）、peek；
当队列用：offer（= offerLast）、poll（= pollFirst）。

为什么 ArrayDeque 优于 Stack / LinkedList：

// 用 ArrayDeque 当栈（官方推荐，替代 Stack）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.pop();   // 2

// 用 ArrayDeque 当队列（替代 LinkedList 做 Queue）
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll();  // 1

⚠️ ArrayDeque 不允许存 null——它用 null 作为「空槽」的标记，存 null 会与「队列为空」的判断冲突，直接抛 NPE。需要存 null 才考虑 LinkedList。

完整版教学

一、先理清继承关系：Deque 是 Queue 的超集

集合框架里这几个接口的关系常被搞混，先建立地图：

Collection
   └── Queue（单端，FIFO）
         └── Deque（双端，两头都能进出）
               ├── ArrayDeque   （循环数组实现）
               └── LinkedList    （双向链表，也实现了 List）
Queue 的其他实现：
   ├── PriorityQueue        （二叉堆，按优先级出队，非 FIFO）
   └── BlockingQueue 家族    （并发阻塞队列）

关键认知：Deque 继承 Queue，所以 Deque 天然是队列；又因为两端可操作，它也能当栈。于是 Java 官方文档明确推荐：需要栈就用 Deque（ArrayDeque），不要再用老旧的 Stack 类。

二、ArrayDeque 的核心：循环数组 + 头尾指针

ArrayDeque 底层是一个数组加两个指针 head、tail。它不像普通数组那样「头部删除要搬移所有元素」，而是让 head/tail 在数组里循环移动（到末尾就绕回开头），两端增删只动指针，均摊 O(1)。

初始 (容量 8): [_ _ _ _ _ _ _ _]  head=tail=0
offerLast(A):  [A _ _ _ _ _ _ _]  head=0 tail=1
offerLast(B):  [A B _ _ _ _ _ _]  head=0 tail=2
offerFirst(Z): [A B _ _ _ _ _ Z]  head=7（绕回末尾！） tail=2
pollFirst():   取 index=head=7 的 Z，head=0

头部插入时 head 从 0「绕回」到 7，靠的是 (head - 1) & (length - 1)——容量始终是 2 的幂，所以能用位与实现循环下标（和 HashMap 同款技巧）。数组满了就扩容成 2 倍，把元素按逻辑顺序拷到新数组。正因为内存连续，CPU 缓存命中率高，实测比 LinkedList 快不少。

三、当栈用：为什么弃用 Stack

Stack 是 JDK 1.0 的遗留类，有两宗罪：

继承 Vector，方法全 synchronized：push/pop/peek 每次调用都要获取对象锁。单线程场景（栈的绝大多数用法）里，这个锁纯属浪费；多线程场景它的同步粒度也不对，复合操作仍不安全。
破坏了栈的封装：Stack 继承了 Vector 的 get(index)、add(index, e)、insertElementAt 等方法，用户可以从中间插入/访问元素——这根本不是栈该有的行为，破坏了「只能从栈顶操作」的抽象。

Stack 继承链：Stack → Vector → AbstractList   （能按下标乱插乱取，还带锁）
ArrayDeque：  只暴露两端操作，无锁，语义干净

ArrayDeque 当栈：无锁、只暴露 push/pop/peek，语义纯粹且更快。JDK 文档原话推荐用它替代 Stack。

四、当队列用：为什么优于 LinkedList

LinkedList 也实现了 Deque，能当队列用，但和 ArrayDeque 比有两个劣势：

对比项	ArrayDeque（数组）	LinkedList（链表）
单元素内存	只存元素本身	每节点额外 2 个指针（prev/next）
内存布局	连续，缓存友好	分散，缓存不友好
两端增删	均摊 O(1)（偶尔扩容）	O(1)（但每次都 new 节点）
存 null	不允许	允许

链表每加一个元素都要 new 一个 Node 对象（含两个指针，约多 16~24 字节），还散落在堆各处，遍历时缓存频繁失效。数组则一块连续内存，读写都快。**所以只做队列/栈、不需要 List 的按下标访问时，ArrayDeque 几乎总是更优。**只有确实要存 null，或者要频繁在「任意位置」增删（那其实该用 List 语义），才选 LinkedList。

五、别忘了 PriorityQueue：不是 FIFO 的队列

Queue 家族里有个特殊成员 PriorityQueue：它虽然叫队列，但出队顺序不是 FIFO，而是按优先级（默认最小元素先出）。底层是二叉小顶堆（数组存储），入队/出队都是 O(log n)，取堆顶 peek 是 O(1)。

PriorityQueue<Integer> pq = new PriorityQueue<>();  // 小顶堆
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll();  // 1（最小的先出，不是先进的 5）
pq.poll();  // 3
// 求 Top K、任务调度、Dijkstra 都靠它

面试常拿它和 ArrayDeque 对比：ArrayDeque 是「按进出顺序」的队列/栈，PriorityQueue 是「按大小顺序」的优先队列，用途完全不同。求 Top K 大用小顶堆、任务按优先级调度，都是 PriorityQueue 的活。

六、选型速查表

需求	选择	理由
栈（LIFO）	`ArrayDeque`（push/pop）	无锁、快、语义纯粹，替代 Stack
普通队列（FIFO）	`ArrayDeque`（offer/poll）	内存连续、无节点开销，优于 LinkedList
双端队列	`ArrayDeque`	两端 O(1)
按优先级出队	`PriorityQueue`	堆，O(log n) 维护有序
要存 null / 要 List 能力	`LinkedList`	ArrayDeque 不容 null
多线程生产消费	`BlockingQueue` 家族	内置阻塞与线程安全

记忆钩子：「栈和队列都优先 ArrayDeque；Stack 因带锁+破坏封装被淘汰，LinkedList 因指针开销+缓存差被超越；要优先级找 PriorityQueue，要并发找 BlockingQueue」。

七、常见误区与追问

误区：栈就该用 Stack 类。 Stack 继承 Vector、方法全 synchronized 且暴露按下标访问，已被官方建议弃用，栈应优先 ArrayDeque。
误区：ArrayDeque 可以存 null。 不行，它用 null 标记空槽，存 null 会与「队空」判断冲突抛 NPE；要存 null 用 LinkedList。
误区：LinkedList 做队列比 ArrayDeque 快。 通常更慢，链表每个节点要额外指针、内存分散、缓存不友好；ArrayDeque 连续内存更快。
误区：PriorityQueue 是先进先出。 它按优先级出队（默认最小先出），不是 FIFO；底层是二叉堆。
追问：ArrayDeque 两端操作为什么是 O(1)？ 循环数组只移动 head/tail 指针，用 & (length-1) 实现循环下标（容量是 2 的幂），不搬移元素；只有扩容才 O(n)，均摊后仍 O(1)。
追问：ArrayDeque 线程安全吗？ 不安全；多线程队列用 ConcurrentLinkedQueue（无锁）或 ArrayBlockingQueue/LinkedBlockingQueue（阻塞）。
追问：Deque 当栈时 push 对应哪端？ push/pop 都操作队首（addFirst/removeFirst），所以「栈顶」是队首；这点要和当队列时 poll 取队首、offer 加队尾区分开。

八、加强记忆

把这几个队列结构串成一条选型链：默认队列和栈都用 ArrayDeque——它是循环数组，两端增删均摊 O(1)，内存连续、缓存友好，用位与实现循环下标（容量 2 的幂，和 HashMap 同款）。它当栈完胜古董 Stack（后者继承 Vector、方法全加锁又暴露按下标访问，破坏封装），当队列完胜 LinkedList（后者每节点多两个指针、内存分散、缓存差）。唯一让位 LinkedList 的情况是「要存 null」。要「按优先级出队」而非先进先出，用二叉堆实现的 PriorityQueue（Top K、任务调度）；要「多线程生产消费」，用 BlockingQueue 家族。记住一句「栈队首选 ArrayDeque，优先级找 Priority，并发找 Blocking，存 null 才用 Linked」，这道对比题就答全了。

简化版

详细版