Python deque：高效的雙端隊列操作

一、deque介紹

在程序設計中，隊列是常用的數據結構之一。Python標準庫提供了deque模塊，旨在提供在兩端高效執行添加和刪除操作的雙端隊列數據結構。

deque內部實現了一個雙向鏈表，使得插入和刪除操作在兩端的時間複雜度均為O(1)。與列表list相比，deque保留了隊列的性質，可以高效地從隊列的兩端執行添加和刪除操作，而無需執行線性時間內的拆移操作。

下面我們看下如何使用Python deque模塊創建一個雙端隊列：

from collections import deque

d = deque()

二、deque基本操作

我們一般使用append()和appendleft()操作添加元素，使用pop()和popleft()操作刪除元素。

下面我們看下這幾個操作的示例代碼：

from collections import deque

d = deque([1, 2, 3])
d.append(4)
print(d)  # 輸出：deque([1, 2, 3, 4])
d.appendleft(5)
print(d)  # 輸出：deque([5, 1, 2, 3, 4])
d.pop()
print(d)  # 輸出：deque([5, 1, 2, 3])
d.popleft()
print(d)  # 輸出：deque([1, 2, 3])

需要注意的是，在Python deque模塊中，如果想要在鏈表的任意位置插入或刪除元素，需要使用insert()和remove()這兩個操作。不過從性能的角度考慮，始終建議在兩端進行添加和刪除操作。

三、deque高級操作

1. rotate()操作

rotate()操作可以將deque從右端移動指定個數的元素到左端，或者從左端移動指定個數的元素到右端。這個操作有一個非常有用的特點：當向右旋轉時，最右側的元素會移到最左側；當向左旋轉時，最左側的元素會移到最右側。

下面我們看下rotate()操作的示例代碼：

from collections import deque

d = deque([1, 2, 3, 4, 5])
d.rotate(1)
print(d)  # 輸出：deque([5, 1, 2, 3, 4])
d.rotate(2)
print(d)  # 輸出：deque([3, 4, 5, 1, 2])

2. maxlen參數

deque還有一個非常有用的參數maxlen，可以指定deque的大小。當deque中元素的數量達到maxlen時，再執行添加操作，deque會從另一端刪除元素。

下面我們看下maxlen參數的示例代碼：

from collections import deque

d = deque(maxlen=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)

3. 其他操作

除了上面提到的幾個基本和高級的操作，Python deque模塊還包括了許多其他的操作。比如count()可以計算某個元素在deque中出現的次數，extend()和extendleft()可以讓我們將一個序列中的元素添加到deque中等等。

下面我們看下count()和extend()操作的示例代碼：

from collections import deque

d = deque([1, 2, 3, 4, 1, 2])
print(d.count(1))  # 輸出：2
print(d.count(5))  # 輸出：0
d.extend([5, 6])
print(d)  # 輸出：deque([1, 2, 3, 4, 1, 2, 5, 6])

四、總結

Python deque模塊提供了高效的雙向隊列數據結構，使得我們在從隊列的兩端執行添加和刪除操作的時候更加方便和高效。deque中還包括一些高級操作，尤其是rotate()操作和maxlen參數，可以為我們的程序帶來更多的靈活性。