双端队列是什么
想象一个队伍，你既可以从队头离开，也可以从队尾离开；新来的人既可以从队尾加入，也可以从队头插队——这就是双端队列（Deque，读作“deck”）。它允许在两端进行插入和删除操作，比普通队列更灵活。
四种基本操作与复杂度
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
addFirst | 在队头插入元素 | O(1) |
addLast | 在队尾插入元素 | O(1) |
removeFirst | 删除队头元素 | O(1) |
removeLast | 删除队尾元素 | O(1) |
所有操作都是常数时间，因为双端队列只操作两端，不涉及中间元素。
和栈/队列的关系
双端队列可以“兼任”栈和队列：只从一端插入和删除（比如只用addFirst和removeFirst），它就变成了栈（后进先出）；只从一端插入、另一端删除（比如addLast和removeFirst），它就变成了队列（先进先出）。所以一个双端队列能替代两种数据结构。
底层实现：双向链表 / 环形数组
双端队列有两种常见实现方式：双向链表和环形数组。双向链表的每个节点有前后指针，两端操作只需修改指针，O(1) 但内存开销大。环形数组用固定大小的数组，通过头尾指针循环使用空间，操作也是 O(1)，且内存更紧凑。Java 的 LinkedList 是双向链表实现，ArrayDeque 是环形数组实现，推荐使用后者。
典型应用：滑动窗口最大值
给定一个数组和一个窗口大小 k，窗口每次向右滑动一步，求每个窗口的最大值。用双端队列可以高效解决：队列中存储数组下标，保证队头是当前窗口最大值的下标。每次滑动时，从队尾移除小于新元素的下标，从队头移除已滑出窗口的下标。这样每个元素最多入队出队一次，总时间 O(n)。