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，因为它不仅高效，而且经过了充分的测试和优化。