双端队列

双端队列（Deque，全称 Double-Ended Queue）是一种允许在队列的前端（Front）和后端（Rear）同时进行插入和删除操作的线性数据结构。它结合了栈（Stack）和队列（Queue）的特性，提供了更灵活的数据操作方式。

概述

双端队列是一种抽象数据类型（ADT），支持以下基本操作：

• 在队列的前端或后端插入元素（`push_front`、`push_back`）
• 从队列的前端或后端删除元素（`pop_front`、`pop_back`）
• 查看队列的前端或后端元素（`peek_front`、`peek_back`）
• 检查队列是否为空（`isEmpty`）
• 获取队列的大小（`size`）

双端队列可以用于实现其他数据结构，如栈（仅使用前端操作）或队列（仅使用一端插入，另一端删除）。

基本操作示例

以下是双端队列的基本操作示例（以Python为例）：

from collections import deque

# 初始化双端队列
d = deque()

# 后端插入
d.append(1)    # deque([1])
d.append(2)    # deque([1, 2])

# 前端插入
d.appendleft(3) # deque([3, 1, 2])

# 后端删除
print(d.pop())  # 输出: 2, deque([3, 1])

# 前端删除
print(d.popleft()) # 输出: 3, deque([1])

实现方式

双端队列可以通过多种方式实现，常见的有：

基于动态数组的实现

动态数组（如Python的`list`）可以用于实现双端队列，但前端插入和删除操作的时间复杂度为O(n)，因为需要移动元素。

基于双向链表的实现

双向链表是最自然的实现方式，所有操作的时间复杂度均为O(1)。

以下是双向链表的简单实现（伪代码）：

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def push_front(self, value):
        # 实现前端插入
        pass

    def push_back(self, value):
        # 实现后端插入
        pass

    def pop_front(self):
        # 实现前端删除
        pass

    def pop_back(self):
        # 实现后端删除
        pass

时间复杂度分析

不同实现方式的时间复杂度如下：

时间复杂度比较

操作	动态数组	双向链表
`push_front`	O(n)	O(1)
`push_back`	O(1)	O(1)
`pop_front`	O(n)	O(1)
`pop_back`	O(1)	O(1)
`peek_front`	O(1)	O(1)
`peek_back`	O(1)	O(1)

实际应用案例

双端队列在计算机科学中有广泛的应用：

1. 撤销操作：文本编辑器中的撤销功能可以使用双端队列实现，最近的操作放在前端。 2. 滑动窗口算法：用于解决数组/字符串的子数组问题。 3. 工作窃取算法：在多线程编程中，双端队列用于任务分配。 4. 回文检查：可以从两端同时检查字符是否匹配。

滑动窗口最大值示例

以下是一个使用双端队列解决滑动窗口最大值问题的示例：

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        # 移除超出窗口范围的元素
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 移除小于当前元素的元素
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# 示例
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)) 
# 输出: [3, 3, 5, 5, 6, 7]

变种与扩展

1. 输入受限双端队列：限制一端只能插入，另一端可以插入和删除。 2. 输出受限双端队列：限制一端只能删除，另一端可以插入和删除。 3. 循环双端队列：使用固定大小的数组实现，通过模运算实现循环。

可视化示例

以下是一个双端队列操作的mermaid图表示例：

graph LR subgraph Deque A[3] <--> B[1] <--> C[2] end

初始状态：`deque([3, 1, 2])`

1. `pop()` 删除后端元素2 2. `popleft()` 删除前端元素3 3. 最终状态：`deque([1])`

数学性质

双端队列的数学性质可以用以下公式表示：

对于长度为$n$的双端队列$D$，有：

解析失败 (未知函数“\begin{cases}”): {\displaystyle \begin{cases} D.\text{push\_front}(x) \Rightarrow D = [x] \cup D \\ D.\text{push\_back}(x) \Rightarrow D = D \cup [x] \\ D.\text{pop\_front}() \Rightarrow D = D[1..n-1] \\ D.\text{pop\_back}() \Rightarrow D = D[0..n-2] \end{cases} }

练习问题

1. 使用双端队列实现一个栈。 2. 使用双端队列实现一个队列。 3. 编写一个程序检查字符串是否是回文（使用双端队列）。 4. 实现一个循环双端队列。

参见

• 栈
• 队列
• 链表
• 抽象数据类型