编辑“︁双端队列”︁

{{Note|本文介绍的是计算机科学中的'''双端队列'''（Deque）。关于其他用法，请参阅相关条目。}}

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

== 概述 ==

双端队列是一种抽象数据类型（ADT），支持以下基本操作：
* 在队列的前端或后端插入元素（`push_front`、`push_back`）
* 从队列的前端或后端删除元素（`pop_front`、`pop_back`）
* 查看队列的前端或后端元素（`peek_front`、`peek_back`）
* 检查队列是否为空（`isEmpty`）
* 获取队列的大小（`size`）

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

== 基本操作示例 ==

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

<syntaxhighlight lang="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])
</syntaxhighlight>

== 实现方式 ==

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

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

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

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 时间复杂度分析 ==

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

{| class="wikitable"
|+ 时间复杂度比较
! 操作 !! 动态数组 !! 双向链表
|-
| `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. '''回文检查'''：可以从两端同时检查字符是否匹配。

=== 滑动窗口最大值示例 ===

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

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

== 变种与扩展 ==

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

== 可视化示例 ==

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

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

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

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

== 数学性质 ==

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

对于长度为<math>n</math>的双端队列<math>D</math>，有：

<math>
\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}
</math>

== 练习问题 ==

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

== 参见 ==

* [[栈]]
* [[队列]]
* [[链表]]
* [[抽象数据类型]]

[[Category:数据结构]]
[[Category:算法]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]