真实面经题目 · 原创解析
Java 里要区分“队列接口”和“链表底层”。Queue、Deque 是行为抽象，表示先进先出、双端队列或优先级访问；LinkedList、ConcurrentLinkedQueue、LinkedBlockingQueue 这类才是链式节点结构。ArrayDeque、ArrayBlockingQueue、PriorityQueue 虽然暴露队列接口，但底层分别是循环数组、有界数组和二叉堆数组，不是链表。LinkedHashMap 则是哈希表加双向链表，用链表维护插入顺序或访问顺序，但它本身不实现 Queue。
面试中可以先澄清概念：Java 中 Queue/Deque 是接口，不等于底层就是队列或链表。常见实现可以分三类看。第一类是链表结构，比如 LinkedList 是双向链表，同时实现 List、Deque、Queue；ConcurrentLinkedQueue 是基于链式节点的无界非阻塞 FIFO 队列；LinkedBlockingQueue 是基于链式节点的可选有界阻塞队列。第二类是数组结构但暴露队列能力，比如 ArrayDeque 是循环数组实现的双端队列，ArrayBlockingQueue 是数组实现的有界阻塞队列。第三类是特殊结构，比如 PriorityQueue 底层是数组表示的二叉堆，虽然实现 Queue，但按优先级出队，不保证 FIFO。还有 LinkedHashMap 是 HashMap 加双向链表，链表用于维护迭代顺序或访问顺序，常用于 LRU 思路，但它不是队列实现类。选型时看是否需要 FIFO、双端操作、优先级、阻塞、线程安全、有界容量和顺序维护。
Queue、Deque、BlockingQueue 这些在 Java 中主要是接口或抽象契约，描述元素进入和移除的行为，例如 FIFO、双端入队出队、阻塞等待等。它们不是某一种固定的底层存储方式。一个类实现 Queue，并不意味着它底层是链表；例如 ArrayDeque 是数组，PriorityQueue 是堆，ArrayBlockingQueue 是数组。反过来，一个类使用链表维护顺序，也不一定是队列；例如 LinkedHashMap 通过双向链表维护键值对顺序，但它不实现 Queue。面试回答要把暴露队列接口和链式底层实现分开讲，这是这道题最容易被混淆的地方。
LinkedList 是最典型的链表底层结构。它内部以节点保存元素，每个节点持有前驱、后继和元素引用，因此是双向链表。它同时实现 List、Deque、Queue，所以既可以当普通线性表使用，也可以当 FIFO 队列、双端队列、栈式结构使用。头尾插入和删除在已定位节点的情况下是 O(1)，但按下标随机访问需要从头或尾遍历，时间复杂度是 O(n)。它不是线程安全的，允许存放 null，但作为队列使用时不建议放 null，因为 poll 返回 null 本身也表示队列为空，容易造成语义混淆。
ArrayDeque 实现 Deque，常被推荐作为非线程安全场景下的栈或队列实现。它底层不是链表，而是可扩容的循环数组，通过头尾指针在数组中环形移动来支持两端插入和删除。相比 LinkedList，它通常有更好的局部性和更少的节点对象分配，常见入队、出队操作是摊还 O(1)。ArrayDeque 不允许 null，因为 null 会破坏内部空槽和返回值语义。它适合单线程或外部同步场景下的普通 FIFO 队列、双端队列和栈替代方案，但不适合需要阻塞或并发安全的生产者消费者场景。
PriorityQueue 实现 Queue 接口，但它不是普通 FIFO 队列，也不是链表底层。它内部使用数组表示二叉堆，默认按照元素自然顺序形成小顶堆，也可以通过 Comparator 指定优先级规则。offer 和 poll 通常是 O(log n)，peek 是 O(1)。它的出队顺序由优先级决定，而不是元素插入顺序；如果多个元素优先级相同，也不保证稳定顺序。它不允许 null，也不是线程安全的。面试中提到它时要强调：它是队列抽象的一种实现，但底层结构是堆数组，不是链表，也不是 FIFO。
ConcurrentLinkedQueue 是 java.util.concurrent 中的无界线程安全队列，底层是链式节点结构，语义上是 FIFO。它采用非阻塞算法，通过 CAS 更新头尾节点，适合多线程下高并发入队、出队但不需要阻塞等待的场景。它的 offer、poll、peek 等操作在并发环境中具有较好的伸缩性，但 size 不是常量时间精确计数，通常需要遍历并且在并发修改时只能得到瞬时结果。因此实际使用时不应该频繁依赖 size 做并发控制。它不允许 null，因为 null 要用来表示 poll 没有取到元素。
LinkedBlockingQueue 是 BlockingQueue 的常用实现，底层由链式节点组成。它可以是无界队列，也可以构造为有界队列；如果不指定容量，默认容量非常大，实际使用时可能导致生产速度超过消费速度后堆内存持续增长。它支持 put、take 这类阻塞方法，适合典型生产者消费者模型。与 ConcurrentLinkedQueue 不同，LinkedBlockingQueue 的重点不是无锁非阻塞，而是阻塞协调和容量控制。它通常使用独立的入队、出队锁来提高生产和消费并发度，但仍然属于基于锁和条件队列协调的阻塞队列。
ArrayBlockingQueue 也是 BlockingQueue 的实现，但底层是固定长度数组，不是链表。它创建时必须指定容量，容量不会自动扩展，因此天然适合做有界缓冲区和背压控制。它通过循环数组维护 putIndex、takeIndex 和 count，入队出队在数组中环形推进。与 LinkedBlockingQueue 相比，它内存更紧凑，没有每个元素一个链表节点的额外对象开销，但容量固定，吞吐和锁竞争特征也不同。它可选择公平锁策略，但公平性通常会降低吞吐。面试中可以用它说明：阻塞队列不一定是链表实现。
LinkedHashMap 不是 Queue，也不属于队列实现，但它的底层非常适合拿来说明链表用于维护顺序。它在 HashMap 的桶结构之外，为所有 entry 维护一条双向链表，从而支持按插入顺序迭代；如果开启 accessOrder，则按访问顺序维护，最近访问的元素会移动到链表尾部。基于这个特性，可以重写 removeEldestEntry 实现简单 LRU 缓存。它的查找仍主要依赖哈希表，链表主要负责顺序，不负责像 Queue 那样定义 offer、poll 语义。
如果只是单线程普通队列，ArrayDeque 通常是优先选择；如果需要 List 能力或者明确要链表结构，可以使用 LinkedList，但要接受随机访问慢和节点开销。多线程场景下，如果需要非阻塞、高并发、无界 FIFO，可以考虑 ConcurrentLinkedQueue；如果需要生产者消费者阻塞语义和容量控制，应考虑 BlockingQueue 家族，例如 LinkedBlockingQueue 或 ArrayBlockingQueue。需要优先级调度时使用 PriorityQueue 或并发场景的 PriorityBlockingQueue，但要注意它们不是 FIFO。不同结构的核心差异不是类名里有没有 Queue，而是底层结构、顺序语义、容量、阻塞行为和线程安全保证。
普通单线程 FIFO 或双端队列场景通常更推荐 ArrayDeque。原因是 ArrayDeque 使用循环数组，元素引用连续存放，缓存局部性更好，也没有每个元素一个 Node 的额外对象开销；头尾操作是摊还 O(1)。LinkedList 的优势是链式结构下节点插入删除灵活，但作为普通队列只在头尾操作时，这个优势并不明显，反而要承担更多内存和指针追踪成本。只有当业务确实需要链表特性，或者同时依赖 List、Deque 的某些行为时，才更有理由选 LinkedList。
因为 PriorityQueue 的出队顺序由比较规则决定，而不是由插入时间决定。它底层是数组形式的二叉堆，每次 peek 或 poll 得到的是堆顶元素，也就是当前优先级最高或最低的元素。假设先插入 10 再插入 1，在默认自然顺序下 poll 会先返回 1，而不是 10。这说明它虽然实现 Queue 接口，但语义是优先级队列。如果业务要求严格 FIFO，就不能直接使用 PriorityQueue；如果既要优先级又要同优先级内 FIFO，需要在比较器里加入递增序号。
如果场景需要线程安全 FIFO，但不希望生产者或消费者因为队列空满而阻塞，可以选择 ConcurrentLinkedQueue，它是无界非阻塞队列，适合高并发事件收集、异步传递、任务暂存等场景。不过它没有容量背压，生产速度长期大于消费速度时仍可能造成内存压力。如果需要 put、take 这类阻塞协调，或者需要设置容量限制来保护系统，就应该选择 LinkedBlockingQueue。简而言之，ConcurrentLinkedQueue 偏非阻塞吞吐，LinkedBlockingQueue 偏生产消费协调和容量控制。
LinkedBlockingQueue 如果不显式指定容量，默认容量非常大，使用上接近无界队列。风险是当生产速度持续超过消费速度时，队列会不断堆积节点和元素引用，最终可能造成堆内存膨胀、GC 压力增大甚至 OOM。很多线上问题不是队列逻辑错，而是没有容量边界，系统在下游变慢时不能及时施加背压。实际工程中通常应该根据消费能力和可接受延迟设置合理容量，并配合拒绝策略、限流、降级或监控报警。
ArrayBlockingQueue 使用固定数组，容量创建时确定，内存布局紧凑，不会为每个元素额外创建链表节点，适合容量明确、希望内存可控的有界缓冲区。LinkedBlockingQueue 使用链式节点，容量可以指定，也可以近似无界，入队和出队的锁分离设计在一些生产消费并发场景下有不同的吞吐表现。底层差异会影响内存占用、容量策略、GC 压力和并发竞争特征。选择时不能只看 BlockingQueue 接口，还要看是否需要固定容量、是否能接受节点分配成本以及生产消费模式。
LinkedHashMap 在 HashMap 的哈希查找能力之外维护了一条双向链表。当构造时开启 accessOrder 后，每次访问元素都会调整其链表位置，使链表顺序反映访问新旧。再重写 removeEldestEntry，就可以在插入新元素后自动移除最旧的 entry，从而得到一个简单的 LRU 缓存结构。这里的重点是链表维护访问顺序，哈希表提供 O(1) 级别的 key 查找。它不是 Queue，因为它不提供队列的入队出队抽象，也不适合直接替代并发缓存。
很多队列实现都不允许 null，例如 ArrayDeque、PriorityQueue、ConcurrentLinkedQueue、BlockingQueue 的常见实现通常都禁止 null。核心原因是队列方法 poll 在队列为空时会返回 null，如果允许 null 元素，就无法区分取到的是一个真实的 null 元素，还是队列为空。LinkedList 作为 List 允许 null，但当它被当作 Queue 使用时，放入 null 会让队列语义变得不清晰，所以工程上也不建议这么做。面试中可以把这点作为接口语义和实现约束的例子。
