Hello 算法精讲：双向队列（Deque）从常用操作、多语言 API 到链表与环形数组两种源码实现

双向队列（deque，double-ended queue）在普通队列“只能队首出、队尾入”的基础上放开限制，允许在队首与队尾两端自由地插入与删除元素，是兼具栈与队列逻辑的通用线性容器。本文以《Hello 算法》仓库中日文版双向队列文档为骨架，结合仓库中 Python、C++、Java、C 等多语言实现源码，讲解双向队列的基本操作、标准库用法、两种底层实现原理及其在软件“撤销”等场景中的实际应用。读完本文，你将掌握双向队列的完整 API 使用、O(1) 复杂度的来源，以及如何亲手用双向链表和环形数组各实现一遍双向队列。

双向队列是什么：比队列更自由的线性结构

在普通队列（queue）中，我们只能删除队首元素或在队尾添加元素，这是一种“一端进、一端出”的约束结构。双向队列在此基础上提供了更高的灵活性：允许在队首和队尾执行元素的添加或删除操作，即四个方向都是 O(1) 的读写。

由于双向队列“两头都能进、两头都能出”，它在逻辑上同时涵盖了栈（后进先出）与队列（先进先出）的能力，甚至允许你在一个容器内切换两种使用模式。

双向队列的常用操作与复杂度

双向队列的六种核心方法命名在不同编程语言中并不完全一致，但语义一致、时间复杂度均为 O(1)（以内置双向队列结构实现为前提）：

方法名	说明	时间复杂度
push_first()	将元素添加至队首	$O(1)$
push_last()	将元素添加至队尾	$O(1)$
pop_first()	删除队首元素	$O(1)$
pop_last()	删除队尾元素	$O(1)$
peek_first()	访问队首元素（不删除）	$O(1)$
peek_last()	访问队尾元素（不删除）	$O(1)$

需要特别说明的是，上面“O(1)”成立的前提是语言确实提供了真正的双向队列容器。若仅用普通数组模拟（如 JS/TS/Swift/Ruby 用 Array），在头部插入/删除会导致后续元素整体平移，实际复杂度会退化为 O(n)，这一点在下面各语言示例中已用注释标出。

直接使用语言内置的双向队列

大多数编程语言的标准库都内置了双向队列或其等价物，可以直接调用，无需自行实现。本仓库在 codes/*/chapter_stack_and_queue/deque.* 中为每种语言保存了完整的可运行示例（例如 C++ 版 deque.cpp 就是一个带 printDeque 输出验证的 Driver 程序）。

Python：collections.deque

代码对应文件：codes/python/chapter_stack_and_queue/deque.py

from collections import deque

# 初始化双向队列
deq: deque[int] = deque()

# 元素入队
deq.append(2)      # 添加至队尾
deq.append(5)
deq.append(4)
deq.appendleft(3)  # 添加至队首
deq.appendleft(1)

# 访问元素
front: int = deq[0]  # 队首元素
rear: int = deq[-1]  # 队尾元素

# 元素出队
pop_front: int = deq.popleft()  # 队首元素出队
pop_rear: int = deq.pop()       # 队尾元素出队

# 获取双向队列的长度
size: int = len(deq)

# 判断双向队列是否为空
is_empty: bool = len(deq) == 0

C++：std::deque

/* 初始化双向队列 */
deque<int> deque;

/* 元素入队 */
deque.push_back(2);   // 添加至队尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // 添加至队首
deque.push_front(1);

/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素

/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
bool empty = deque.empty();

Java：java.util.Deque 接口（常用 LinkedList 实现）

/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();

/* 元素入队 */
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

/* 访问元素 */
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

/* 元素出队 */
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();

C#：LinkedList<T>

/* 初始化双向队列 */
// 在 C# 中，将链表 LinkedList 看作双向队列来使用
LinkedList<int> deque = new();

/* 元素入队 */
deque.AddLast(2);   // 添加至队尾
deque.AddLast(5);
deque.AddLast(4);
deque.AddFirst(3);  // 添加至队首
deque.AddFirst(1);

/* 访问元素 */
int peekFirst = deque.First.Value;  // 队首元素
int peekLast = deque.Last.Value;    // 队尾元素

/* 元素出队 */
deque.RemoveFirst();  // 队首元素出队
deque.RemoveLast();   // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.Count;

/* 判断双向队列是否为空 */
bool isEmpty = deque.Count == 0;

Go：container/list（双向链表）

/* 初始化双向队列 */
// 在 Go 中，将 list 作为双向队列使用
deque := list.New()

/* 元素入队 */
deque.PushBack(2)      // 添加至队尾
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // 添加至队首
deque.PushFront(1)

/* 访问元素 */
front := deque.Front() // 队首元素
rear := deque.Back()   // 队尾元素

/* 元素出队 */
deque.Remove(front)    // 队首元素出队
deque.Remove(rear)     // 队尾元素出队

/* 获取双向队列的长度 */
size := deque.Len()

/* 判断双向队列是否为空 */
isEmpty := deque.Len() == 0

Swift：用 Array 模拟

/* 初始化双向队列 */
// Swift 没有内置的双向队列类，可以把 Array 当作双向队列来使用
var deque: [Int] = []

/* 元素入队 */
deque.append(2) // 添加至队尾
deque.append(5)
deque.append(4)
deque.insert(3, at: 0) // 添加至队首
deque.insert(1, at: 0)

/* 访问元素 */
let peekFirst = deque.first! // 队首元素
let peekLast = deque.last! // 队尾元素

/* 元素出队 */
// 使用 Array 模拟时 popFirst 的复杂度为 O(n)
let popFirst = deque.removeFirst() // 队首元素出队
let popLast = deque.removeLast() // 队尾元素出队

/* 获取双向队列的长度 */
let size = deque.count

/* 判断双向队列是否为空 */
let isEmpty = deque.isEmpty

JavaScript / TypeScript：用 Array 模拟

/* 初始化双向队列 */
// JavaScript 没有内置的双端队列，只能把 Array 当作双端队列来使用
const deque = [];

/* 元素入队 */
deque.push(2);
deque.push(5);
deque.push(4);
// 请注意，由于是数组，unshift() 方法的时间复杂度为 O(n)
deque.unshift(3);
deque.unshift(1);

/* 访问元素 */
const peekFirst = deque[0];
const peekLast = deque[deque.length - 1];

/* 元素出队 */
// 请注意，由于是数组，shift() 方法的时间复杂度为 O(n)
const popFront = deque.shift();
const popBack = deque.pop();

/* 获取双向队列的长度 */
const size = deque.length;

/* 判断双向队列是否为空 */
const isEmpty = size === 0;

/* 初始化双向队列 */
// TypeScript 没有内置的双端队列，只能把 Array 当作双端队列来使用
const deque: number[] = [];

/* 元素入队 */
deque.push(2);
deque.push(5);
deque.push(4);
// 请注意，由于是数组，unshift() 方法的时间复杂度为 O(n)
deque.unshift(3);
deque.unshift(1);

/* 访问元素 */
const peekFirst: number = deque[0];
const peekLast: number = deque[deque.length - 1];

/* 元素出队 */
// 请注意，由于是数组，shift() 方法的时间复杂度为 O(n)
const popFront: number = deque.shift() as number;
const popBack: number = deque.pop() as number;

/* 获取双向队列的长度 */
const size: number = deque.length;

/* 判断双向队列是否为空 */
const isEmpty: boolean = size === 0;

Dart：Queue 本身就是双向队列

/* 初始化双向队列 */
// 在 Dart 中，Queue 被定义为双向队列
Queue<int> deque = Queue<int>();

/* 元素入队 */
deque.addLast(2);  // 添加至队尾
deque.addLast(5);
deque.addLast(4);
deque.addFirst(3); // 添加至队首
deque.addFirst(1);

/* 访问元素 */
int peekFirst = deque.first; // 队首元素
int peekLast = deque.last;   // 队尾元素

/* 元素出队 */
int popFirst = deque.removeFirst(); // 队首元素出队
int popLast = deque.removeLast();   // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.length;

/* 判断双向队列是否为空 */
bool isEmpty = deque.isEmpty;

Rust：VecDeque

/* 初始化双向队列 */
let mut deque: VecDeque<u32> = VecDeque::new();

/* 元素入队 */
deque.push_back(2);  // 添加至队尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3); // 添加至队首
deque.push_front(1);

/* 访问元素 */
if let Some(front) = deque.front() { // 队首元素
}
if let Some(rear) = deque.back() {   // 队尾元素
}

/* 元素出队 */
if let Some(pop_front) = deque.pop_front() { // 队首元素出队
}
if let Some(pop_rear) = deque.pop_back() {   // 队尾元素出队
}

/* 获取双向队列的长度 */
let size = deque.len();

/* 判断双向队列是否为空 */
let is_empty = deque.is_empty();

Kotlin：LinkedList（实现 Deque 语义）

/* 初始化双向队列 */
val deque = LinkedList<Int>()

/* 元素入队 */
deque.offerLast(2)  // 添加至队尾
deque.offerLast(5)
deque.offerLast(4)
deque.offerFirst(3) // 添加至队首
deque.offerFirst(1)

/* 访问元素 */
val peekFirst = deque.peekFirst() // 队首元素
val peekLast = deque.peekLast()   // 队尾元素

/* 元素出队 */
val popFirst = deque.pollFirst() // 队首元素出队
val popLast = deque.pollLast()   // 队尾元素出队

/* 获取双向队列的长度 */
val size = deque.size

/* 判断双向队列是否为空 */
val isEmpty = deque.isEmpty()

Ruby：用 Array 模拟

# 初始化双向队列
# Ruby 没有内置的双端队列，只能把 Array 当作双端队列来使用
deque = []

# 元素入队
deque << 2
deque << 5
deque << 4
# 请注意，由于是数组，Array#unshift 方法的时间复杂度为 O(n)
deque.unshift(3)
deque.unshift(1)

# 访问元素
peek_first = deque.first
peek_last = deque.last

# 元素出队
# 请注意，由于是数组， Array#shift 方法的时间复杂度为 O(n)
pop_front = deque.shift
pop_back = deque.pop

# 获取双向队列的长度
size = deque.length

# 判断双向队列是否为空
is_empty = size.zero?

C：无内置双向队列，需自行实现

// C 未提供内置双向队列

值得留意的是，方法名的差异并不影响使用逻辑：凡是“队首增删”对应 push/pop _front、unshift/shift、offer/poll First 这类带“首/Front/First/left”语义的方法；凡是对应“队尾”则使用带 back、Last、append/pop、push/pop_back 等命名。抓住“哪一端操作、是读还是删”两个维度，就可以在不同语言之间自如迁移。

双向队列的两种实现原理与源码级解析

原文档指出：双向队列的实现与队列类似，可以选择链表或数组作为底层数据结构。本仓库在 codes/ 的每个语言目录下都提供了 linkedlist_deque.* 与 array_deque.* 两份完整实现，并配有 Driver Code 可运行验证（见 C 版 linkedlist_deque.c 与 C 版 array_deque.c 的 main() 函数）。

基于双向链表的实现

回顾普通队列的实现：使用单向链表即可胜任，因为只需要“删头（出队）+ 尾后追加（入队）”两个方向的低成本操作。而双向队列要求头部和尾部都能入队、出队，即两个对称方向都需要操作，因此必须选用带 prev（前驱）与 next（后继）两个指针的双向链表。

实现思路：把双向链表的头节点和尾节点直接当作双向队列的队首和队尾，通过链表两端完成节点的添加与删除。对应的分步示意图可在 ja/docs/chapter_stack_and_queue/deque.assets/ 下的 linkedlist_deque_step1.png 至 linkedlist_deque_step5_pop_first.png 中查看（步骤依次为初始状态、队尾入队、队首入队、队尾出队、队首出队）。

以 C 语言实现为例，节点结构同时保存前驱与后继：

/* 双向链表节点 */
typedef struct DoublyListNode {
    int val;                     // 节点值
    struct DoublyListNode *next; // 后继节点
    struct DoublyListNode *prev; // 前驱节点
} DoublyListNode;

入队操作被统一封装为带 isFront 标志的 push()，按目标端完成指针重连并更新头尾引用，参见 linkedlist_deque.c：

/* 入队 */
void push(LinkedListDeque *deque, int num, bool isFront) {
    DoublyListNode *node = newDoublyListNode(num);
    // 若链表为空，则令 front 和 rear 都指向 node
    if (empty(deque)) {
        deque->front = deque->rear = node;
    }
    // 队首入队操作
    else if (isFront) {
        deque->front->prev = node; // 将 node 链接至旧队首之前
        node->next = deque->front;
        deque->front = node;       // 更新头节点
    }
    // 队尾入队操作
    else {
        deque->rear->next = node;  // 将 node 链接至旧队尾之后
        node->prev = deque->rear;
        deque->rear = node;
    }
    deque->queSize++;              // 更新队列长度
}

/* 队首入队 */
void pushFirst(LinkedListDeque *deque, int num) {
    push(deque, num, true);
}

/* 队尾入队 */
void pushLast(LinkedListDeque *deque, int num) {
    push(deque, num, false);
}

出队操作 pop() 同样通过 isFront 区分方向：队首出队时暂存头节点值、将 front 指向原头节点的 next 并释放原头节点；队尾出队则对称地处理 rear 的前驱节点。由于每一端都只涉及常数次指针操作，入队、出队、读取队首/队尾全部是 O(1)；同时因为每个节点都持有两个方向的指针，额外内存开销约为单向链表的两倍（多一个 prev 指针字段）。

基于环形数组的实现

如果不想为每个元素分配独立节点，也可以用数组实现。由于数组不支持在头部以 O(1) 插入/删除，需引入**环形数组（circular array）**技巧：用取余运算把数组“首尾相接”，让 front 指针在越过数组边界时自动回绕。仓库中的多语言版本结构高度一致，例如 Python 版 array_deque.py 用 _nums、_front、_size 三个成员；C 版 array_deque.c 对应为 nums、front、queSize + queCapacity。

核心是索引回绕函数与指针维护逻辑：

/* 计算环形数组索引 */
int dequeIndex(ArrayDeque *deque, int i) {
    // 通过取余操作实现数组首尾相连
    return ((i + capacity(deque)) % capacity(deque));
}

/* 队首入队 */
void pushFirst(ArrayDeque *deque, int num) {
    if (deque->queSize == capacity(deque)) {
        printf("双向队列已满\r\n");
        return;
    }
    // 队首指针向左移动一位，越过数组头部后回到尾部
    deque->front = dequeIndex(deque, deque->front - 1);
    deque->nums[deque->front] = num;
    deque->queSize++;
}

/* 队尾入队 */
void pushLast(ArrayDeque *deque, int num) {
    if (deque->queSize == capacity(deque)) {
        printf("双向队列已满\r\n");
        return;
    }
    // 队尾指针指向“队首索引 + 队长度”，即队尾的下一个空位
    int rear = dequeIndex(deque, deque->front + deque->queSize);
    deque->nums[rear] = num;
    deque->queSize++;
}

对应分步示意图见 ja/docs/chapter_stack_and_queue/deque.assets/ 下的 array_deque_step1.png 至 array_deque_step5_pop_first.png。阅读代码时可抓住两条规律：

• 队尾位置不需要单独存指针：队尾空位恒等于 front + queSize（经 dequeIndex 回绕），因此只需维护 front 与 queSize 两个量即可描述整个队列；
• popLast 只减少 queSize：队尾元素出队时无需移动任何指针，逻辑上“失效”即可（见 array_deque.c 的 popLast()），而 popFirst 需要把 front 右移一位再自减长度。

需要补充的工程细节是：环形数组实现的空间是在构造时预分配的固定容量（newArrayDeque(capacity)），当 queSize == capacity 时入队会提示“队列已满”并拒绝操作（Python/C 版本均有此逻辑）。若需要动态扩容，还需在满时申请更大的数组并把元素按 front 到 rear 的顺序拷贝迁移，这一扩展步骤在基础教学版中未展示，实际使用时请预留足够容量或自行增加扩容逻辑。

两种实现方式的取舍也非常清晰：

• 双向链表：按需分配节点，无容量上限（受内存限制），四端操作天然 O(1)，但节点带 prev/next 指针，内存占用较高，且对 CPU 缓存不友好；
• 环形数组：内存连续、缓存友好、空间利用率高，四端操作同样是 O(1)，但容量固定、需要预分配或扩容，扩容时需要 O(n) 的搬迁。

典型应用：带步数上限的软件“撤销”功能

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度，典型例子就是软件中的“撤销（Undo）”功能。

我们知道，软件“撤销”功能通常使用栈来实现：系统把每次更改操作 push 进栈，执行撤销时 pop 出最近一次操作即可，这完全符合后进先出（LIFO）语义。然而受系统资源限制，软件通常会限制可撤销的步数——例如只允许保存最近 50 步。此时问题出现了：

• 当栈长度超过 50 时，软件必须从栈底（队首）删除最旧的那一步，让“可撤销窗口”始终只保留最近 50 次操作；
• 但标准栈只开放“栈顶进、栈顶出”，无法从底部删除元素，用栈无法直接实现该需求。

正确的做法是用双向队列替代栈：入栈对应 push_last，撤销对应 pop_last，而“超出 50 步时淘汰最旧操作”则对应 pop_first。需要注意的是，撤销的核心逻辑依然是“后进先出”，双向队列并没有改变这一原则，它只是让“限制撤销深度”这类额外逻辑得以灵活实现。从这一案例也可以看出，理解底层数据结构（栈、队列、双向队列）的能力边界，是设计此类系统的基础。

小结与延伸阅读

双向队列是“栈 + 队列”的集合体：六种核心操作（两端各三种：读、插、删）在真正的双向队列结构上均为 O(1)；若语言仅提供普通数组（如 JS/TS/Swift/Ruby），头部操作会退化为 O(n)；而 C 等语言未内置该结构，需要基于双向链表或环形数组自行实现，仓库源码可作为逐行对照的参考实现。

如果你希望进一步对比它与另两种线性结构的关系，可以阅读仓库中同章节的《Hello 算法》文档：

• 栈（stack）：了解仅一端操作的 LIFO 结构，是理解双向队列“多出来的那半边”的基础；
• 队列（queue）：了解一端入、一端出的 FIFO 结构，双向队列正是其对称扩展；
• 栈与队列章节小结：从整体视角梳理三类线性容器的异同。

相关多语言可运行代码统一存放在仓库 codes/*/chapter_stack_and_queue/ 目录下（文件名为 deque.*、linkedlist_deque.*、array_deque.*），每个文件均带有输出验证的 Driver Code，可 clone 仓库后在对应语言环境中直接编译运行，配合文档中的分步示意图观察指针移动与数组回绕过程，即可完整掌握双向队列。