python中的deque基本用法詳解

更新時間：2024年04月30日 11:17:17 作者：AI浩

Python?中的?deque是一個低級別的、高度優(yōu)化的雙端隊列,對于實現(xiàn)優(yōu)雅、高效的Pythonic隊列和堆棧很有用,這篇文章主要介紹了python中的deque基本用法的相關資料,需要的朋友可以參考下

摘要
示例1：基本使用
示例2：使用maxlen限制隊列長度
示例3：使用deque實現(xiàn)滑動窗口算法
示例 4: 使用 deque 實現(xiàn)旋轉(zhuǎn)數(shù)組
示例 5: 使用 deque 實現(xiàn)最大/最小棧
示例 6: 使用 deque 實現(xiàn)廣度優(yōu)先搜索（BFS）
總結(jié)

摘要

deque（雙端隊列）是Python標準庫collections模塊中的一個類，它支持從兩端快速添加和刪除元素。deque為固定大小或者可變大小的隊列提供了線程安全的實現(xiàn)，并且它比使用列表（list）來實現(xiàn)相同的功能更為高效

deque的主要特點和操作包括：

快速從兩端添加和刪除元素：deque在兩端添加和刪除元素的時間復雜度都是O(1)，而列表在列表頭部添加或刪除元素的時間復雜度是O(n)。
線程安全：deque的實例可以在多線程環(huán)境中安全使用，而不需要額外的鎖定。
可選的最大長度：可以通過maxlen參數(shù)來限制deque的最大長度。當deque已滿時，添加新元素會導致最早添加的元素被自動移除。

下面是deque的一些詳細示例：

示例1：基本使用

from collections import deque

# 創(chuàng)建一個空的deque
d = deque()

# 從右側(cè)添加元素
d.append('a')
d.append('b')
print(d)  # 輸出：deque(['a', 'b'])

# 從左側(cè)添加元素
d.appendleft('c')
print(d)  # 輸出：deque(['c', 'a', 'b'])

# 從右側(cè)移除元素
right_item = d.pop()
print(right_item)  # 輸出：'b'
print(d)  # 輸出：deque(['c', 'a'])

# 從左側(cè)移除元素
left_item = d.popleft()
print(left_item)  # 輸出：'c'
print(d)  # 輸出：deque(['a'])

示例2：使用maxlen限制隊列長度

from collections import deque

# 創(chuàng)建一個最大長度為3的deque
d = deque(maxlen=3)

# 添加元素
d.append('a')
d.append('b')
d.append('c')
print(d)  # 輸出：deque(['a', 'b', 'c'], maxlen=3)

# 繼續(xù)添加元素，最早添加的元素'a'將被移除
d.append('d')
print(d)  # 輸出：deque(['b', 'c', 'd'], maxlen=3)

# 嘗試從左側(cè)添加元素，同樣會移除最早添加的元素
d.appendleft('e')
print(d)  # 輸出：deque(['e', 'c', 'd'], maxlen=3)

示例3：使用deque實現(xiàn)滑動窗口算法

滑動窗口算法常用于數(shù)組或列表的子序列問題，如尋找最大/最小子序列和。

from collections import deque

def max_sliding_window(nums, k):
    # 使用deque保存窗口中的最大值索引
    window = deque()
    result = []

    for i in range(len(nums)):
        # 如果deque不為空且當前元素大于deque尾部元素對應的值，則移除尾部元素
        while window and nums[window[-1]] <= nums[i]:
            window.pop()
        # 添加當前元素的索引到deque
        window.append(i)
        # 當窗口大小達到k時，開始記錄窗口內(nèi)的最大值，并嘗試移動窗口左邊界
        if i >= k - 1:
            result.append(nums[window[0]])  # window[0]是當前窗口內(nèi)最大值的索引
            # 如果deque頭部的索引已經(jīng)不在當前窗口內(nèi)，則移除頭部索引
            if window[0] <= i - k:
                window.popleft()

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # 輸出：[3, 3, 5, 5, 6, 7]

在這個例子中，deque用于存儲當前窗口內(nèi)元素值的索引，通過維護一個遞減的索引隊列，我們可以快速找到窗口內(nèi)的最大值。當窗口向右滑動時，我們更新隊列并記錄每個窗口的最大值。

在Python中，collections.deque 是一個非常實用的雙向隊列實現(xiàn)，它可以高效地在隊列兩端添加或移除元素。以下是一些使用 deque 的示例：

示例 4: 使用 deque 實現(xiàn)旋轉(zhuǎn)數(shù)組

from collections import deque

def rotate_array(nums, k):
    dq = deque(nums)
    dq.rotate(-k)  # 逆時針旋轉(zhuǎn) k 位，如果是順時針旋轉(zhuǎn)則直接寫 k
    return list(dq)

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotated_nums = rotate_array(nums, k)
print(rotated_nums)  # 輸出: [5, 6, 7, 1, 2, 3, 4]

示例 5: 使用 deque 實現(xiàn)最大/最小棧

from collections import deque

class MaxStack:
    def __init__(self):
        self.stack = deque()
        self.max_stack = deque()

    def push(self, x):
        self.stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self):
        if self.stack:
            if self.stack[-1] == self.max_stack[-1]:
                self.max_stack.pop()
            return self.stack.pop()
        return None

    def top(self):
        return self.stack[-1] if self.stack else None

    def getMax(self):
        return self.max_stack[-1] if self.max_stack else None

# 使用示例
max_stack = MaxStack()
max_stack.push(5)
max_stack.push(7)
max_stack.push(1)
max_stack.push(5)
print(max_stack.getMax())  # 輸出: 7
max_stack.pop()
print(max_stack.top())  # 輸出: 5
print(max_stack.getMax())  # 輸出: 7

在這個例子中，MaxStack 類使用兩個 deque：一個用于存儲棧的元素，另一個用于存儲當前棧中的最大值。這樣，我們可以在常數(shù)時間內(nèi)獲取棧頂?shù)淖畲笾?/p>

示例 6: 使用 deque 實現(xiàn)廣度優(yōu)先搜索（BFS）

在圖的遍歷中，deque 常用于實現(xiàn)廣度優(yōu)先搜索（BFS）。

from collections import deque

def bfs(graph, root):
    visited = set()
    queue = deque([root])

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

# 圖的鄰接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')  # 輸出: A B C D E F

在上面的例子中，我們使用 deque 作為隊列來存儲待訪問的節(jié)點，實現(xiàn)了圖的廣度優(yōu)先搜索。

這些示例展示了 deque 在不同場景下的應用，從基本的隊列操作到更復雜的算法實現(xiàn)。deque 的靈活性和高效性使得它成為處理序列數(shù)據(jù)的強大工具。