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小时内删除侵权内容。