Python Deque Methods: 雙端隊列的增刪查改操作

一、什麼是雙端隊列

在介紹Python中的雙端隊列（deque）方法之前，我們先來了解一下什麼是雙端隊列。

雙端隊列（Deque），全稱為雙端隊列(Double-Ended Queue)，是一種具有隊列和棧的性質的數據結構。

它的兩端都可以執行插入和刪除操作，因此它可以在隊列頭部和尾部兩端進行插入和刪除元素的操作。

它的特點是：插入和刪除元素的時間複雜度都是O(1)。

from collections import deque

# 創建雙端隊列
my_deque = deque()

# 在隊列的左側插入一個元素
my_deque.appendleft('a')

# 在隊列的右側插入一個元素
my_deque.append('b')

# 在隊列左側刪除一個元素，並返回該元素的值
left_pop = my_deque.popleft()

# 在隊列右側刪除一個元素，並返回該元素的值
right_pop = my_deque.pop()

二、雙端隊列的常用操作方法

1. append(item) 方法

在隊列的右側插入一個元素。

from collections import deque

# 創建雙端隊列
my_deque = deque()

# 在隊列的右側插入一個元素
my_deque.append('a')

2. appendleft(item) 方法

在隊列的左側插入一個元素。

from collections import deque

# 創建雙端隊列
my_deque = deque()

# 在隊列的左側插入一個元素
my_deque.appendleft('a')

3. clear() 方法

清空隊列中的所有元素。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c'])

# 清空隊列
my_deque.clear()

4. count(item) 方法

統計隊列中某個元素的出現次數。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'b', 'c', 'd'])

# 統計元素'b'的出現次數
b_count = my_deque.count('b')

5. extend(iterable) 方法

在隊列的右側依次插入可迭代對象中的所有元素。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b'])

# 將另一個可迭代對象的元素插入到隊列的右側
my_deque.extend(['c', 'd'])

6. extendleft(iterable) 方法

在隊列的左側依次插入可迭代對象中的所有元素。需要注意的是，元素的順序與可迭代對象的順序相反。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b'])

# 將另一個可迭代對象的元素插入到隊列的左側
my_deque.extendleft(['c', 'd'])  # 結果為 deque(['d', 'c', 'a', 'b'])

7. index(item, start=0, stop=len(queue)) 方法

在隊列中查找某個元素的位置，並返回它第一次出現的索引。

可以指定查找的區間，start和stop參數分別表示查詢區間的起始和終止位置，如果不指定，則默認搜索整個隊列。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c', 'd', 'e'])

# 查找元素'd'在隊列中第一次出現的索引
d_index = my_deque.index('d')

# 查找元素'd'在隊列中從第3個元素（不包括第3個元素）到隊列末尾的位置
d_index = my_deque.index('d', 3)

8. insert(index, item) 方法

在隊列的指定位置插入一個元素。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c'])

# 在指定位置插入元素
my_deque.insert(1, 'd')  # 結果為 deque(['a', 'd', 'b', 'c'])

9. pop() 方法

從隊列的右側刪除一個元素，並返回該元素的值。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c'])

# 從右側刪除一個元素並返回該元素的值
right_pop = my_deque.pop()

10. popleft() 方法

從隊列的左側刪除一個元素，並返回該元素的值。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c'])

# 從左側刪除一個元素並返回該元素的值
left_pop = my_deque.popleft()

11. remove(item) 方法

從隊列中刪除某個元素，如果有多個，則刪除第一個。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c', 'b'])

# 刪除第一個元素'b'
my_deque.remove('b')

12. reverse() 方法

翻轉隊列中的元素。

from collections import deque

# 創建雙端隊列，插入幾個元素
my_deque = deque(['a', 'b', 'c'])

# 反轉隊列中的元素
my_deque.reverse()  # 結果為 deque(['c', 'b', 'a'])

三、雙端隊列使用場景舉例

雙端隊列可以在很多場景中使用，下面以Python中的實現為例：

1. 最近最少使用（LRU）緩存算法

在Python中，collections模塊中的OrderedDict類就是一個經典的LRU緩存算法的實現。

OrderedDict類繼承了Python內置字典類的所有方法，同時還實現了一個__setitem__方法，用於在向字典中插入新元素時維護元素的順序。

當緩存達到最大容量時，在向OrderedDict中添加新的元素時，先刪除最早被訪問的元素，然後再添加新元素。

from collections import OrderedDict

# 創建最大容量為2的OrderedDict對象
cache = OrderedDict(maxlen=2)

# 向緩存中添加元素
cache[1] = 'a'
cache[2] = 'b'

# 打印當前緩存中的元素順序
print(cache.items())  # 結果為 dict_items([(1, 'a'), (2, 'b')])

# 再添加一個元素，由於緩存大小只有2，因此會刪除最早被訪問的元素1
cache[3] = 'c'

# 打印當前緩存中的元素順序
print(cache.items())  # 結果為 dict_items([(2, 'b'), (3, 'c')])

2. 廣度優先搜索算法

在廣度優先搜索算法中，需要使用隊列來維護待訪問的節點集合，而雙端隊列可以同時在隊列的頭尾進行插入和刪除操作，非常適合用於實現廣度優先搜索算法。

廣度優先搜索算法可以應用於很多領域，包括自然語言處理、計算機視覺、圖像處理等。

from collections import deque

# 定義圖的鄰接表表示
graph = {
    'A':{'B'},
    'B':{'C','D'},
    'C':{'D'},
    'D':{'C'},
    'E':{'D'}
}

# 廣度優先搜索算法，計算從起點'A'到終點'D'的最短路徑
def bfs(start, end):
    # 隊列中保存路徑
    queue = deque()
    queue.append([start])
    # 保存已經遍歷的節點
    visited = set()

    while queue:
        # 取出路徑
        path = queue.popleft()
        # 取出路徑的最後一個節點
        node = path[-1]
        if node == end:
            # 如果已經到達終點，則返迴路徑
            return path
        if node not in visited:
            # 如果當前節點沒有被訪問過，則標記為已訪問
            visited.add(node)
            # 在所有鄰居中增加一條新路徑，並把這些新路徑全部加入到隊列中
            for neighbor in graph[node]:
                new_path = path + [neighbor]
                queue.append(new_path)

# 測試bfs函數
print(bfs('A', 'D'))  # 結果為 ['A', 'B', 'D']

四、結語

利用雙端隊列可以快速高效地實現很多常見的數據結構和算法，比如實現隊列、棧、LRU緩存算法和廣度優先搜索算法等。

同時，Python中的collections模塊中也提供了非常豐富的雙端隊列方法，幫助我們輕鬆地實現各種數據結構和算法，提高生產效率。