Python中如何实现双端队列Dequeue

Python中如何实现双端队列Dequeue

双端队列（Dequeue，全称Double-Ended Queue）是一种具有队列和栈性质的数据结构，允许在队列的两端进行插入和删除操作。与普通队列（只能在队尾插入，队头删除）不同，双端队列可以在队头和队尾同时进行插入和删除操作。这种灵活性使得双端队列在很多场景下非常有用，例如实现滑动窗口、缓存管理等。

在Python中，双端队列可以通过多种方式实现。本文将介绍如何使用Python内置的collections.deque模块以及如何手动实现一个双端队列。

1. 使用collections.deque实现双端队列

Python的标准库collections模块中提供了一个名为deque的类，专门用于实现双端队列。deque类提供了高效的双端操作，时间复杂度为O(1)。

1.1 创建双端队列

首先，我们需要导入deque类：

from collections import deque 

然后，我们可以通过以下方式创建一个双端队列：

d = deque() 

也可以初始化时传入一个可迭代对象：

d = deque([1, 2, 3, 4]) 

1.2 在队头和队尾插入元素

deque提供了append()和appendleft()方法，分别用于在队尾和队头插入元素：

d.append(5) # 在队尾插入元素5 d.appendleft(0) # 在队头插入元素0 

1.3 在队头和队尾删除元素

deque提供了pop()和popleft()方法，分别用于在队尾和队头删除元素：

d.pop() # 删除队尾元素 d.popleft() # 删除队头元素 

1.4 其他常用操作

• len(d)：获取队列的长度。
• d[index]：访问队列中的元素。
• d.extend(iterable)：在队尾批量插入元素。
• d.extendleft(iterable)：在队头批量插入元素。
• d.rotate(n)：将队列中的元素向右旋转n步（如果n为负数，则向左旋转）。

1.5 示例代码

from collections import deque # 创建双端队列 d = deque([1, 2, 3, 4]) # 在队尾插入元素 d.append(5) print(d) # 输出: deque([1, 2, 3, 4, 5]) # 在队头插入元素 d.appendleft(0) print(d) # 输出: deque([0, 1, 2, 3, 4, 5]) # 删除队尾元素 d.pop() print(d) # 输出: deque([0, 1, 2, 3, 4]) # 删除队头元素 d.popleft() print(d) # 输出: deque([1, 2, 3, 4]) # 旋转队列 d.rotate(2) print(d) # 输出: deque([3, 4, 1, 2]) 

2. 手动实现双端队列

虽然collections.deque已经提供了高效的双端队列实现，但为了深入理解双端队列的工作原理，我们可以手动实现一个简单的双端队列。

2.1 使用列表实现双端队列

Python的列表（list）可以用于实现双端队列，但由于列表在头部插入和删除元素的时间复杂度为O(n)，因此效率较低。不过，对于小规模数据，列表仍然是一个可行的选择。

2.1.1 实现代码

class Deque: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def append(self, item): self.items.append(item) def appendleft(self, item): self.items.insert(0, item) def pop(self): if self.is_empty(): raise IndexError("pop from empty deque") return self.items.pop() def popleft(self): if self.is_empty(): raise IndexError("popleft from empty deque") return self.items.pop(0) def __len__(self): return len(self.items) def __getitem__(self, index): return self.items[index] def __repr__(self): return f"Deque({self.items})" 

2.1.2 示例代码

d = Deque() # 在队尾插入元素 d.append(1) d.append(2) print(d) # 输出: Deque([1, 2]) # 在队头插入元素 d.appendleft(0) print(d) # 输出: Deque([0, 1, 2]) # 删除队尾元素 d.pop() print(d) # 输出: Deque([0, 1]) # 删除队头元素 d.popleft() print(d) # 输出: Deque([1]) 

2.2 使用双向链表实现双端队列

为了在双端队列的两端都实现O(1)时间复杂度的插入和删除操作，我们可以使用双向链表来实现双端队列。

2.2.1 实现代码

class Node: def __init__(self, value): self.value = value self.next = None self.prev = None class Deque: def __init__(self): self.head = None self.tail = None self.size = 0 def is_empty(self): return self.size == 0 def append(self, value): new_node = Node(value) if self.is_empty(): self.head = self.tail = new_node else: self.tail.next = new_node new_node.prev = self.tail self.tail = new_node self.size += 1 def appendleft(self, value): new_node = Node(value) if self.is_empty(): self.head = self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node self.size += 1 def pop(self): if self.is_empty(): raise IndexError("pop from empty deque") value = self.tail.value if self.size == 1: self.head = self.tail = None else: self.tail = self.tail.prev self.tail.next = None self.size -= 1 return value def popleft(self): if self.is_empty(): raise IndexError("popleft from empty deque") value = self.head.value if self.size == 1: self.head = self.tail = None else: self.head = self.head.next self.head.prev = None self.size -= 1 return value def __len__(self): return self.size def __repr__(self): values = [] current = self.head while current: values.append(current.value) current = current.next return f"Deque({values})" 

2.2.2 示例代码

d = Deque() # 在队尾插入元素 d.append(1) d.append(2) print(d) # 输出: Deque([1, 2]) # 在队头插入元素 d.appendleft(0) print(d) # 输出: Deque([0, 1, 2]) # 删除队尾元素 d.pop() print(d) # 输出: Deque([0, 1]) # 删除队头元素 d.popleft() print(d) # 输出: Deque([1]) 

3. 总结

本文介绍了如何在Python中实现双端队列。首先，我们使用collections.deque模块快速实现了一个高效的双端队列。然后，我们手动实现了两种双端队列：基于列表的实现和基于双向链表的实现。虽然collections.deque已经提供了高效的双端队列实现，但手动实现有助于我们更好地理解双端队列的工作原理。

在实际应用中，建议优先使用collections.deque，因为它不仅高效，而且经过了充分的测试和优化。