Python deque：高效地進行雙端操作

一、概述

Python deque（雙端隊列）是Python標準庫collections模塊中的一個數據容器，它是一種具有線性表的性質，並且可以在隊列的兩端進行添加和刪除元素。與列表相比，deque除了支持隊列和棧的操作，還提供了旋轉、均攤複雜度為O（1）的appendleft和popleft方法。

有時候我們需要使用隊列，找到最前面/最後面的項目，或者需要從中刪除一些項目，那麼deque就可以派上用場。deque是一個雙端隊列，可以在隊列的頭部或尾部快速插入和刪除元素，具有高效地進行雙端操作的特性。

二、deque基礎使用

Deque實例可以從左端和右端添加或刪除元素。更具體來說，在deque開頭添加和刪除元素是O（1）的操作，但將一個元素插入中間是比較慢的，因為它需要移動內部元素以為新元素騰出空間。以下是deque的基本操作。

from collections import deque

d = deque()
d.append('a')           # 添加到隊列右側
d.appendleft('b')       # 添加到隊列左側
d.extend(['c', 'd'])    # 在隊列右側添加多個元素
d.extendleft(['e', 'f'])# 在隊列左側添加多個元素

print(d)                # deque(['f', 'e', 'b', 'a', 'c', 'd'])

d.pop()                 # 從隊列右側刪除元素
d.popleft()             # 從隊列左側刪除元素

print(d)                # deque(['b', 'a', 'c'])

三、deque的高效性

deque作為一個雙端隊列，在隊列兩端同時添加和刪除元素的時候具有高效性。例如，可以使用deque在一個大數組上模擬一個滑動窗口，下面我們通過一個例子來演示deque的高效性。

我們有一個長度為100,000的列表，要在其中找到長度為100的最大子序列。假設我們用列表進行求解的話，代碼會是這樣的：

a = [...]    # 長度為100,000的列表
k = 100

largest_sum = float('-inf')
for i in range(len(a)-k):
    current_sum = sum(a[i:i+k])
    largest_sum = max(largest_sum, current_sum)

在上面的代碼中，我們遍歷了列表中的每個子序列，並在其中找到了最大子序列。但是由於要遍歷很多子序列，時間複雜度為O（n * k）。

改用deque，我們可以將時間複雜度降至O（n），如下所示。

from collections import deque

a = [...]         # 長度為100,000的列表
k = 100

d = deque()
largest_sum = float('-inf')
for i, item in enumerate(a):
    # 彈出過期數據
    if len(d) == k:
        d.popleft()

    # 加入新數據
    d.append(item)

    if len(d) == k:
        current_sum = sum(d)
        largest_sum = max(largest_sum, current_sum)

在上面的代碼中，我們使用deque維護了一個長度為100的滑動窗口，時間複雜度為O（n），具有比上面使用列表更高的效率。

四、deque的其他用途

除了作為雙端隊列，deque還有其他的用途。比如，在操作系統中，deque被用來存儲系統調用。在圖形學和遊戲中，deque被用來存儲和管理動畫幀。在Web框架中，deque被用來存儲客戶請求和消息日誌。

五、總結

deque是Python標準庫中的一個雙端隊列，具有線性表的性質，並且可以在隊列的兩端進行添加和刪除元素。與列表相比，deque除了支持隊列和棧的操作，還提供了旋轉、均攤複雜度為O（1）的appendleft和popleft方法。deque可用於從隊列中查找最前面/最後面的項目，或者需要從中刪除一些項目，具有高效地進行雙端操作的特性。該數據容器在操作系統、遊戲等領域有廣泛應用。