队列
普通队列按先进先出（FIFO）组织元素。本文负责循环数组、端点操作和两栈实现。
1. 面试核心
先记住这几条，再读正文- FIFO 的范围。 FIFO 队列从尾部入队，从头部出队。它约束的是取出顺序，多线程处理任务时，完成顺序还取决于每项任务的耗时。卡 · 使用边界
- 循环队列。 循环数组复用已出队元素腾出的槽位。可用
size区分空与满，也可预留一个槽位来区分两种状态。卡 · 首尾位置与循环数组 - 两栈队列。 两栈队列只在输出栈为空时倒栈。每个元素只转移一次，因此连续出入队操作的摊销时间为 O(1)。卡 · 两栈队列
2. 首尾位置与循环数组
数组容量为 capacity，要求 capacity 大于 0。head 指向待取位置，tail 指向待写位置。位置移动使用 next=(index+1)%capacity。
维护 size 时，size=0 为空，size=capacity 为满。满和空都能出现 head=tail，由 size 区分。
另一种实现预留一个槽位。此时 head=tail 为空，next(tail)=head 为满。可用容量为 capacity−1。实现需选定其中一种约定。
3. 入队与出队
java.util.Queue<Integer> queue = new java.util.ArrayDeque<>();
queue.offer(10);
queue.offer(20);
System.out.println(queue.poll()); // 10
System.out.println(queue.peek()); // 20，仍留在队列中
10 先进入，所以先取出。peek 返回 20，并保留该元素。Java 21 ArrayDeque 的空队列 poll、peek 返回 null。remove、element 在空队列上抛异常，容器拒绝 null 元素。
4. 两栈队列
入队将元素压入输入栈。出队读取输出栈顶。输出栈为空时，才将输入栈全部倒入输出栈。
依次入队 1、2、3，输入栈顶是 3。倒栈后输出栈顶是 1，恢复 FIFO 顺序。输出栈尚有元素时继续倒栈，会让新元素抢到旧元素前面。
每项至多入输入栈一次、转移一次、出输出栈一次。m 次队列操作总成本为 O(m)，所以摊销 O(1)。一次倒栈可移动 n 项，单次最坏仍为 O(n)。
5. 使用边界
生产持续快于消费时，无界队列会积压。容量有界时，需要定义满队列的处理策略。阻塞、拒绝或丢弃应由调用协议决定。
FIFO 约束取出顺序，多线程的完成顺序受执行耗时影响。ArrayDeque 未提供线程安全或阻塞等待。跨线程传递需使用匹配的并发队列。
按优先级取任务使用堆，其出队规则由优先级决定。
6 · 面试题卡片
本页题目与参考回答
6.1 FIFO 能保证并发任务按入队顺序完成吗？
考察重点：取出顺序与完成顺序。
相关内容：使用边界。
参考回答
FIFO 只约束出队顺序。
多个线程的耗时不同，后取任务可先完成。业务要求完成顺序一致时，可串行执行。只要求输出有序时，可按序号缓冲已完成的结果。
6.2 循环队列如何区分空与满？
考察重点：size 与预留槽位两种约定。
相关内容：首尾位置与循环数组。
参考回答
可用 size 区分：0 为空，capacity 为满。
也可预留一格，用 head=tail 表示空。下一写位置等于 head 时表示满，此时少用一个槽位。
6.3 两栈队列为何只在输出栈为空时倒栈？
考察重点：FIFO 不变量与摊销成本。
相关内容：两栈队列。
参考回答
输出栈保存更早入队的元素，必须先取完。
为空时倒栈才能让最早的剩余元素位于栈顶。每项只转移一次，所以连续操作摊销 O(1)。