python之collection-deque

1.什麼是雙端隊列

deque的英文意思是Double-Ended Queue，從字面的意思來看，他就是一個雙向隊列。我們使用list存儲數據的時候，按索引訪問元素很快，因為list是線性存儲，數據量很大的時候在列表頭插入和刪除元素的效率就會很慢。為什麼list效率低呢?

• 因為list有append()和insert(index,value)兩個添加方法，append()方法只能在在列表的尾部追加元素，而insert(index)雖然能在指定的位置去添加元素，但是他需要去遍歷list才行所以時間複雜度為o(N)。
• 而list中的刪除有del names[index],pop()或者pop(index),remove(value)可以看出list刪除除了pop()[刪除列表末尾的元素]之外，剩下的都需要去遍歷list列表，所以時間複雜度是o(N)。

deque是為了在兩端高效實現插入和刪除操作的雙向列表，適合用於隊列和棧：deque除了實現list的append()和pop()外，還支持appendleft()和popleft()，這樣就可以非常高效地往頭部或者尾部添加或刪除元素。

2.列表與雙端隊列

雙端隊列支持線程安全，在雙端隊列的任何一端執行添加和刪除操作，它們的內存效率幾乎相同（時間複雜度為O(1)）。

雖然list也支持類似的操作，但是它對定長列表的操作表現很不錯，而當遇到pop(0)和insert(0, v)這樣既改變了列表的長度又改變其元素位置的操作時，其時間複雜度就變為O(n)了。

在雙端隊列中最好不使用切片(如果使用deque進行切片的話會拋出異常)和索引(和列表一樣的使用，雖然效果上是一樣的，但是可能效率上還是列表的索引效率更高一些)，你可以用popleft和appendleft方法，雙端隊列對這些操作做了優化。在兩端的索引訪問時間複雜度為O(1)，但是訪問中間元素的時間複雜度為O(n)，速度較慢，對於快速隨機的訪問，還是用列表代替。

列表用於隨機訪問和定長數據的操作，包括切片，而雙端隊列適用於在兩端壓入或彈出元素，索引的效率可能低於列表，同時也不支持切片。

3.雙端隊列的使用

extendleft()方法，他是把列表中的元素進行迭代，先取出第一個元素，然後放在左邊，然後再去取出下一個，重複執行，就得到了最終的結果。

from collections import dequed = deque([1,2,3])d.extendleft([a,b,c])print(d)deque([c, b, a, 1, 2, 3])

其他類似list的操作方法

from collections import dequed = deque([a,b,c,d,e,f])print(d)print(len(d))#獲取雙端隊列的長度print(d[-1])#類似list的索引訪問,使用方法與列表的索引一樣# d.reverse()# print(d)#反轉輸出print(d.count(a))#輸出元素出現的次數print(d.index(e))print(d.index(c,0,3)) #指定查找區間#插入元素d.insert(0,1)print(d)#remove(value)#刪除指定元素d.remove(a)print(d)deque([a, b, c, d, e, f])6f142deque([1, a, b, c, d, e, f])deque([1, b, c, d, e, f])

注意：如果使用deque進行切片的話會拋出異常

TypeError: sequence index must be integer, not slice，中文翻譯的意思就是：類型錯誤:序列索引必須是整數，而不是「切片」。

from collections import dequed = deque([1,2,3,4])print(d[:-1])Traceback (most recent call last): File "G:/Python源碼/dequetest.py", line 3, in <module> print(d[:-1])TypeError: sequence index must be integer, not slice

rotate（把右邊元素放到左邊，默認為1）

from collections import dequed = deque([1,2,3,4,5])d.rotate()#默認為1d.rotate(1)print(d)deque([5, 1, 2, 3, 4])

參數>0的時候是從右往左放元素

from collections import dequed = deque([1,2,3,4,5])d.rotate(2)print(d)deque([4, 5, 1, 2, 3])

參數<0的時候是從左往右放元素

from collections import dequed = deque([1,2,3,4,5])d.rotate(-2)print(d)deque([3, 4, 5, 1, 2])

還有一個值得關注的地方，初始化deque的時候可以給他傳一個參數maxlen，如果deque中的元素超過maxlen的值，那麼就會從deque中的一邊去刪除元素，也就是deque始終保持maxlen最大長度的元素，如果超過了就會自動把以前的元素彈出(刪除)。當然這些追加都是沒有問題的。

from collections import dequed = deque([1,2,3],maxlen = 3)print(d)d.append(4)print(d)d.appendleft(5)print(d)deque([1, 2, 3], maxlen=3)deque([2, 3, 4], maxlen=3)deque([5, 2, 3], maxlen=3)

當時如果我使用insert(index,value)就會拋出異常。當然這種情況出現在我隊列中的元素==maxlen的情況下使用insert才會拋出異常。如果元素!=maxlen的時候insert沒有問題。我覺得可能在指定位置插入的話，他不知道去刪除那一端的元素。

from collections import dequed = deque([1,2,3],maxlen = 3)# d.insert(0,a)# print(d)d.insert(1,b)print(d)Traceback (most recent call last): File "G:/Python源碼/collections_deque.py", line 5, in <module> d.insert(1,b)IndexError: deque already at its maximum size

當然刪除操作肯定不會有什麼問題。

from collections import dequed = deque([1,2,3],maxlen = 3)print(d)d.pop()print(d)d.popleft()print(d)d.remove(2)print(d)deque([1, 2, 3], maxlen=3)deque([1, 2], maxlen=3)deque([2], maxlen=3)deque([], maxlen=3)

推薦閱讀：