Deque 解决"两端都能进出"这一件事，落地却分成两条几乎不相交的路：ArrayDeque/LinkedList 这组内存内双端栈队列，和 DelayQueue 这组带时间维度的到期队列。前者关心头尾下标怎么走，后者关心谁先到期；选错的代价不在功能，在常数、缓存局部性和过期精度。
1. 接口设计：两端的六个方法
Deque 在 Queue 单端基础上对称补了整套 First/Last 变体，规律很硬：add/remove/get 抛异常，offer/poll/peek 返回特殊值；push/pop 全映射到头部，所以一个 Deque 既当 FIFO 队列也当 LIFO 栈。
1.1 ArrayDeque 与 LinkedList 的取舍
| 维度 | ArrayDeque |
LinkedList |
|---|---|---|
| 底层结构 | 环形数组 + head/tail 下标 |
双向链表，每元素一个 Node |
| 内存布局 | 连续数组，引用集中 | 节点分散，各带两引用 + 对象头 |
| 缓存友好度 | 高，顺序遍历基本全命中 | 低，指针跳转易 cache miss |
| 扩容 | 不足时成倍扩容并复制 | 无扩容，只加节点 |
| 随机访问 | 不支持 get(i) |
支持但 O(n) |
允许 null |
不允许，插入即 NullPointerException |
允许 |
| 空队列 | poll → null，remove → NoSuchElementException |
同上 |
Deque<String> dq = new ArrayDeque<>(16);
dq.offerFirst("a"); // head 前移一格
dq.offerLast("b"); // tail 后移一格
dq.offerFirst("c"); // 下标回绕到数组末尾；迭代顺序 c, a, b
禁 null 不是洁癖：poll 用 null 表示空队列，二者不能共存。
一句话选择：双端进出且不带索引访问用 ArrayDeque；要中间删改或允许 null 才轮到 LinkedList。
2. queue 与 stack 两组方法对照
同一批元素，用 Queue 的视角和用 Stack 的视角看，调用名完全不同：
| 意图 | Deque 抛异常版 |
Deque 特殊值版 |
遗留写法 | 遗留失败行为 |
|---|---|---|---|---|
| 头部入队 | addFirst(e) |
offerFirst(e) |
— | — |
| 尾部入队 | addLast(e) / add(e) |
offerLast(e) / offer(e) |
Queue.add 返回 boolean |
有界满抛 IllegalStateException |
| 头部出队 | removeFirst() |
pollFirst() |
Queue.poll 返回 null |
— |
| 尾部出队 | removeLast() |
pollLast() |
— | — |
| 看头部 | getFirst() / element() |
peekFirst() / peek() |
Queue.peek 返回 null |
空栈时 Stack.peek 抛 EmptyStackException |
| 看尾部 | getLast() |
peekLast() |
— | — |
| 出队（严格） | remove() |
— | pop() |
空栈抛 EmptyStackException |
| 栈式入 | push(e) = addFirst |
— | push(e) |
— |
String a = deque.poll(); // 空时 null，调用方必须判空
String b = deque.remove(); // 空时抛 NoSuchElementException
if (deque.isEmpty()) { ... } // 先判空再 remove，最稳
两组方法的差别只在有界队列上生效：ArrayBlockingQueue 满时 offer 返回 false、add 抛 IllegalStateException。
3. 用 ArrayDeque 替代 Stack 的理由
Stack 继承 Vector，每个方法都带 synchronized，还继承了一堆与栈无关的操作（add(int, E)、get(int)）：锁粒度全压在对象上，单线程白付代价，而 Vector 的索引方法让"任意位置插入"变成合法调用，破坏了栈的抽象。
迭代顺序也不同：Stack 是从栈底到栈顶，ArrayDeque 用 push 后是从栈顶到栈底。只换类不改消费顺序，输出会整体反过来。
// 改写前：Stack，全方法 synchronized，迭代由底到顶
Stack<Task> stack = new Stack<>();
stack.push(task);
while (!stack.isEmpty()) process(stack.pop()); // 空栈抛 EmptyStackException
// 改写后：ArrayDeque，无锁、禁 null、迭代由顶到底
Deque<Task> stack = new ArrayDeque<>();
stack.push(task); // = addFirst
while (!stack.isEmpty()) process(stack.poll()); // 空时 null，不抛异常
for (Task t : stack) log(t); // 迭代：栈顶 → 栈底
并发栈得用 ConcurrentLinkedDeque 或 LinkedBlockingDeque，Stack 也不是答案。
4. 三种典型应用
4.1 单调队列：滑动窗口最大值
被淘汰的元素只从队头出，新元素只从队尾入，队尾不大于新元素的直接丢掉。
// 单调递减队列：队头永远是窗口最大值；存下标不存值
int[] maxWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // 队头过期
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // 队尾淘汰
dq.offerLast(i);
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
4.2 工作窃取：ForkJoinPool 的 workQueue
每个工作线程持有一个 WorkQueue，本质是双端队列：自己 fork 从队尾 push、自己执行从队尾 pop；别的线程来偷，从队头 poll。 本地线程只碰队尾、窃取者只碰队头，两端相遇才需要 CAS。JDK 17 内部是数组实现的双端队列（WorkQueue 的 ForkJoinTask<?>[] array），语义与 Deque 一致。
Task t = queue.pollLast(); // 本地：LIFO，取最新的
if (t != null) t.fork(); // 子任务压回队尾
// 窃取线程：queue.pollFirst() 从最老的开始偷，FIFO
4.3 编辑器撤销栈
撤销与重做是一对方向相反的栈，两个 Deque，push/pop 全在头部：
void apply(Edit e) {
undo.push(e); // 新操作入撤销栈
if (undo.size() > LIMIT) undo.pollLast(); // 超限丢最老的
redo.clear(); // 新操作让重做栈失效
}
void undo() {
if (undo.isEmpty()) return;
Edit e = undo.pop();
e.revert();
redo.push(e); // 挪到重做栈
}
pollLast 丢最久远的、pop 取最新的，两端语义必须分清。
一句话总结：Deque 的价值在"两端语义明确"，栈、队列、单调队列、工作窃取都只是同一组方法的不同使用姿势。
5. 延迟队列的四种实现
Deque 管顺序，DelayQueue 管时间。到期这件事有四种落法：
| 方案 | 精度 | 可靠性（重启） | 成本 | 适用量级 |
|---|---|---|---|---|
DelayQueue |
随轮询与 getDelay，通常毫秒级 |
进程内，重启即丢 | 极低，单机内存 | 单机万级以内 |
| Redis ZSet 轮询 | 随轮询间隔，秒级常见 | 落 Redis，看持久化配置 | 低，需一个轮询线程 | 几十万级，可分片 |
| MQ 延迟消息 | 随 broker 实现 | 最高，重投 + 消费确认 | 中高，要维护中间件 | 百万级、跨服务 |
| 时间轮 | 随 tick 粒度，通常秒级 | 同样在进程内 | 低，插入 O(1) | 单机十万级高频 |
有序性：DelayQueue 按 compareTo，ZSet 按 score，时间轮同槽无序跨槽有序，MQ 由 broker 按投递时间保证。按各自文档核对：RocketMQ 延迟是固定档位（1s/5s/10s…按所部署版本查），不是任意秒数；RabbitMQ 原生不支持任意延迟，要靠 TTL + 死信队列或延迟插件，前者有"队头阻塞"——队头未到期时后面已到期的也出不去。
// Redis ZSet：score 存到期时间戳
// ZADD delay:q <expireMs> <taskId>；轮询 ZRANGEBYSCORE delay:q -inf <now> LIMIT 0 100
Long n = jedis.zrem("delay:q", taskId);
if (n != null && n == 1L) execute(taskId); // 抢到执行权的实例才跑
ZREM 返回删除条数，只有拿到 1 的实例有执行权，这是多实例轮询最省事的去重；但取任务与执行之间没有事务，中途挂掉就丢任务，要更强保证得走 MQ 的消费确认。
一句话选择：单机短延迟用 DelayQueue，跨实例用 MQ，量级在中间且已有 Redis 就用 ZSet 轮询。
6. 时间轮的分层设计
有序集合做定时是插入 O(log n)，时间轮把它压成 O(1)：按到期时间算出槽位下标，挂进那个槽的链表。单层轮的死穴是槽数固定，跨度一长就要么槽极多、要么 tick 极粗，分层轮用"秒级槽 + 层级推进"解决：
| 层级 | 槽数 | 每槽跨度 | 覆盖范围 | 推进条件 |
|---|---|---|---|---|
| L0 | 60 | 1 秒 | 60 秒 | 每 tick 前移一格 |
| L1 | 60 | 1 分钟 | 60 分钟 | L0 转满一圈前移一格 |
| L2 | 24 | 1 小时 | 24 小时 | L1 转满一圈前移一格 |
插入按延迟选层级，高层槽被推进到时把槽内任务降级重插低层，每个任务最终都在 L0 到期。
void insert(Task t) { // O(1) 入槽
long delay = t.expireAt - now();
int lv = levelOf(delay); // 按延迟选层级
int idx = (int) ((tick(lv) + delay / tickOf(lv)) % slotsOf(lv));
wheels[lv][idx].tasks.offerLast(t); // 槽本身是个 Deque
}
void advance() { // 每 tick 调一次
Deque<Task> q = wheels[0][(int) (tick++ % 60)].tasks;
while (!q.isEmpty()) {
Task t = q.pollFirst();
if (t.expireAt <= now()) run(t); // 真到期才执行
else cascade(t); // 未到期：降级重插
}
}
- 空转：没任务时
advance()仍按 tick 推进，槽多就是白烧 CPU；netty的HashedWheelTimer用固定wheelSize+ 单线程sleep到下一个 deadline，靠startTime对齐压住空转。 - 同槽无序：执行前必须再判一次
expireAt <= now()，否则提前执行；Kafka 的TimerWheel用粗 tick + 延迟队列兜底，思路接近。
DelayQueue 本质是按 getDelay 排序的堆，插入 O(log n)；时间轮插入 O(1)，但槽数与 tick 粒度必须提前定死。
7. DelayQueue 的语义细节
7.1 元素必须实现 Delayed
class Order implements Delayed {
final long expireAt; // 绝对到期时间（毫秒），不是延迟时长
Order(long d) { this.expireAt = System.currentTimeMillis() + d; }
public long getDelay(TimeUnit u) { // 剩余延迟，可为负
return u.convert(expireAt - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
public int compareTo(Delayed o) { // 堆序：与 getDelay 同口径
return Long.compare(this.expireAt, ((Order) o).expireAt);
}
}
两者必须基于同一个绝对到期时间：若 compareTo 按插入时间排而 getDelay 按到期时间算，堆顶就不是最早到期的元素，take() 会取到未到期的对象，或把已到期的任务压在堆里出不来。
7.2 leader-follower：只让一个线程等
内部只有一个 leader 字段。多个消费者调 take() 时只有 leader 用 awaitNanos(delay) 带超时等待，其余无限 park；leader 取到元素后置 leader = null 并 signal() 唤醒一个 follower 接班。
// take() 循环骨架（JDK 17 语义）
for (;;) {
E first = q.peek();
if (first == null) available.await(); // 空：无限等
else if (first.getDelay(NANOSECONDS) <= 0L) return q.poll(); // 到期：取走
else if (leader != null) available.await(); // 已有 leader：跟着 park
else { leader = Thread.currentThread();
try { available.awaitNanos(first.getDelay(NANOSECONDS)); } // 只有 leader 带超时
finally { if (leader == currentThread) leader = null; } }
}
为什么不让所有线程都 awaitNanos：那样到期瞬间全体醒来抢锁形成惊群；leader-follower 让同一时刻只有一个线程计时，省掉重复的定时器注册。
7.3 take 与 poll(timeout) 的差别
| 方法 | 队列空时 | 非空但未到期 | 超时参数 |
|---|---|---|---|
take() |
阻塞直到有元素到期 | 阻塞到该元素到期 | 无，只能靠中断退出 |
poll() |
立即返回 null |
立即返回 null |
无 |
poll(timeout, unit) |
最多等 timeout |
等到 min(timeout, 剩余延迟) |
有，超时返 null |
无参 poll() 在"有元素但都没到期"时也返回 null，常被误认为队列空了。
7.4 多消费者与重复消费
take() 取出的元素会被 q.poll() 从堆里移除，不会重复消费；真正的风险在"取出来之后、处理完成之前进程崩溃"——元素已消失，任务就丢了。它没有 ack，也不做持久化。
8. 排错
| 现象 | 原因 | 处理 |
|---|---|---|
偶发 NoSuchElementException |
poll 与 remove 混用，空队列时 remove 抛异常 |
统一用 poll/peek 并判空 |
peek() 后调方法抛 NPE |
peek 在空队列返回 null |
返回值必须判空 |
ArrayDeque 一插就抛 NPE |
元素是 null |
该容器禁 null，需要则改 LinkedList |
换 ArrayDeque 后顺序反了 |
迭代方向由"底→顶"变"顶→底" | 检查 for/forEach 的消费顺序 |
有元素但 poll() 返回 null |
元素未到期，无参 poll 不等待 |
改 take() 或带超时 poll |
take() 取到未到期元素 |
compareTo 与 getDelay 口径不一致 |
两者用同一到期时间字段 |
| 延迟任务重启后全丢 | DelayQueue 纯内存，无持久化 |
落库/落 Redis，启动重建 |
| 时间轮 CPU 偏高但没任务 | 空 tick 推进 + 槽数过多 | 按最大延迟定槽数，空闲跳空转 |
9. 边界
| 场景 | 该用什么 | 理由 |
|---|---|---|
| 单机、万级任务、允许重启丢失 | DelayQueue |
零依赖，语义最直白 |
| 需要持久化与跨实例 | Redis ZSet / MQ 延迟消息 | 进程挂了任务还在 |
| 有界并发队列、要阻塞 | ArrayBlockingQueue / LinkedBlockingDeque |
ArrayDeque 不阻塞、无上限 |
| 多线程共享栈/队列 | ConcurrentLinkedDeque |
ArrayDeque 非线程安全 |
| 十万级高频定时、跨度大 | 分层时间轮 | 插入 O(1)，槽数需预估 |
| 毫秒级精度的少量定时 | ScheduledThreadPoolExecutor |
基于延迟堆，精度同级 |
| 需要索引访问或中间插入 | LinkedList / ArrayList |
Deque 契约没有 get(i) |
ArrayDeque 不是"更好的 LinkedList"，它是"更好的 Stack 和队列"：要按下标读写、要在中间删改，都不该往 Deque 上靠。
10. 自测
offer与add在ArrayDeque上几乎没差别，这个差别在哪个类上才真正生效？- 把
Stack换成ArrayDeque后，for循环的遍历顺序为什么变了？ - 单调队列为什么存下标而不是存元素值？
DelayQueue里compareTo与getDelay不同口径，会出什么现象？take()的 leader-follower 设计，具体省掉了哪一类开销？- 时间轮同一槽内的任务，执行前为什么还要再判一次到期时间？