什么是双端队列（Deque）？它和栈、队列是什么关系？

简化版

双端队列（Deque，double-ended queue）是两端都能进、都能出的线性表：头尾都支持插入和删除。它是栈和队列的「超集」——只用一端就是栈，一端进另一端出就是队列。Java 里 ArrayDeque 是它的高效实现，既能当栈也能当队列，官方也推荐用它替代老 Stack 和 LinkedList 做栈/队列。

详细版

普通队列只能「尾进头出」，双端队列放开了限制，头尾都能操作，核心是四组方法：

操作	队头	队尾
插入	`addFirst` / `offerFirst`	`addLast` / `offerLast`
删除	`removeFirst` / `pollFirst`	`removeLast` / `pollLast`
查看	`peekFirst`	`peekLast`

和栈、队列的关系：

当栈用：只在一端进出 → push(=addFirst) / pop(=removeFirst) / peek(=peekFirst)。
当队列用：一端进另一端出 → offer(=addLast) / poll(=removeFirst)。

所以「双端队列 = 栈 + 队列」，一个结构涵盖两者。Java 里 Deque 是接口，常用实现 ArrayDeque（数组，快）和 LinkedList（链表）。

完整版教学

一、为什么说它是栈和队列的统一

栈（同端进出）和队列（异端进出）都是「操作受限的线性表」。双端队列把限制放开到「两端都能进出」，于是：

只用「头进头出」或「尾进尾出」→ 就是栈；
用「尾进头出」→ 就是队列。

一个双端队列就能模拟这两者，所以它是更通用的结构。这也是为什么 Java 推荐 Deque 作为栈和队列的统一入口。

二、两种实现的取舍

ArrayDeque（数组实现的循环双端队列）：底层是可扩容的循环数组，两端操作均摊 O(1)，缓存友好、无节点开销，是绝大多数场景的首选。不允许存 null（因为 null 被用作「无元素」的信号）。
LinkedList（双向链表）：也实现了 Deque，两端操作 O(1)，但每个节点有前后指针开销、缓存差。它的优势是能存 null、且作为链表还能在中间操作，但当队列/栈用时通常不如 ArrayDeque。

一句话：当栈或队列用，优先 ArrayDeque；只有确实需要链表特性时才用 LinkedList。

三、经典应用：单调队列

双端队列最出彩的应用是单调队列，解决「滑动窗口最大值」这类问题：维护一个队头到队尾单调递减的双端队列，存的是下标。

新元素进来前，从队尾弹掉所有比它小的（它们不可能再是最大值）；
从队头弹掉滑出窗口的下标；
队头始终是当前窗口的最大值。

整个过程每个元素最多进队出队各一次，O(n) 解决，正是靠「两端都能删」的双端队列才做得到。

四、其他用途

回文判断：把字符依次入双端队列，再同时从两端弹出比较。
工作窃取（work-stealing）：线程池调度里，每个线程有自己的双端队列，自己从一端取任务，空闲线程从另一端「偷」任务，减少竞争。
需要「最近使用的从这端进出、最老的从那端淘汰」的缓存类结构也常用到。

五、复杂度与实现边界

Deque 的常规两端操作都应该是 O(1)：addFirst、addLast、removeFirst、removeLast。数组实现通常用循环数组，头尾指针通过取模移动；链表实现则靠前后指针直接摘接节点。面试回答不要只说“双端都能操作”，还要说明它为什么能作为栈、队列和单调队列的底层结构。

队头 front                         队尾 rear
  addFirst/removeFirst      addLast/removeLast
        <---------------- 双端都可操作 ---------------->

如果用数组实现，扩容时仍然可能是 O(n)，但摊还到多次插入通常可看作均摊 O(1)。如果题目强调固定容量或实时系统，就要考虑扩容抖动和容量上限。

六、常见误区与追问

结构	允许操作	典型用途
栈	只在一端进出	DFS、括号匹配
队列	一端进、另一端出	BFS、任务排队
双端队列	两端都能进出	滑动窗口、回文辅助
单调队列	双端队列 + 单调性	滑动窗口最大/最小值

记忆钩子：Deque 是“更通用的两端容器”，但单调队列不是新容器，而是在 Deque 上加了单调不变量。

数字例子：滑动窗口大小 k=3，数组 [1,3,-1,-3,5] 求最大值。Deque 里存候选下标并保持对应值递减；当 5 进来时，会把比 5 小的下标从队尾弹出，5 成为新的最大候选。每个下标最多入队一次、出队一次，所以整体 O(n)。

误区：Deque 等同于 Queue。 Queue 只限制 FIFO，Deque 两端都能插入删除，可以模拟栈和队列。
误区：单调队列就是普通队列排序。 它不是全量排序，只维护窗口内仍可能成为答案的候选元素。
误区：数组 Deque 永远不会移动元素。 循环数组能避免普通头删搬移，但扩容时仍可能重排已有元素。
追问：Deque 为什么适合滑动窗口最大值？ 队头保存当前最大候选，队尾负责淘汰不可能成为最大值的新旧元素。
追问：Java 里为什么常推荐 ArrayDeque 而不是 Stack？ ArrayDeque 更现代，能作为栈或队列使用，通常也避免了旧 Stack 的同步遗留开销。
追问：什么时候链表 Deque 更合适？ 频繁在中间持有节点并删除时链表有优势；只做两端操作时数组 Deque 往往缓存友好。

七、加强记忆

双端队列两端都能进出，是栈（同端进出）和队列（异端进出）的统一超集。Java 用 Deque 接口、优先 ArrayDeque 实现（快、缓存友好、不存 null），当栈当队列都推荐它。最亮眼的应用是单调队列解滑动窗口最大值（O(n)）。

简化版

详细版