Hello 算法中的双向队列（Deque）：六大 O(1) 操作、多语言标准库用法与双向链表/环形数组实现

双向队列（Double-Ended Queue，简称 Deque）是队列的对称扩展：允许在队首和队尾两个方向执行插入与删除，从而同时覆盖栈（LIFO）和队列（FIFO）的应用场景，并带来更高自由度。本文以《Hello 算法》教材中的双向队列章节为核心，系统梳理双向队列的六个基本操作及其时间复杂度、十余种语言的标准库用法与陷阱，并深入解析仓库中基于双向链表与环形数组的两种实现源码，最后说明一个典型实战场景——步数受限的“撤销”功能。

双向队列的基本操作与时间复杂度

在普通队列中，我们仅能在头部删除元素或在尾部添加元素。而双向队列将“入队”和“出队”这两个动作复制到两端，提供了更高的灵活性。其常用操作及效率如下（具体方法名因语言而异，下表为教材给出的统一抽象）：

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

上述效率成立的前提是选用合适的底层数据结构（双向链表或环形数组），以及语言标准库中真正实现了双端语义的容器。下面各语言示例即为教材原文给出的可运行代码。

各语言标准库中的双向队列

Python：collections.deque

Python 标准库提供原生 deque，六个操作全部 $O(1)$：

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

对应的完整可运行示例（含打印驱动代码）见 codes/python/chapter_stack_and_queue/deque.py，教材原文中的这段代码与该文件的驱动部分一一对应。

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：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 当作双向队列使用

/* 初始化双向队列 */
// 在 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

注意 Go 的 list 包返回的是节点指针而非元素值，Front()/Back() 之后需要通过 node.Value.(type) 取出实际数据。

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();

没有内置双向队列的语言：用数组模拟，但要注意队首操作的 $O(n)$ 代价

JavaScript、TypeScript、Ruby 均没有内置的双端队列，教材建议把数组当作双端队列使用，并特别提示队首操作（unshift/shift）由于需要整体搬移元素，时间复杂度为 $O(n)$：

/* 初始化双向队列 */
// 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 与 Ruby 的写法与此完全同构（push/unshift/pop/shift，Ruby 用 << 替代 push），因此队首入队与队首出队同样退化为 $O(n)$。

Swift 同样没有内置双向队列类，教材给出的模拟方案是 Array，并明确标注 removeFirst() 的复杂度为 $O(n)$：

/* 初始化双向队列 */
// 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

Dart 与 Kotlin 则相反，它们的集合 API 原生支持双端语义，六个操作均可高效完成：

/* 初始化双向队列 */
// 在 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;

/* 初始化双向队列 */
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()

而 C 语言未提供内置双向队列容器，只能自行实现——这正是下一节两种底层实现的意义所在。

综合来看，各语言的双端能力可以分为三类：

类别	语言	推荐容器	队首操作复杂度
原生双向队列	Python、C++、Rust、Dart	deque / std::deque / VecDeque / Queue	$O(1)$
双端链表	Java、C#、Go、Kotlin	LinkedList 实现 Deque	$O(1)$
数组模拟	JavaScript、TypeScript、Ruby、Swift	数组 + unshift/shift 等	$O(n)$

仓库中每一章都提供了多语言的平行实现，上述代码可在 codes/python/chapter_stack_and_queue/deque.py、codes/cpp/chapter_stack_and_queue/deque.cpp 等对应语言目录下找到并直接运行。

基于双向链表的实现

回顾队列一章：单向链表适合队列，因为它方便地删除头节点（出队）并在尾节点后追加新节点（入队）。但双向队列的头部和尾部都要执行入队和出队，也就是要实现“对称方向”的操作，因此选用双向链表作为底层结构：将链表的头节点与尾节点视为队首与队尾，在两端都可以 $O(1)$ 地添加或删除节点。

仓库中的 Python 实现见 codes/python/chapter_stack_and_queue/linkedlist_deque.py。核心设计是：push 与 pop 各由一个统一方法加方向参数完成，四个对外方法只是薄封装：

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

    def __init__(self):
        self._front: ListNode | None = None  # 头节点 front
        self._rear: ListNode | None = None  # 尾节点 rear
        self._size: int = 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 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 push_first(self, num: int):
        """队首入队"""
        self.push(num, True)

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

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

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

从源码结构看，几个细节保证了正确性与效率：

• 空队列特判：首个元素入队时令 _front 与 _rear 同时指向新节点（linkedlist_deque.py），避免空指针解引用。
• 对称的双向指针维护：队首入队时新节点成为 front 并接管 prev 链；队首出队时先把 front.next 的 prev 置空，再把 front 后移——两端各改常数次指针，故全部操作 $O(1)$。
• 防御性检查：pop 与 peek_first/peek_last 在空队列时抛出 IndexError("双向队列为空")，把非法访问显式暴露给调用方。
• 封装复用：push_first/push_last/pop_first/pop_last 全部委托给带 is_front 参数的统一方法，逻辑只写一遍，两端行为严格对称。

C 语言的等价实现见 codes/c/chapter_stack_and_queue/linkedlist_deque.c，用 struct DoublyListNode { int val; *next; *prev; } 与 LinkedListDeque { front, rear, queSize } 两个结构体表达同样的设计，并手工管理 malloc/free（delLinkedListdeque 逐节点释放）；C++ 版本见 codes/cpp/chapter_stack_and_queue/linkedlist_deque.cpp。

链表实现的优势是不需要预设容量、可动态增长；代价是每个节点都要额外存储 prev 指针，且缓存局部性不如连续内存。

基于环形数组的实现

与基于数组实现队列的思路一致，也可以用环形数组实现双向队列。相对队列实现，只需要增加“队首入队”与“队尾出队”两个方法——这正是教材原文的定位。仓库中的 Python 实现见 codes/python/chapter_stack_and_queue/array_deque.py：

class ArrayDeque:
    """基于环形数组实现的双向队列"""

    def __init__(self, capacity: int):
        """构造方法"""
        self._nums: list[int] = [0] * capacity
        self._front: int = 0
        self._size: int = 0

    def index(self, i: int) -> int:
        """计算环形数组索引"""
        # 通过取余操作实现数组首尾相连
        # 当 i 越过数组尾部后，回到头部
        # 当 i 越过数组头部后，回到尾部
        return (i + self.capacity()) % self.capacity()

    def push_first(self, num: int):
        """队首入队"""
        if self._size == self.capacity():
            print("双向队列已满")
            return
        # 队首指针向左移动一位
        # 通过取余操作实现 front 越过数组头部后回到尾部
        self._front = self.index(self._front - 1)
        # 将 num 添加至队首
        self._nums[self._front] = num
        self._size += 1

    def push_last(self, num: int):
        """队尾入队"""
        if self._size == self.capacity():
            print("双向队列已满")
            return
        # 计算队尾指针，指向队尾索引 + 1
        rear = self.index(self._front + self._size)
        # 将 num 添加至队尾
        self._nums[rear] = num
        self._size += 1

    def pop_first(self) -> int:
        """队首出队"""
        num = self.peek_first()
        # 队首指针向后移动一位
        self._front = self.index(self._front + 1)
        self._size -= 1
        return num

    def pop_last(self) -> int:
        """队尾出队"""
        num = self.peek_last()
        self._size -= 1
        return num

从源码结构看，该实现有三个关键设计点：

• index() 是环形语义的唯一入口：(i + capacity) % capacity 同时处理了正向越界（尾部回绕到头部）与负向越界（front - 1 为负时回绕到尾部），使得 push_first 中 front 向左扩展只需写一行（array_deque.py）。+ capacity 这一项专门保证负数取余的正确性。
• front + size 双状态量，而不是 front + rear 双指针：push_last 把元素写入 index(front + size) 位置，peek_last 读取 index(front + size - 1) 位置。由于队尾指针是“计算”而非“维护”的，pop_last 甚至不需要移动任何指针，只把 size 减一即可（array_deque.py）——这是 $O(1)$ 的队尾出队。
• 满与空的状态判断分离：入队前检查 size == capacity 并提示“双向队列已满”；出队/访问前由 peek 在空队列时抛出 IndexError。由于使用 size 计数而非“front == rear 即满/空”的歧义判断，满与空可以准确区分。

C 语言版本 codes/c/chapter_stack_and_queue/array_deque.c 的 ArrayDeque 结构体（nums/front/queSize/queCapacity）与 dequeIndex 环形索引函数与 Python 版逐行对应，C++ 版本见 codes/cpp/chapter_stack_and_queue/array_deque.cpp。

两种实现的取舍

维度	双向链表实现	环形数组实现
容量	动态增长，无需预设	构造时固定 capacity，满时拒绝入队
空间开销	每节点额外存储 prev/next 指针	连续内存，仅 capacity 个元素槽位
缓存局部性	差（节点分散分配）	好（顺序访问）
六个操作复杂度	均 $O(1)$	均 $O(1)$
语言标准库对应物	Java LinkedList、Go list、C# LinkedList	Python deque、C++ std::deque、Rust VecDeque

可以推断：容量可控、追求吞吐的场景（如固定窗口的缓冲、撤销栈）更适合环形数组；长度不可预估、需要频繁在两端交替操作的场景更适合链表。标准库容器内部大多采用“分段连续内存”这类介于两者之间的设计，但本文两种手写实现已完整覆盖核心思想。

典型应用：步数受限的“撤销”功能

双向队列兼具栈与队列的逻辑，因此可以实现这两者的所有应用场景，同时提供更高的自由度。教材给出的一个具体案例是软件的“撤销”（Undo）功能：

1. 常规做法是把每次用户更改操作 push 到栈中，通过 pop 实现逐步撤销，遵循先入后出原则。
2. 但出于系统资源限制，软件通常限制可撤销的步数（例如仅保留最近 50 步）。
3. 当栈中记录超过 50 条时，必须在最旧的一端（即栈底/队首）丢弃记录。普通栈只允许操作栈顶，无法实现这一端删除。
4. 此时应改用双向队列替代栈：撤销的核心逻辑（pop_last 取最近操作）仍然是 LIFO，而超限时用 pop_first 丢弃最旧记录，正好利用了双向队列“两端均可删除”的自由度。

用仓库中的 LinkedListDeque 表达即为：push_last(op) 记录操作，pop_last() 撤销最近一步，当 size() > 50 时执行 pop_first() 淘汰最旧一步——三个操作全部 $O(1)$，完整实现了“有界撤销栈”语义。

小结

• 双向队列提供 push_first/push_last/pop_first/pop_last/peek_first/peek_last 六个 $O(1)$ 操作，是栈与队列的统一超集。
• 语言选型上：Python deque、C++ std::deque、Rust VecDeque 是原生双端容器；Java/C#/Go/Kotlin 可把双端链表当作 Deque 使用；JS/TS/Swift/Ruby 用数组模拟时须记住队首 unshift/shift 为 $O(n)$。
• 手写实现两条路线：双向链表靠 front/rear 双端指针完成对称操作；环形数组靠 (i + capacity) % capacity 索引回绕，且仅维护 front + size 即可让队尾出队零指针移动。
• 实战上，双向队列可替代“有界撤销栈”等栈无法覆盖的场景，同时保留 LIFO 的核心语义。

本章全部代码可对照 docs/chapter_stack_and_queue/deque.md 原文，并在 codes/python/chapter_stack_and_queue/ 等目录中按语言运行验证。