双端队列实现
核心要点
双端队列（Deque）基本原理
双端队列（double-ended queue）是一种允许在队头和队尾两端都进行插入和删除操作的线性数据结构。
对比标准队列：
- 标准队列（Queue）：FIFO，只能队尾插入、队头删除
- 双端队列（Deque）：队头和队尾都可以插入/删除，不再满足 FIFO
类比：
- 标准队列 → 排队买票（先来先买）
- 双端队列 → 过街天桥（两端都可以进出）
API 接口
class MyDeque<E> {
void addFirst(E e); // O(1) 队头插入
void addLast(E e); // O(1) 队尾插入
E removeFirst(); // O(1) 队头删除
E removeLast(); // O(1) 队尾删除
E peekFirst(); // O(1) 查看队头
E peekLast(); // O(1) 查看队尾
}
实现方式一：链表实现
复用 双链表 结构，利用双链表天然支持 $O(1)$ 时间复杂度在头尾增删元素的特性。
核心思路：
- 使用语言标准库的链表结构（如 Java 的
LinkedList） - 或直接复用已实现的
MyLinkedList双链表类
Java 实现示例：
import java.util.LinkedList;
public class MyListDeque<E> {
private LinkedList<E> list = new LinkedList<>();
void addFirst(E e) { list.addFirst(e); }
void addLast(E e) { list.addLast(e); }
E removeFirst() { return list.removeFirst(); }
E removeLast() { return list.removeLast(); }
E peekFirst() { return list.getFirst(); }
E peekLast() { return list.getLast(); }
}
实现方式二：数组实现
复用 环形数组（CycleArray），利用环形数组的头尾指针实现 $O(1)$ 时间复杂度的头尾增删。
核心思路：
- 环形数组通过取模运算实现逻辑上的"环形"存储
- 头尾指针可以在数组首尾自由移动
Java 实现示例：
class MyArrayDeque<E> {
private CycleArray<E> arr = new CycleArray<>();
void addFirst(E e) { arr.addFirst(e); }
void addLast(E e) { arr.addLast(e); }
E removeFirst() { return arr.removeFirst(); }
E removeLast() { return arr.removeLast(); }
E peekFirst() { return arr.getFirst(); }
E peekLast() { return arr.getLast(); }
}
时间复杂度
| 操作 | 链表实现 | 数组实现 |
|---|---|---|
| addFirst | $O(1)$ | $O(1)$ |
| addLast | $O(1)$ | $O(1)$ |
| removeFirst | $O(1)$ | $O(1)$ |
| removeLast | $O(1)$ | $O(1)$ |
| peekFirst | $O(1)$ | $O(1)$ |
| peekLast | $O(1)$ | $O(1)$ |
应用场景
- Python 算法题：Python 标准库无内置栈和队列，常用
collections.deque模拟标准队列 - 滑动窗口：某些滑动窗口问题可用双端队列维护最值
- 广度优先搜索（BFS）：某些变体需要双端操作
注意：在算法题场景中，双端队列使用频率不算很高，主要是 Python 生态用的多一些。