Deque

双向队列（Deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。在双向队列中，元素可以从两端插入，也可以从两端删除，因此它比传统的队列和栈更加灵活。Python中的collections模块提供了一个双向队列的实现。

一. 双向队列的基本操作

双向队列主要有以下几种基本操作，每种操作都有其特定的用途。

pushFirst()：将元素添加至队首
pushLast()：将元素添加至队尾
popFirst()：删除队首元素
popLast()：删除队尾元素
peekFirst()：访问队首元素
peekLast()：访问队尾元素

1. Python中的双向队列实现
   Python中可以使用collections.deque来实现双向队列。

# 导入双向队列类
from collections import deque

# 初始化双向队列
dq = deque()

# 元素入队
dq.append(2)          # 添加至队尾
dq.appendleft(1)      # 添加至队首

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

# 元素出队
dq.popleft()          # 队首元素出队
dq.pop()              # 队尾元素出队

# 获取双向队列的长度
size = len(dq)

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

二. 基于双向链表的实现

与队列类似，双向队列可以基于双向链表来实现。在双向链表的基础上，我们可以在两端添加和删除节点。

1. 双向链表节点定义
   在定义双向链表的节点时，除了需要一个next指针指向后继节点，还需要一个prev指针指向前驱节点。

   class ListNode: def __init__(self, val: int): self.val = val # 节点的值 self.next = None # 后继节点引用 self.prev = None # 前驱节点引用

2. 队列操作
   基于双向链表的双向队列，我们可以实现各种队列操作，如push_first，push_last，pop_first，pop_last等。

   class LinkedListDeque: # ... 其他代码 ... def push_first(self, num: int): """队首入队""" # ... 实现代码 ... def push_last(self, num: int): """队尾入队""" # ... 实现代码 ... def pop_first(self) -> int: """队首出队""" # ... 实现代码 ... def pop_last(self) -> int: """队尾出队""" # ... 实现代码 ...

三. 基于数组的实现

除了双向链表，我们还可以使用数组来实现双向队列。通过维护两个指针，一个指向队首，一个指向队尾，我们可以在数组的两端进行入队和出队操作。

1. 基于数组的双向队列定义
   在基于数组的双向队列中，我们需要一个固定大小的数组来存储元素，以及一些变量来存储队列的状态，如队首指针和队列的大小。

   class ArrayDeque: def __init__(self, capacity: int): self.__nums = [0] * capacity # 存储元素的数组 self.__front = 0 # 队首指针 self.__size = 0 # 队列的大小

2. 队列操作
   基于数组的双向队列，我们可以实现各种队列操作，如push_first，push_last，pop_first，pop_last等。

   class ArrayDeque: # ... 其他代码 ... def push_first(self, num: int): """队首入队""" if self.__size == len(self.__nums): print("双向队列已满") return self.__front = (self.__front - 1 + len(self.__nums)) % len(self.__nums) # 更新队首指针 self.__nums[self.__front] = num # 将元素添加至队首 self.__size += 1 # 更新队列大小 def push_last(self, num: int): """队尾入队""" if self.__size == len(self.__nums): print("双向队列已满") return rear = (self.__front + self.__size) % len(self.__nums) # 计算队尾指针 self.__nums[rear] = num # 将元素添加至队尾 self.__size += 1 # 更新队列大小 def pop_first(self) -> int: """队首出队""" if self.__size == 0: raise IndexError("双向队列为空") num = self.__nums[self.__front] # 获取队首元素 self.__front = (self.__front + 1) % len(self.__nums) # 更新队首指针 self.__size -= 1 # 更新队列大小 return num def pop_last(self) -> int: """队尾出队""" if self.__size == 0: raise IndexError("双向队列为空") rear = (self.__front + self.__size - 1) % len(self.__nums) # 计算队尾指针 num = self.__nums[rear] # 获取队尾元素 self.__size -= 1 # 更新队列大小 return num

   四. 双向队列的应用

   双向队列因其灵活性，可以应用在多个场景中，例如可以实现具有撤销功能的软件。

在某些软件中，我们通常使用栈来实现撤销功能，即每次更改都会被推送到栈中，然后通过弹出栈来实现撤销。但由于系统资源的限制，我们通常会限制撤销的步数。当栈的长度超过限制时，我们需要在栈底执行删除操作，这时就需要使用双向队列来实现。

1. 撤销功能的实现
   下面是一个简单的使用双向队列实现的带有撤销功能的文本编辑器的例子：

   from collections import deque class TextEditor: def __init__(self): self.text = [] # 存储文本 self.undo_deque = deque(maxlen=10) # 存储撤销的操作，最多存储10个 def insert(self, char: str): """插入字符，并将操作存储到撤销队列中""" self.text.append(char) self.undo_deque.append(('insert', char)) def delete(self): """删除字符，并将操作存储到撤销队列中""" if self.text: char = self.text.pop() self.undo_deque.append(('delete', char)) def undo(self): """撤销操作""" if self.undo_deque: operation, char = self.undo_deque.pop() if operation == 'insert': self.text.pop() else: self.text.append(char)

   通过使用双向队列，我们不仅可以实现撤销操作，还可以在撤销队列达到最大长度时自动丢弃最旧的操作，从而更加有效地管理系统资源。

   五. 双向队列的扩展与深入应用

   双向队列的灵活性使其在许多复杂场景下变得非常有用。接下来，我们将探讨一些更加复杂和实用的双向队列应用案例。
2. 滑动窗口最大值
   双向队列经常用于解决滑动窗口问题。例如，给定一个数组和一个整数k，我们可以用双向队列找到每个窗口的最大值。

   from collections import deque def maxSlidingWindow(nums, k): if not nums: return [] res = [] # 存储结果 dq = deque() # 存储索引的双向队列 for i, n in enumerate(nums): # 保持队列的单调递减 while dq and nums[dq[-1]] < n: dq.pop() dq.append(i) # 当窗口左边界超过队首元素索引时，弹出队首元素 if i - dq[0] >= k: dq.popleft() # 当窗口长度达到k时，将队首元素加入结果列表 if i >= k - 1: res.append(nums[dq[0]]) return res

   在这个例子中，我们维护一个单调递减的双向队列，这样可以确保队首元素始终是当前窗口的最大值。
3. 用双向队列实现LRU缓存
   LRU（Least Recently Used）缓存是一种常见的缓存策略，其中最近最少使用的项首先被移除。双向队列可以用于实现这个算法。

   from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() # 使用有序字典存储缓存项 def get(self, key: int) -> int: if key not in self.cache: return -1 value = self.cache.pop(key) # 获取值并从字典中移除该项 self.cache[key] = value # 将该项添加到字典末尾，表示最近使用 return value def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.pop(key) elif len(self.cache) >= self.capacity: self.cache.popitem(last=False) # 移除最久未使用的项 self.cache[key] = value # 将新项添加到字典末尾

   在这个例子中，我们使用Python的OrderedDict来实现双向队列，并利用它的有序性来跟踪最近使用的元素。
4. 几何计算：计算凸包
   凸包问题是计算几何中的经典问题。在这个问题中，我们要找到一组二维点的凸包。凸包可以被视为包含所有点的最小凸多边形。

我们可以使用Graham扫描算法来解决这个问题，并用双向队列来存储凸包的顶点。双向队列在这里的好处是，它允许我们在两端都能进行有效的添加和删除操作。

Graham 扫描算法和双向队列实现凸包
下面是使用Python和双向队列实现的Graham扫描算法：

from collections import deque
from typing import List, Tuple

def orientation(p: Tuple[int, int], q: Tuple[int, int], r: Tuple[int, int]) -> int:
    """
    判断三个点的方向
    如果为正，则p-q-r是逆时针方向
    如果为负，则p-q-r是顺时针方向
    如果为0，则p-q-r是共线的
    """
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

def graham_scan(points: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """
    使用Graham扫描算法计算凸包
    """
    n = len(points)
    if n < 3:
        return []  # 少于三个点无法构成多边形
    
    # 找到y坐标最小的点，如果有多个，则取x坐标最小的那个
    pivot = min(points, key=lambda p: (p[1], p[0]))
    
    # 根据极角对点进行排序，极角相同则按距离排序
    points.sort(key=lambda p: (atan2(p[1]-pivot[1], p[0]-pivot[0]), p))
    
    # 初始化双向队列并放入前三个点
    dq = deque(points[:3])
    
    for i in range(3, n):
        while len(dq) > 1 and orientation(list(dq)[-2], list(dq)[-1], points[i]) <= 0:
            dq.pop()  # 如果新点和双向队列的最后两个点不构成左转，则弹出最后一个点
        dq.append(points[i])
    
    return list(dq)  # 返回凸包的顶点

# 例子
points = [(0,0), (2,2), (1,1), (3,1), (4,0), (4,4), (3,3), (2,4), (1,3)]
print(graham_scan(points))  # 输出凸包的顶点

在这个实现中，我们使用双向队列dq来存储凸包的顶点，这样可以在两端都进行高效的添加和删除操作，确保算法的高效性。

六. Python双向队列的额外特性

Python的collections.deque除了基本操作外，还提供了一些额外的有用功能，如rotate，reverse和maxlen等。

1. Rotate操作
   rotate方法可以轻松实现队列的旋转。例如，对于一个双向队列d = deque([1, 2, 3, 4, 5])，执行d.rotate(2)会得到deque([4, 5, 1, 2, 3])。

   from collections import deque d = deque([1, 2, 3, 4, 5]) d.rotate(2) # 右旋转2个位置 print(d) # 输出: deque([4, 5, 1, 2, 3])

2. Reverse操作
   reverse方法可以将双向队列中的元素顺序颠倒，这个操作是原地操作，并且运行时间为O(n)。

   from collections import deque d = deque([1, 2, 3, 4, 5]) d.reverse() # 颠倒双向队列中的元素 print(d) # 输出: deque([5, 4, 3, 2, 1])

3. Maxlen属性
   在创建deque对象时，可以通过maxlen参数来指定双向队列的最大长度。如果忽略此参数，双向队列的长度就是无限的。如果设置了maxlen，双向队列就变成了一个固定大小的队列，当新的元素入队时，相同数量的元素会从另一端出队。

   from collections import deque d = deque(maxlen=3) # 创建一个最大长度为3的双向队列 d.append(1) d.append(2) d.append(3) print(d) # 输出: deque([1, 2, 3], maxlen=3) d.append(4) # 添加新元素，导致另一端的元素被推出 print(d) # 输出: deque([2, 3, 4], maxlen=3)

七. 总结

双向队列是一种非常灵活和多功能的数据结构，可以高效地在两端进行插入和删除操作。我们在本文中详细探讨了Python中的双向队列，介绍了其基本操作、实现方式、以及一些高级应用和特性。

• 我们学习了如何使用Python的collections.deque进行基本的双向队列操作，包括在两端的插入、删除和访问操作。
• 我们探讨了双向队列的两种主要实现方法：基于双向链表和基于数组，并且展示了如何使用Python实现它们。
• 我们深入研究了双向队列的一些应用场景，如滑动窗口问题、LRU缓存和几何计算，说明了它在解决实际问题时的巨大价值。
• 最后，我们还学习了Python双向队列的一些额外特性，如rotate、reverse和maxlen等。
  通过深入了解双向队列的实现和应用，我们可以更加灵活和高效地使用这个数据结构来解决各种编程问题，提高我们的编程能力和解题水平。希望本文能为大家提供双向队列方面的有用知识，帮助大家更好地掌握这个重要的数据结构。