Hello 算法：双端队列（Deque）原理、双向链表与环形数组实现及多语言实战指南

2026-09-07 22:58:08作者：霍妲思

本文是《Hello 算法》栈与队列章节中**双端队列（Double-Ended Queue，简称 deque）**主题的技术指南。它围绕 en/docs/chapter_stack_and_queue/deque.md 展开，面向希望在队列基础上进一步掌握"两端皆可进出"数据结构、并理解其两种底层实现（双向链表 / 环形数组）的读者。读完本文，你将能够：描述双端队列六大核心操作的时间复杂度；在 Python、C++、Java 等主流语言中直接使用语言内置的 deque 容器；从零手写基于双向链表与基于环形数组的 deque，并理解两者在扩容、缓存友好性上的差异。

双端队列是什么

在普通队列（Queue）中，我们只能在队尾（rear）添加元素、在队首（front）删除元素；而栈（Stack）则只允许在同一端进出。双端队列打破了这种单向约束——它同时允许在队首与队尾进行元素的添加与删除，因此在灵活度上是"栈 + 队列"的超集。

只使用 push_last() + pop_first()（队尾进、队首出），deque 就退化为一个普通 FIFO 队列；
只使用 push_last() + pop_last()（同端进出），deque 就退化为一个栈；
当需要同时具备两端操作能力（如"限制步数的撤销"功能）时，deque 是比单个栈更合适的选择。

双端队列的常用操作

与队列类似，deque 的核心接口只有六种，且只要底层实现得当，全部可以在 $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)$

注意上表的前提是"底层实现得当"。原文档特别强调一个易被忽略的坑：部分语言没有内置真正的双端队列，只能用动态数组（Array/List）模拟，此时在队首一侧的 unshift / shift / removeFirst 类操作会退化为 $O (n)$ 。仓库中文档 en/docs/chapter_stack_and_queue/deque.md 及后续多语言代码中均用注释明确标注了这一限制，例如 Swift、JavaScript、TypeScript、Ruby 的实现都注明队首插入为 $O (n)$ 。

各语言内置双端队列的用法对照

deque 是数据结构教材与工程中都很常见的容器，主流语言几乎都提供了开箱即用的实现，但类名与方法名差异很大。下表汇总了文档覆盖的全部语言的内置容器及方法名映射（左 / 右分别对应队首 / 队尾操作）：

语言	容器类型	队首插入	队尾插入	队首删除	队尾删除	访问两端
Python	`collections.deque`	`appendleft`	`append`	`popleft`	`pop`	`deq[0]` / `deq[-1]`
C++	`std::deque`	`push_front`	`push_back`	`pop_front`	`pop_back`	`front()` / `back()`
Java	`Deque`（常配 `LinkedList`）	`offerFirst`	`offerLast`	`pollFirst`	`pollLast`	`peekFirst` / `peekLast`
C#	`LinkedList<T>`（作为 deque 使用）	`AddFirst`	`AddLast`	`RemoveFirst`	`RemoveLast`	`First.Value` / `Last.Value`
Go	`container/list.List`	`PushFront`	`PushBack`	`Remove(front)`	`Remove(rear)`	`Front()` / `Back()`
Swift	用 `Array` 模拟	`insert(_:at: 0)` O(n)	`append`	`removeFirst()` O(n)	`removeLast`	`first` / `last`
JavaScript	用 `Array` 模拟	`unshift` O(n)	`push`	`shift` O(n)	`pop`	`arr[0]` / `arr[len-1]`
TypeScript	用 `Array` 模拟	`unshift` O(n)	`push`	`shift` O(n)	`pop`	`arr[0]` / `arr[len-1]`
Dart	`Queue`（本身就是 deque）	`addFirst`	`addLast`	`removeFirst`	`removeLast`	`first` / `last`
Rust	`std::collections::VecDeque`	`push_front`	`push_back`	`pop_front`	`pop_back`	`front()` / `back()`
Kotlin	`LinkedList` / `ArrayDeque`	`offerFirst`	`offerLast`	`pollFirst`	`pollLast`	`peekFirst` / `peekLast`
Ruby	用 `Array` 模拟	`unshift` O(n)	`<<`(push)	`shift` O(n)	`pop`	`first` / `last`
C / Zig	无内置，需自行实现	见下文"手写实现"部分

以文档中的 Python 代码（collections.deque）为例，其运行逻辑如下：

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（完整驱动示例见 en/codes/cpp/chapter_stack_and_queue/deque.cpp）：

#include <deque>
using namespace std;

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 侧文档推荐通过 Deque<Integer> deque = new LinkedList<>(); 声明，配合 offerFirst/offerLast 与 pollFirst/pollLast 使用；Go 标准库 container/list 的双向链表天然支持两端操作，仓库以测试文件形式给出了完整驱动：见 en/codes/go/chapter_stack_and_queue/deque_test.go，其中 TestDeque、TestArrayDeque、TestLinkedListDeque 三个用例分别覆盖了内置 list、自实现环形数组版、自实现链表版三种 deque 的完整流程。

值得留意的是：deque 的原语操作究竟绑定哪个"端"的名字，纯属语言约定。例如 Java 的 offerLast/pollFirst 是"队列"语义，而同样底层容器上的 push/pop 则可能是"栈"语义，读者切换语言时务必以官方文档为准。

基于双向链表的双端队列实现

为什么普通单向链表不够用

此前用单向链表实现队列时很方便：头节点天然支持删除（出队），在尾节点之后插入新节点也只需 $O (1)$ 。但 deque 需要在两端同时支持"增"与"删"，单向链表在"删除尾节点"时无法拿到前驱节点，必须从头遍历。因此仓库与文档给出的方案是改用**双向链表（doubly linked list）**作为底层结构，让每个节点同时持有 next 与 prev 两个指针。

实现思路：把双向链表的头节点与尾节点分别视作 deque 的队首与队尾，从而在两端都获得 $O (1)$ 的增删能力。

链表版的完整代码

下面以仓库的 Python 实现为例（完整文件：en/codes/python/chapter_stack_and_queue/linkedlist_deque.py），核心设计是：

节点类 ListNode 含 val、next、prev 三个字段；
队列类维护 _front（头节点）、_rear（尾节点）、_size（长度）三个成员；
push 与 pop 内部用布尔参数 is_front 统一"前端 / 后端"两条分支，再各自封装为 push_first / push_last 等公开方法，避免代码重复。

class ListNode:
    """双向链表节点"""
    def __init__(self, val: int):
        self.val: int = val
        self.next: ListNode | None = None  # 后继节点引用
        self.prev: ListNode | None = None  # 前驱节点引用


class LinkedListDeque:
    """基于双向链表实现的双向队列"""

    def __init__(self):
        self._front: ListNode | None = None  # 头节点 front
        self._rear: ListNode | None = None   # 尾节点 rear
        self._size: int = 0                  # 双向队列的长度

    def size(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def push(self, num: int, is_front: bool):
        """入队操作"""
        node = ListNode(num)
        # 若链表为空，则令 front 和 rear 都指向 node
        if self.is_empty():
            self._front = self._rear = node
        # 队首入队操作
        elif is_front:
            # 将 node 添加至链表头部
            self._front.prev = node
            node.next = self._front
            self._front = node  # 更新头节点
        # 队尾入队操作
        else:
            # 将 node 添加至链表尾部
            self._rear.next = node
            node.prev = self._rear
            self._rear = node   # 更新尾节点
        self._size += 1         # 更新队列长度

    def push_first(self, num: int):  # 队首入队
        self.push(num, True)

    def push_last(self, num: int):   # 队尾入队
        self.push(num, False)

    def pop(self, is_front: bool) -> int:
        """出队操作"""
        if self.is_empty():
            raise IndexError("双向队列为空")
        # 队首出队操作
        if is_front:
            val: int = self._front.val
            # 删除头节点
            fnext: ListNode | None = self._front.next
            if fnext is not None:
                fnext.prev = None
                self._front.next = None
            self._front = fnext      # 更新头节点
        # 队尾出队操作
        else:
            val: int = self._rear.val
            # 删除尾节点
            rprev: ListNode | None = self._rear.prev
            if rprev is not None:
                rprev.next = None
                self._rear.prev = None
            self._rear = rprev       # 更新尾节点
        self._size -= 1              # 更新队列长度
        return val

    def pop_first(self) -> int:      # 队首出队
        return self.pop(True)

    def pop_last(self) -> int:       # 队尾出队
        return self.pop(False)

    def peek_first(self) -> int:     # 访问队首元素
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._front.val

    def peek_last(self) -> int:      # 访问队尾元素
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._rear.val

C 语言版本在仓库中同样完整可用，en/codes/c/chapter_stack_and_queue/linkedlist_deque.c 额外体现了手动内存管理细节：newDoublyListNode/delDoublyListNode 负责单个节点的分配与释放，delLinkedListdeque 析构函数在释放队列结构前会先遍历释放全部节点，避免内存泄漏；出队 pop 在删除头/尾节点时通过 fNext->prev = NULL、rPrev->next = NULL 先断开指针再 free，这正是 C 语言相比 GC 语言必须多考虑的一步。各版本的分步插删过程（push_last → push_first → pop_last → pop_first）可对照文档中的步骤图理解。

基于环形数组的双端队列实现

用取模运算"卷"出一个环

数组版 deque 的思路与环形数组实现队列一致：让 front 指向队首元素，用 (front + size) 计算出队尾的下一个写入位置，并通过 index(i) = (i + capacity) % capacity 让下标越过数组边界时自动"绕回"到另一端，从而复用已被出队元素腾出的空间。

在此基础上，双端队列只需追加"队首入队"与"队尾出队"两个方法：

push_first：先把 front 左移一位（front = index(front - 1)），再写入新元素；
pop_last：直接返回 peek_last() 并让 size--，无需移动指针。

数组版的完整代码

以仓库 C++ 实现为例（完整文件：en/codes/cpp/chapter_stack_and_queue/array_deque.cpp）：

class ArrayDeque {
  private:
    vector<int> nums; // 用于存储双向队列元素的数组
    int front;        // 队首指针，指向队首元素
    int queSize;      // 双向队列长度

  public:
    ArrayDeque(int capacity) {
        nums.resize(capacity);
        front = queSize = 0;
    }

    int capacity() { return nums.size(); }
    int size() { return queSize; }
    bool isEmpty() { return queSize == 0; }

    /* 计算环形数组索引 */
    int index(int i) {
        return (i + capacity()) % capacity();
    }

    /* 队首入队 */
    void pushFirst(int num) {
        if (queSize == capacity()) {
            cout << "双向队列已满" << endl;
            return;
        }
        // 队首指针向左移动一位
        front = index(front - 1);
        nums[front] = num;
        queSize++;
    }

    /* 队尾入队 */
    void pushLast(int num) {
        if (queSize == capacity()) {
            cout << "双向队列已满" << endl;
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        int rear = index(front + queSize);
        nums[rear] = num;
        queSize++;
    }

    /* 队首出队 */
    int popFirst() {
        int num = peekFirst();
        front = index(front + 1);   // 队首指针向后移动一位
        queSize--;
        return num;
    }

    /* 队尾出队 */
    int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    /* 访问队首元素 */
    int peekFirst() {
        if (isEmpty())
            throw out_of_range("双向队列为空");
        return nums[front];
    }

    /* 访问队尾元素 */
    int peekLast() {
        if (isEmpty())
            throw out_of_range("双向队列为空");
        int last = index(front + queSize - 1);
        return nums[last];
    }
};

代码中有三处关键细节值得重点理解：

"队首入队"必须先移动指针再写入：push_first 先 front = index(front - 1) 腾出位置，这正是取模运算的妙处——当 front 已是下标 0 时，index(-1) 会得到 capacity - 1，元素被"绕"到数组末端；
push_last 用 front + size 定位尾插位置，配合 peek_last 中的 front + size - 1 完成队尾元素的读写，两个公式是理解环形数组的关键；
数组版存在容量上限：与链表版不同，当 queSize == capacity() 时入队会被拒绝（打印"已满"提示）。链表版按需分配节点、无此问题，代价是每次 push 都要执行一次节点内存分配、且节点在内存中分散不利于缓存。

Python 版（en/codes/python/chapter_stack_and_queue/array_deque.py）与 Go 测试版（en/codes/go/chapter_stack_and_queue/deque_test.go 中的 TestArrayDeque）逻辑完全一致，可作为对照阅读。

两种实现方案的对比小结

对比维度	双向链表实现	环形数组实现
插入 / 删除复杂度	两端均为 $O (1)$	两端均为 $O (1)$
内存分配	每个节点独立分配，push 有分配开销	一次性连续分配，空间局部性好、缓存友好
容量	无固定上限，随节点增减	有固定 `capacity`，满时需"扩容+搬移"或拒绝写入
额外存储	每个节点需 `prev` 指针，占用更多内存	仅需 front / size 两个整数状态
空队列出队	抛出异常或返回哨兵值	同样需处理空队列异常

从工程角度概括：读多写多、追求缓存命中的场景倾向数组版；元素频繁增删、长度难以预估的场景倾向链表版。两种实现文档中均以多步图示给出，可结合 deque.md 原文中的步骤图逐一推演。

双端队列的典型应用

一个自然的追问是：既然普通队列和栈都够用了，为什么还需要 deque？文档给出了极具代表性的应用场景——有限步数的"撤销（undo）"功能：

撤销功能的常规做法是用栈：系统把每一次修改操作 push 进栈，撤销时 pop，天然符合 LIFO 语义；
但受系统资源限制，软件通常限制可撤销步数（例如只保存最近 50 步）。当栈长度超过 50 时，就必须在栈底（相当于队首）删掉最旧的一条记录——普通栈做不到这一点；
于是用 deque 替代栈：核心逻辑依然是 LIFO 的栈操作，但当容量达到上限时，从队首（栈底）把最旧的记录 pop 掉即可，栈和队列的能力由此合二为一。

除此之外，deque 在工程中也是"滑动窗口求最值"这类经典算法题的常用载体（队首存候选、队尾淘汰过期元素），其双端特性使得"窗口右移 + 过期元素出队 + 新元素单调入队"都能在摊还 $O (1)$ 内完成。感兴趣可进一步阅读本章其余内容：队列与栈，把三种受限线性结构的边界彻底理清。

小结与延伸阅读

双端队列 = 队首可进出 + 队尾可进出，是栈与队列的超集，其六种核心操作均可做到 $O (1)$ ；
语言内置容器命名差异大，且 Swift / JavaScript / TypeScript / Ruby 等以数组模拟的版本在队首操作上是 $O (n)$ ，需在性能敏感场景下自实现；
两种手写方案——双向链表版（linkedlist_deque.py）与环形数组版（array_deque.py）——仓库中均有 Python、C++、C、Go、Java、Rust、Swift、Kotlin、Dart 等多语言等价实现，读者可选择熟悉语言对照阅读，并留意 C 语言版本中的手动内存管理与各版本驱动测试。