Python 的雙端隊列：實現高效的隊列和堆棧

目錄

Python 的雙端隊列入門

有效地彈出和附加項目

訪問雙端隊列中的隨機項

使用 deque 構建高效隊列

探索 deque 的其他特性

限制最大項目數：maxlen

旋轉項目：.rotate()

一次添加多個項目：.extendleft()

使用 deque 的 Sequence-Like 特性

將 Python 的雙端隊列付諸行動

保留頁面歷史

在線程之間共享數據

模擬 tail 命令

結論

如果您經常在 Python 中使用列表，那么您可能知道當您需要在列表的左端彈出和附加項目時，它們的執行速度不夠快。Python 的collections模塊提供了一個名為的類deque，該類專門設計用于提供快速且節省內存的方法來從底層數據結構的兩端追加和彈出項目。

Pythondeque是一種低級且高度優化的雙端隊列，可用于實現優雅、高效和 Pythonic 的隊列和堆棧，這是計算中最常見的類似列表的數據類型。

在本教程中，您將學習：

如何deque在代碼中創建和使用 Python

如何有效地從 a 的兩端附加和彈出項目deque

如何使用deque構建高效的隊列和堆棧

什么時候值得使用deque而不是list

為了更好地理解這些主題，您應該了解使用 Python列表的基礎知識。對queues和stacks有一個大致的了解也會對您有所幫助。

最后，您將編寫一些示例，引導您了解 的一些常見用例deque，它是 Python 最強大的數據類型之一。

Python 入門?deque

在 Python 列表的右端添加和彈出項目通常是高效的操作。如果使用大O符號的時間復雜度，那么你可以說他們是?（1）。但是，當 Python 需要重新分配內存以增加底層列表以接受新項目時，這些操作會變慢并且可能變成O?(?n?)。

此外，眾所周知，在 Python 列表的左端追加和彈出項目是O?(?n?) 速度的低效操作。

因為Python列表提供了兩種操作與.append()和.pop()，他們可作為堆棧和隊列。但是，您之前看到的性能問題會顯著影響應用程序的整體性能。

Pythondeque是Python 2.4 中添加到collections模塊的第一個數據類型。這種數據類型是專門為克服Python 列表中的和效率問題而設計的。.append().pop()

雙端隊列是類似序列的數據類型，設計為棧和隊列的泛化。它們支持對數據結構兩端的內存高效和快速的追加和彈出操作。

注意：?deque發音為“deck”。這個名字代表了d?ouble-?é?nded闕UE。

deque對象兩端的追加和彈出操作是穩定且同樣高效的，因為雙端隊列是作為雙向鏈表實現的。此外，對雙端隊列的追加和彈出操作也是線程安全和內存高效的。這些特性使得雙端隊列對于在 Python 中創建自定義堆棧和隊列特別有用。

如果您需要保留上次看到的項目的列表，雙端隊列也是一種可行的方法，因為您可以限制雙端隊列的最大長度。如果這樣做，那么一旦雙端隊列已滿，當您在另一端添加新項目時，它會自動丟棄一端的項目。

以下是對主要特點的總結deque：

存儲任何數據類型的項目

是可變數據類型

支持與運營商的會員操作in

支持索引，如a_deque[i]

不支持切片，就像在?a_deque[0:2]

支持內置在上序列和iterables操作功能，例如len()，sorted()，reversed()，和更

不支持就地排序

支持正反迭代

支持酸洗?pickle

確保在兩端進行快速、內存高效和線程安全的彈出和追加操作

創建deque實例是一個簡單的過程。您只需要導入dequefromcollections并使用可選iterable參數作為參數調用它：

>>> from collections import deque >>> # Create an empty deque >>> deque() deque([]) >>> # Use different iterables to create deques >>> deque((1, 2, 3, 4)) deque([1, 2, 3, 4]) >>> deque([1, 2, 3, 4]) deque([1, 2, 3, 4]) >>> deque(range(1, 5)) deque([1, 2, 3, 4]) >>> deque("abcd") deque(['a', 'b', 'c', 'd']) >>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4} >>> deque(numbers.keys()) deque(['one', 'two', 'three', 'four']) >>> deque(numbers.values()) deque([1, 2, 3, 4]) >>> deque(numbers.items()) deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])

如果您在deque不提供 aniterable作為參數的情況下進行實例化，那么您會得到一個空的雙端隊列。如果您提供并輸入iterable，則deque使用其中的數據初始化新實例。初始化從左到右使用deque.append().

在deque初始化采用以下兩個可選參數：

iterable?持有一個提供初始化數據的迭代。

maxlen持有的整數數目，指定雙端隊列的最大長度。

如前所述，如果您不提供 an?iterable，則會得到一個空的雙端隊列。如果您為 提供值maxlen，那么您的雙端隊列將最多存儲maxlen項目。

最后，您還可以使用無序可迭代對象（例如set）來初始化您的雙端隊列。在這些情況下，對于最終雙端隊列中的項目，您將沒有預定義的順序。

有效地彈出和附加項目

deque和之間最重要的區別list是前者允許您在序列的兩端執行有效的追加和彈出操作。的deque專用類實現.popleft()和.appendleft()方法，關于直接序列的左端操作：

>>>

>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.popleft() 1 >>> numbers.popleft() 2 >>> numbers deque([3, 4]) >>> numbers.appendleft(2) >>> numbers.appendleft(1) >>> numbers deque([1, 2, 3, 4])

在這里，您使用.popleft()和.appendleft()分別刪除和添加值到 的左端numbers。這些方法特定于 的設計deque，您不會在list.

就像list，deque還提供.append()與.pop()方法對序列的右端操作。但是，.pop()行為不同：

>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.pop() 4 >>> numbers.pop(0) Traceback (most recent call last): File "", line 1, in TypeError: pop() takes no arguments (1 given)

在這里，.pop()刪除并返回雙端隊列中的最后一個值。該方法不將索引作為參數，因此您不能使用它從雙端隊列中刪除任意項目。您只能使用它來移除和返回最右邊的項目。

正如您之前了解到的，deque是作為雙向鏈表實現的。因此，給定雙端隊列中的每個項目都持有一個指向序列中下一個和上一個項目的引用（指針）。

雙向鏈表使得從任一端添加和彈出項目都可以輕松高效地操作。這是可能的，因為只需要更新指針。因此，這兩個操作具有相似的性能，O?(1)。它們在性能方面也是可預測的，因為不需要重新分配內存和移動現有項目以接受新項目。

從常規 Python 列表的左端追加和彈出項目需要移動所有項目，這最終是一個O?(?n?) 操作。此外，將項目添加到列表的右端通常需要 Python 重新分配內存并將當前項目復制到新的內存位置。之后，它可以添加新項目。這個過程需要更長的時間才能完成，追加操作從O?(1) 到O?(?n?)。

考慮以下將項目附加到序列左端的性能測試，dequevs?list：

# time_append.py from collections import deque from time import perf_counter TIMES = 10_000 a_list = [] a_deque = deque() def average_time(func, times): total = 0.0 for i in range(times): start = perf_counter() func(i) total += (perf_counter() - start) * 1e9 return total / times list_time = average_time(lambda i: a_list.insert(0, i), TIMES) deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES) gain = list_time / deque_time print(f"list.insert() {list_time:.6} ns") print(f"deque.appendleft() {deque_time:.6} ns ({gain:.6}x faster)")

在此腳本中，average_time()計算執行func給定次數的函數 (?)times所需的平均時間。如果從命令行運行腳本，則會得到以下輸出：

$ python time_append.py list.insert() 3735.08 ns deque.appendleft() 238.889 ns (15.6352x faster)

在這個特定示例中，.appendleft()在 adeque上比.insert()在 a 上快幾倍list。注意deque.appendleft()是O?(1)，這意味著執行時間是恒定的。但是，list.insert()列表的左端是O?(?n?)，這意味著執行時間取決于要處理的項目數。

在此示例中，如果您增加 的值TIMES，那么您將獲得更高的時間測量值，list.insert()但 的穩定（恒定）結果deque.appendleft()。如果您想對雙端隊列和列表的 pop 操作嘗試類似的性能測試，那么您可以展開下面的練習塊，并在完成后將您的結果與Real Python的結果進行比較。

練習：測試deque.popleft()與list.pop(0)性能顯示/隱藏

解決方案：測試deque.popleft()與list.pop(0)性能顯示/隱藏

該deque數據類型被設計為保證高效附加并且在序列的任一端彈出的操作。它非常適合解決需要在 Python 中實現隊列和堆棧數據結構的問題。

訪問隨機項目?deque

Pythondeque返回的可變序列與列表的工作方式非常相似。除了允許您有效地從它們的末端附加和彈出項目之外，雙端隊列還提供了一組類似列表的方法和其他類似序列的操作來處理任意位置的項目。以下是其中一些：

您可以使用這些方法和技術來處理deque對象內任何位置的項目。以下是如何做到這一點：

>>> from collections import deque >>> letters = deque("abde") >>> letters.insert(2, "c") >>> letters deque(['a', 'b', 'c', 'd', 'e']) >>> letters.remove("d") >>> letters deque(['a', 'b', 'c', 'e']) >>> letters[1] 'b' >>> del letters[2] >>> letters deque(['a', 'b', 'e'])

在這里，你先插入"c"到letters的位置2。然后"d"使用.remove().?雙端隊列還允許索引訪問項目，您在此處使用這些項目"b"在 index 處訪問1。最后，您可以使用del?關鍵字從雙端隊列中刪除任何現有項目。請注意，.remove()允許您按值刪除項目，而按索引del刪除項目。

即使deque對象支持索引，它們也不支持切片。換句話說，你不能提取切片從現有的雙端隊列使用切片語法，[start:stop:step]如你有定期列表：

>>>

>>> from collections import deque >>> numbers = deque([1, 2, 3, 4, 5]) >>> numbers[1:3] Traceback (most recent call last): File "", line 1, in TypeError: sequence index must be integer, not 'slice'

Deques 支持索引，但有趣的是，它們不支持切片。當您嘗試從雙端隊列中獲取切片時，您會得到一個TypeError.?通常，對鏈表執行切片效率低下，因此該操作不可用。

到目前為止，您已經看到這deque與list.?然而，whilelist是基于數組的，deque是基于雙向鏈表的。

deque實現為雙向鏈表的背后有一個隱藏的成本：訪問、插入和刪除任意項目不是有效的操作。為了執行它們，解釋器必須遍歷雙端隊列，直到到達所需的項目。因此，它們是O?(?n?) 而不是O?(1) 操作。

這是一個腳本，顯示了在處理任意項目時雙端隊列和列表的行為：

# time_random_access.py from collections import deque from time import perf_counter TIMES = 10_000 a_list = [1] * TIMES a_deque = deque(a_list) def average_time(func, times): total = 0.0 for _ in range(times): start = perf_counter() func() total += (perf_counter() - start) * 1e6 return total / times def time_it(sequence): middle = len(sequence) // 2 sequence.insert(middle, "middle") sequence[middle] sequence.remove("middle") del sequence[middle] list_time = average_time(lambda: time_it(a_list), TIMES) deque_time = average_time(lambda: time_it(a_deque), TIMES) gain = deque_time / list_time print(f"list {list_time:.6} μs ({gain:.6}x faster)") print(f"deque {deque_time:.6} μs")

此腳本會在雙端隊列和列表中間插入、刪除和訪問項目。如果您運行該腳本，則會得到如下所示的輸出：

$ python time_random_access.py list 63.8658 μs (1.44517x faster) deque 92.2968 μs

雙端隊列不是像列表那樣的隨機訪問數據結構。因此，從雙端隊列中間訪問元素比在列表上做同樣的事情效率低。這里的主要內容是雙端隊列并不總是比列表更有效。

Pythondeque針對序列兩端的操作進行了優化，因此在這方面它們始終比列表更好。另一方面，列表更適合隨機訪問和固定長度的操作。以下是雙端隊列和列表在性能方面的一些差異：

在列表的情況下，.append()當解釋器需要增長列表以接受新項目時，已攤銷受內存重新分配影響的性能。此操作需要將當前所有項復制到新的內存位置，這會顯著影響性能。

此摘要可以幫助您為手頭的問題選擇合適的數據類型。但是，請確保在從列表切換到雙端隊列之前分析您的代碼。兩者都有各自的性能優勢。

建立高效的隊列?deque

正如您已經了解到的，它deque是作為雙端隊列實現的，它提供了堆棧和隊列的泛化。在本節中，您將學習如何以優雅、高效和 Pythonic 的方式在底層deque實現您自己的隊列抽象數據類型 (ADT)。

注意：在 Python 標準庫中，您會發現queue.?該模塊實現了多生產者、多消費者隊列，允許您在多個線程之間安全地交換信息。

如果您正在使用隊列，那么deque除非您正在實現自己的數據結構，否則最好使用這些高級抽象。

隊列是項目的集合。您可以通過在一端添加項目并從另一端刪除項目來修改隊列。

隊列以先進/先出(?FIFO?) 方式管理它們的項目。它們用作管道，您可以在管道的一端插入新物品，并從另一端彈出舊物品。將項目添加到隊列的一端稱為入隊操作。從另一端刪除一個項目稱為dequeue。

為了更好地理解隊列，以您最喜歡的餐廳為例。餐廳里排起了長隊，等著一張桌子點菜。通常，最后一個到達的人將站在隊列的末尾。一旦有桌子，排在隊列開頭的人就會離開。

以下是使用基本deque對象模擬該過程的方法：

>>> from collections import deque >>> customers = deque() >>> # People arriving >>> customers.append("Jane") >>> customers.append("John") >>> customers.append("Linda") >>> customers deque(['Jane', 'John', 'Linda']) >>> # People getting tables >>> customers.popleft() 'Jane' >>> customers.popleft() 'John' >>> customers.popleft() 'Linda' >>> # No people in the queue >>> customers.popleft() Traceback (most recent call last): File "", line 1, in IndexError: pop from an empty deque

在這里，您首先創建一個空deque對象來表示到達餐廳的人的隊列。要排隊一個人，您可以使用.append()，它將單個項目添加到右端。要使一個人出隊，您可以使用.popleft()，它刪除并返回雙端隊列左端的單個項目。

酷！您的隊列模擬有效！但是，由于deque是泛化，它的API與典型的隊列 API 不匹配。例如，.enqueue()您有，而不是.append()。你也有.popleft()代替.dequeue().?此外，deque還提供了一些可能不適合您的特定需求的其他操作。

好消息是您可以使用您需要的功能創建自定義隊列類，而沒有其他功能。為此，您可以在內部使用雙端隊列來存儲數據并在您的自定義隊列中提供所需的功能。您可以將其視為適配器設計模式的實現，在其中將雙端隊列的接口轉換為看起來更像隊列接口的東西。

例如，假設您需要一個僅提供以下功能的自定義隊列抽象數據類型：

Enqueuing items

Dequeuing items

Returning the length of the queue

Supporting membership tests

Supporting normal and reverse iteration

Providing a user-friendly string representation

在這種情況下，您可以編寫一個如下所示的Queue類：

# custom_queue.py from collections import deque class Queue: def __init__(self): self._items = deque() def enqueue(self, item): self._items.append(item) def dequeue(self): try: return self._items.popleft() except IndexError: raise IndexError("dequeue from an empty queue") from None def __len__(self): return len(self._items) def __contains__(self, item): return item in self._items def __iter__(self): yield from self._items def __reversed__(self): yield from reversed(self._items) def __repr__(self): return f"Queue({list(self._items)})"

在這里，._items持有一個deque對象，允許您存儲和操作隊列中的項目。Queue實現.enqueue()使用deque.append()將項目添加到隊列的末尾。它還實現.dequeue()了deque.popleft()從隊列的開頭有效地刪除項目。

該特殊方法支持以下功能：

理想情況下，.__repr__()應該返回一個表示有效 Python 表達式的字符串。此表達式將允許您使用相同的值明確地重新創建對象。

但是，在上面的示例中，目的是使用方法的返回值在交互式 shell上優雅地顯示對象。您可以Queue通過接受一個初始化迭代作為參數.__init__()并從中構建實例，從而從這個特定的字符串表示構建實例成為可能。

通過這些最后的添加，您的Queue課程就完成了。要在您的代碼中使用此類，您可以執行以下操作：

>>> from custom_queue import Queue >>> numbers = Queue() >>> numbers Queue([]) >>> # Enqueue items >>> for number in range(1, 5): ... numbers.enqueue(number) ... >>> numbers Queue([1, 2, 3, 4]) >>> # Support len() >>> len(numbers) 4 >>> # Support membership tests >>> 2 in numbers True >>> 10 in numbers False >>> # Normal iteration >>> for number in numbers: ... print(f"Number: {number}") ... 1 2 3 4

作為練習，您可以測試其余功能并實現其他功能，例如支持相等性測試、刪除和訪問隨機項目等。來試試看吧！

探索其他功能?deque

除了您目前看到的功能外，deque還提供了特定于其內部設計的其他方法和屬性。它們為這種通用數據類型添加了新的有用功能。

在本節中，您將了解雙端隊列提供的其他方法和屬性、它們的工作方式以及如何在代碼中使用它們。

限制最大項目數：?maxlen

最有用的特性之一deque是可以在實例化類時使用參數指定給定雙端隊列的最大長度maxlen。

如果您為 提供值maxlen，那么您的雙端隊列將最多存儲maxlen項目。在這種情況下，您有一個有界 deque。一旦有界雙端隊列充滿指定數量的項目，在任一端添加新項目會自動刪除并丟棄另一端的項目：

>>> from collections import deque >>> four_numbers = deque([0, 1, 2, 3, 4], maxlen=4) # Discard 0 >>> four_numbers deque([1, 2, 3, 4], maxlen=4) >>> four_numbers.append(5) # Automatically remove 1 >>> four_numbers deque([2, 3, 4, 5], maxlen=4) >>> four_numbers.append(6) # Automatically remove 2 >>> four_numbers deque([3, 4, 5, 6], maxlen=4) >>> four_numbers.appendleft(2) # Automatically remove 6 >>> four_numbers deque([2, 3, 4, 5], maxlen=4) >>> four_numbers.appendleft(1) # Automatically remove 5 >>> four_numbers deque([1, 2, 3, 4], maxlen=4) >>> four_numbers.maxlen 4

如果輸入迭代中的項目數大于maxlen，則deque丟棄最左邊的項目（0在示例中）。一旦雙端隊列已滿，在任何一端附加一個項目會自動刪除另一端的項目。

請注意，如果您沒有為 指定值maxlen，則它默認為None，并且雙端隊列可以增長到任意數量的項目。

可以選擇限制最大項目數允許您使用雙端隊列來跟蹤給定對象或事件序列中的最新元素。例如，您可以跟蹤銀行帳戶中的最后五筆交易、編輯器中最近打開的十個文本文件、瀏覽器中的最后五頁等等。

請注意，maxlen它在您的雙端隊列中作為只讀屬性可用，它允許您檢查雙端隊列是否已滿，例如在deque.maxlen == len(deque).

最后，您可以設置maxlen為任何正整數，表示要存儲在特定雙端隊列中的最大項目數。如果您為 提供負值maxlen，則您會得到一個ValueError。

Rotating the Items： .rotate()

.rotate()雙端隊列的另一個有趣特性是可以通過調用非空雙端隊列來旋轉它們的元素。此方法將整數n作為參數并n向右旋轉項目步驟。換句話說，它n以循環方式將項目從右端移動到左端。

默認值n是1。如果為 提供負值n，則向左旋轉：

>>> from collections import deque >>> ordinals = deque(["first", "second", "third"]) >>> # Rotate items to the right >>> ordinals.rotate() >>> ordinals deque(['third', 'first', 'second']) >>> ordinals.rotate(2) >>> ordinals deque(['first', 'second', 'third']) >>> # Rotate items to the left >>> ordinals.rotate(-2) >>> ordinals deque(['third', 'first', 'second']) >>> ordinals.rotate(-1) >>> ordinals deque(['first', 'second', 'third'])

在這些示例中，您ordinals使用.rotate()不同的 值旋轉多次n。如果.rotate()不帶參數調用，則它依賴于的默認值n并將雙端隊列1位置向右旋轉。使用負數調用該方法n允許您將項目向左旋轉。

一次添加多個項目：?.extendleft()

與常規列表一樣，.extend()雙端隊列提供了一種方法，該方法允許您使用 aniterable作為參數將多個項目添加到雙端隊列的右端。此外，雙端隊列有一個名為 的方法extendleft()，該方法將 aniterable作為參數并一次性將其項添加到目標雙端隊列的左端：

>>> from collections import deque >>> numbers = deque([1, 2]) >>> # Extend to the right >>> numbers.extend([3, 4, 5]) >>> numbers deque([1, 2, 3, 4, 5]) >>> # Extend to the left >>> numbers.extendleft([-1, -2, -3, -4, -5]) >>> numbers deque([-5, -4, -3, -2, -1, 1, 2, 3, 4, 5])

調用.extendleft()與iterable延伸目標deque的左側。在內部，.extendleft()執行一系列.appendleft()從左到右處理輸入可迭代的單獨操作。這最終以相反的順序將項目添加到目標雙端隊列的左端。

使用類似序列的特征?deque

由于雙端隊列是可變序列，它們幾乎實現了序列和可變序列共有的所有方法和操作。到目前為止，您已經了解了其中的一些方法和操作，例如.insert()索引、成員資格測試等。

以下是您可以對deque對象執行的其他操作的一些示例：

>>> from collections import deque >>> numbers = deque([1, 2, 2, 3, 4, 4, 5]) >>> # Concatenation >>> numbers + deque([6, 7, 8]) deque([1, 2, 2, 3, 4, 4, 5, 6, 7, 8]) >>> # Repetition >>> numbers * 2 deque([1, 2, 2, 3, 4, 4, 5, 1, 2, 2, 3, 4, 4, 5]) >>> # Common sequence methods >>> numbers = deque([1, 2, 2, 3, 4, 4, 5]) >>> numbers.index(2) 1 >>> numbers.count(4) 2 >>> # Common mutable sequence methods >>> numbers.reverse() >>> numbers deque([5, 4, 4, 3, 2, 2, 1]) >>> numbers.clear() >>> numbers deque([])

您可以使用加法運算符(?+) 連接兩個現有的雙端隊列。另一方面，乘法運算符 (?*) 返回一個新的雙端隊列，相當于根據需要多次重復原始雙端隊列。

關于其他序列方法，下表提供了一個總結：

在這里，.index()還可以采用兩個可選參數：start和stop。它們允許您將搜索限制在 或之后start和之前的那些項目stop。該方法引發一個ValueErrorifvalue沒有出現在手頭的雙端隊列中。

與列表不同，雙端隊列不包含.sort()對序列進行適當排序的方法。這是因為對鏈表進行排序是一種低效的操作。如果您需要對雙端隊列進行排序，那么您仍然可以使用sorted().

將 Pythondeque付諸行動

您可以在大量用例中使用雙端隊列，例如實現隊列、堆棧和循環緩沖區。您還可以使用它們來維護撤消重做歷史記錄、將傳入請求排入Web 服務隊列、保留最近打開的文件和網站的列表、在多個線程之間安全地交換數據等等。

在以下部分中，您將編寫一些小示例，以幫助您更好地理解如何在代碼中使用雙端隊列。

保留頁面歷史

有一個maxlen限制項目的最大數量使得deque適合解決幾個問題。例如，假設您正在構建一個應用程序，擦傷來自搜索引擎和社交媒體網站的數據。在某些時候，您需要跟蹤應用程序從中請求數據的最后三個站點。

要解決此問題，您可以使用帶有maxlenof的雙端隊列3：

>>> from collections import deque >>> sites = ( ... "google.com", ... "yahoo.com", ... "bing.com" ... ) >>> pages = deque(maxlen=3) >>> pages.maxlen 3 >>> for site in sites: ... pages.appendleft(site) ... >>> pages deque(['bing.com', 'yahoo.com', 'google.com'], maxlen=3) >>> pages.appendleft("facebook.com") >>> pages deque(['facebook.com', 'bing.com', 'yahoo.com'], maxlen=3) >>> pages.appendleft("twitter.com") >>> pages deque(['twitter.com', 'facebook.com', 'bing.com'], maxlen=3)

在此示例中，pages保留您的應用程序訪問的最后三個站點的列表。一旦pages已滿，將新站點添加到雙端隊列的末尾會自動丟棄另一端的站點。此行為使您的列表與您最近使用的三個站點保持同步。

請注意，您可以將maxlen任何正整數設置為表示要存儲在手頭雙端隊列中的項目數。例如，如果要保留十個站點的列表，則可以設置maxlen為10。

在線程之間共享數據

雙端隊列的.append()、.appendleft()、.pop()、.popleft()和len(d)操作在 CPython 中是線程安全的。（來源）

因此，您可以安全地同時從單獨的線程添加和刪除雙端隊列兩端的數據，而不會出現數據損壞或其他相關問題的風險。

要嘗試deque在多線程應用程序中的工作方式，請啟動您最喜歡的代碼編輯器，創建一個名為 的新腳本threads.py，然后向其中添加以下代碼：

# threads.py import logging import random import threading import time from collections import deque logging.basicConfig(level=logging.INFO, format="%(message)s") def wait_seconds(mins, maxs): time.sleep(mins + random.random() * (maxs - mins)) def produce(queue, size): while True: if len(queue) < size: value = random.randint(0, 9) queue.append(value) logging.info("Produced: %d -> %s", value, str(queue)) else: logging.info("Queue is saturated") wait_seconds(0.1, 0.5) def consume(queue): while True: try: value = queue.popleft() except IndexError: logging.info("Queue is empty") else: logging.info("Consumed: %d -> %s", value, str(queue)) wait_seconds(0.2, 0.7) logging.info("Starting Threads...\n") logging.info("Press Ctrl+C to interrupt the execution\n") shared_queue = deque() threading.Thread(target=produce, args=(shared_queue, 10)).start() threading.Thread(target=consume, args=(shared_queue,)).start()

這里，produce()以 aqueue和 asize作為參數。然后它random.randint()在while循環中使用以連續產生隨機數并將它們存儲在名為的全局雙端隊列中shared_queue。由于向雙端隊列追加項是線程安全的操作，因此您不需要使用鎖來保護共享數據不受其他線程的影響。

輔助函數wait_seconds()模擬這兩者produce()并consume()代表長時間運行的操作。它返回的秒的給定范圍之間的隨機等待時間值，mins和maxs。

在 中consume()，您.popleft()在循環內部調用以系統地檢索和刪除數據shared_queue。您將調用包裝.popleft()在一個try…except語句中，以處理共享隊列為空的情況。

請注意，當您shared_queue在全局命名空間中定義時，您可以通過produce()and內部的局部變量訪問它consume()。直接訪問全局變量會更成問題，絕對不是最佳實踐。

最后兩行腳本創建和啟動單獨的線程來執行produce()，并consume()兼任。如果您從命令行運行該腳本，您將獲得類似于以下內容的輸出：

$ python threads.py Starting Threads... Press Ctrl+C to interrupt the execution Produced: 1 -> deque([1]) Consumed: 1 -> deque([]) Queue is empty Produced: 3 -> deque([3]) Produced: 0 -> deque([3, 0]) Consumed: 3 -> deque([0]) Consumed: 0 -> deque([]) Produced: 1 -> deque([1]) Produced: 0 -> deque([1, 0]) ...

生產者線程在共享雙端隊列的右端添加數字，而消費者線程從左端消耗數字。要中斷腳本執行，您可以按鍵盤上的Ctrl+C。

最后，您可以在produce()和里面玩一點時間間隔consume()。更改傳遞給 的值wait_seconds()，并觀察當生產者比消費者慢時程序的行為，反之亦然。

模擬tail命令

您將在此處編寫代碼的最后一個示例模擬tail命令，該命令可在Unix和類 Unix操作系統上使用。該命令接受命令行中的文件路徑并將該文件的最后十行打印到系統的標準輸出。您可以tail使用-n,--lines選項調整需要打印的行數。

這是一個模擬以下核心功能的小型 Python 函數tail：

>>>

>>> from collections import deque >>> def tail(filename, lines=10): ... try: ... with open(filename) as file: ... return deque(file, lines) ... except OSError as error: ... print(f'Opening file "{filename}" failed with error: {error}') ...

在這里，您定義tail().?第一個參數filename將目標文件的路徑保存為字符串。第二個參數lines表示要從目標文件末尾檢索的行數。請注意，lines默認為10模擬tail.

注意：這個例子的最初想法來自 Python 文檔deque。查看deque食譜部分以獲取更多示例。

突出顯示行中的雙端隊列最多只能存儲您傳遞給 的項目數lines。這可以保證您從輸入文件的末尾獲得所需的行數。

正如你之前看到的，當你創建一個有界雙端隊列并用一個迭代器初始化它時，它包含的項目多于允許的 (?maxlen)，deque構造函數會丟棄輸入中所有最左邊的項目。因此，您最終會maxlen得到目標文件的最后幾行。

結論

隊列和棧是編程中常用的抽象數據類型。它們通常需要在底層數據結構的任一端進行高效的彈出和追加操作。Python 的collections模塊提供了一種名為的數據類型deque，專為在兩端進行快速且節省內存的追加和彈出操作而設計。

使用deque，您可以以優雅、高效和 Pythonic 的方式在低級別編寫自己的隊列和堆棧。

在本教程中，您學習了如何：

deque在代碼中創建和使用 Python

有效地從序列的兩端附加和彈出項目deque

用于在 Python 中deque構建高效的隊列和堆棧

決定何時使用deque而不是list

在本教程中，您還編寫了一些示例來幫助您處理dequePython 中的一些常見用例。

Python 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。