队列：从 FIFO 到 DelayQueue

以前看到“队列：从 FIFO 到 DelayQueue”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为我最初把队列理解成“只能从两端操作的数组”，后来接触阻塞队列和延迟队列，才看到它其实在约束任务流转顺序。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。

队列规定“先进入的元素先处理”，即 FIFO。这个简单约束把生产者和消费者解耦：生产者只负责入队，消费者按规则取出任务，而不必知道任务由谁产生。

它从哪里来

排队规则远早于计算机。进入操作系统时代后，任务调度、打印作业、网络数据包和设备请求都需要按顺序等待处理，队列因此成为连接生产者与消费者的基础抽象。后来优先队列、阻塞队列和延迟队列又为不同调度规则服务。

基础队列与环形数组

环形队列、优先队列、阻塞队列和延迟队列关系图

图：从环形数组到不同工程队列的访问语义

如果数组队列每次出队都把剩余元素左移，出队会变成 O(n)。更合理的做法是维护 head 和 tail，把数组首尾看成相连的圆环。

public final class CircularQueue<E> {
    private final Object[] elements;
    private int head;
    private int tail;
    private int size;

    public CircularQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        elements = new Object[capacity];
    }

    public boolean offer(E value) {
        if (size == elements.length) return false;
        elements[tail] = value;
        tail = (tail + 1) % elements.length;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0) return null;
        E value = (E) elements[head];
        elements[head] = null;
        head = (head + 1) % elements.length;
        size--;
        return value;
    }
}

使用 size 可以明确区分“空”和“满”；另一种实现会故意空出一个槽位，通过 head == tail 表示空。

Java Queue 的方法语义

操作	失败抛异常	失败返回特殊值
入队	`add`	`offer` 返回 `false`
出队	`remove`	`poll` 返回 `null`
查看队头	`element`	`peek` 返回 `null`

业务代码通常更适合 offer/poll/peek，因为容量不足或暂时为空可以成为正常控制流，而不是异常。

队列、双端队列和优先队列不是一回事

Queue 强调队尾进入、队头离开。
Deque 允许两端进入和离开，可同时表达队列、栈和滑动窗口。
PriorityQueue 按比较器决定谁先离开，不保证 FIFO。
BlockingQueue 在队列空或满时提供等待语义，用于线程协作。

优先级相同的元素是否保持到达顺序，需要明确设计。Java PriorityQueue 不承诺稳定性；若必须稳定，可把递增序号加入比较键。

队列是 BFS 的核心

广度优先搜索把起点入队，每次取出一个节点，再把未访问邻居入队。因为队列维持发现顺序，节点会按距离层级被处理。

static int shortestSteps(java.util.List<java.util.List<Integer>> graph,
                         int start, int target) {
    int[] distance = new int[graph.size()];
    java.util.Arrays.fill(distance, -1);
    java.util.ArrayDeque<Integer> queue = new java.util.ArrayDeque<>();
    distance[start] = 0;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int current = queue.poll();
        if (current == target) return distance[current];
        for (int next : graph.get(current)) {
            if (distance[next] != -1) continue;
            distance[next] = distance[current] + 1;
            queue.offer(next);
        }
    }
    return -1;
}

必须在入队时标记访问；若等到出队才标记，同一节点可能被多个前驱重复加入。

BlockingQueue 与生产者消费者

生产者消费者队列背压图

图：生产与消费吞吐不匹配时的队列和背压策略

java.util.concurrent.BlockingQueue<Task> queue =
        new java.util.concurrent.ArrayBlockingQueue<>(1000);

// 生产者：容量满时等待
queue.put(task);

// 消费者：队列空时等待
Task next = queue.take();

有限容量是背压的一部分。当消费变慢时，生产者会被限制，不至于把所有压力变成内存占用。但阻塞是否能接受、等待多久、超时后丢弃还是降级，都需要业务决策。

常见实现选择：

容器	特点	适合
`ArrayBlockingQueue`	固定容量、数组存储	明确背压上限
`LinkedBlockingQueue`	可设容量、节点存储	吞吐优先但仍应显式限界
`SynchronousQueue`	不存元素，生产消费直接交接	线程池任务移交
`PriorityBlockingQueue`	按优先级，无界	有优先级且能控制生产速度
`DelayQueue`	到期后可取，无界	进程内延迟任务

无界不是没有容量，而是上限大到通常先耗尽进程内存。

DelayQueue 为什么不是普通 FIFO

延迟队列中的元素只有到期后才能被取走。它通常依赖优先队列，让“剩余延迟最短”的元素位于堆顶。多个元素的先后顺序主要由到期时间决定，而不是单纯的入队时间。

record RetryTask(String id, long deadlineNanos)
        implements java.util.concurrent.Delayed {
    @Override
    public long getDelay(java.util.concurrent.TimeUnit unit) {
        long remaining = deadlineNanos - System.nanoTime();
        return unit.convert(remaining, java.util.concurrent.TimeUnit.NANOSECONDS);
    }

    @Override
    public int compareTo(java.util.concurrent.Delayed other) {
        return Long.compare(deadlineNanos, ((RetryTask) other).deadlineNanos);
    }
}

使用单调时钟 System.nanoTime() 计算持续时间，比可能发生校时跳变的墙上时间更稳妥。compareTo 与延迟计算必须使用一致的排序依据，否则队头可能不是最早到期的任务。

工程边界

DelayQueue 适合单进程内的超时检查、短期重试和缓存过期。它并不天然持久化，进程重启后任务会丢失；多实例之间也不会自动协调。涉及订单关闭、资金、长时间调度等可靠任务，应使用带持久化、确认和重试机制的消息系统或任务调度平台。

还要注意背压：生产速度长期高于消费速度时，无界队列只会把压力变成内存增长。有限队列、拒绝策略、限流和监控通常需要一起设计。

队列测试清单

空队列 poll/peek 的返回语义。
容量为 1 时的满、空切换。
head 和 tail 多次跨越数组末尾。
填满、取出一半、再填满，验证元素顺序。
DelayQueue 中多个相同到期时间元素的比较一致性。
生产快于消费时，容量、等待和拒绝策略是否符合预期。

自测

环形队列如何区分空和满？
offer 与 add 的语义差异是什么？
DelayQueue 为什么需要优先队列？
哪些任务不应该只保存在进程内延迟队列？