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，因為它不僅高效，而且經過了充分的測試和優化。