站点图标 AI技术聚合

Python中队列的完整指南

心中带点小风骚

Python中队列的完整指南

什么是队列以及如何在 Python 中实现队列

编程术语中的队列是一种抽象数据类型，它存储项目添加到结构中的顺序，但它只允许添加到队列的末尾，而只允许从队列的前面删除。在这样做时，这遵循先进先出 (FIFO) 数据结构。从本质上讲，这就像您期望队列在实际中的行为一样，例如在排队进入商店时，那些先到那里的人会先到那里。然而，与现实生活不同的是，我们以一种确保没有插队的方式来构建它！

当我们想要将输出存储在保留其顺序的结构中，然后按给定顺序执行操作时，可以使用这些。编程中的常见示例包括为计算机的 CPU 调度作业、为打印机排队以确保执行最先发送的作业、为业务处理订单或处理消息。

考虑到这一点，知道我们想要数据结构做什么以及我们想要如何与之交互，我们就可以开始考虑如何在 Python 中的实际数据结构中实现这一点。通常与此相关的关键方法包括：

  • enqueue(item)：将一个项目添加到队列的末尾
  • dequeue()：移除并返回队列最前面的项目
  • peek()：返回队列前面的项目而不删除它
  • is_empty()：如果队列为空，则返回 True
  • size()：返回队列中有多少项

这意味着我们需要使用可变的 Python 数据类型来构建它，并且可以用来存储有序的项目集合。我们可以问自己的第一件事是，是否已经在 Python 中实现了可以为我们执行此操作的数据类型？

一个列表！我们可以使用列表！

我们知道列表是可变的，它可以更改，我们可以使用列表已经内置的功能来实现队列，我们​​可以简单地从头到尾添加和删除项目。

在使用列表时，我们必须定义一个使用它的类，但仅具有允许用户以我们想要的方式与之交互的特定功能。为此，我们可以使用 Python 的类结构来定义数据结构将包含的信息以及我们想要使用的方法。

然后要做的第一件事就是将该类命名为 Queue 并为这个新类创建构造函数。一旦创建了对象的新实例，我们想要的是初始化一个可以使用 .items 属性访问的空列表。代码如下：

class Queue:    #create the constructor
    def __init__(self):        #create an empty list as the items attribute
        self.items = []

这意味着当我们创建 Queue 类的实例时，item 属性将表示一个空列表。

然后我们可以开始向 Queue 类添加主要功能。我们想要做的第一件事就是向我们的 Queue 添加一个项目。在这一点上，重要的是能够确定哪一端是我们从中获取数据的队列的前端，以及哪一端是我们可以添加项目的队列的一端。

这意味着每个过程需要多长时间，因为在列表开头更改事物会导致 O(n) 的时间复杂度，因为我们必须更改列表中后续项目的所有索引以将所有内容向右移动.但是，如果我们在列表末尾操作事物，则时间复杂度为 O(1)，因为我们仅在删除或添加项目时才更改列表末尾的索引。

但是，这并不重要，因为您选择添加或从其他功能中删除的任何一方仍然具有其他时间复杂度。因此，考虑到这一点，我们可以实现 enqueue(item) 方法来将项目添加到我们的队列中。

    def enqueue(self, item):
        """
        Add item to the left of the list, returns Nothing        Runs in linear time O(n) as we change all indices
        as we add to the left of the list
        """        #use the insert method to insert at index 0
        self.items.insert(0, item)

这将简单地将一个项目添加到我们队列的末尾（左侧）。在这种情况下，我们并不太关心我们添加到队列中的内容，只是我们可以添加它。当然，您可以为此添加更多功能，但现在这很好。

这意味着当我们想要从 Queue 类的列表右端删除项目时。在这样做时，我们需要注意一个相当简单的边缘情况，即我们的队列是否为空。在这种情况下，如果队列为空，我们可以简单地返回 None ，这样我们仍然会返回一些东西，程序不会抛出错误，但如果它不为空，那么我们可以返回队列中的“第一个”项目，并且把它返还。由于我们使用的是 Python 的内置列表类，我们可以简单地使用 .pop() 方法，该方法在 Python 3.6+ 中从列表中删除 ist 项并返回它。这在恒定时间 O(1) 中运行，因为我们只删除列表项而不影响任何其他索引。因此，这可以实现为：

    def dequeue(self):
        """
        Removes the first item from the queue and removes it        Runs in constant time O(1) because we are index to
        the end of the list.
        """        #check to see whether there are any items in the queue
        #if so then we can pop the final item
        if self.items:
            
            return self.items.pop()        #else then we return None
        else:            return None

因此，我们实现了队列的主要功能，确保我们只将项目添加到队列的一端并从队列的另一端删除项目。这将维护队列中项目的顺序，并确保我们以与添加到队列中的顺序相同的顺序使用这些项目。

然后我们可以考虑其他有助于在实际程序中使用队列数据结构的补充方法。我们可以添加的第一个附加功能是允许用户查看要从队列中删除的下一个项目，而无需实际删除它。它的实现将遵循与 dequeue() 方法类似的结构，但我们可以暗示使用列表中的最后一项来访问该项目，而不是使用 .pop()。这意味着当我们使用索引来访问项目时，我们的时间复杂度为 O(1)，这使得它变得简单而美观。

    def peek(self):
        """
        Returns the final item in the Queue without removal
        
        Runs in constant time O(1) as we are only using the index
        """        #if there are items in the Queue 
        if self.items:
            #then return the first item
            return self.items
        
        #else then return none
        else:
            return Non

我们还可以提供一种检查队列是否为空的方法。如果队列实际上是空的，这将简单地返回一个布尔值 True，如果不是，则返回 False。这也以恒定时间运行，因为它只是检查队列中的列表是否存在

    def is_empty(self):
        """
        Returns boolean whether Queue is empty or not        Runs in constant time O(1) as does not depend on size
        """        return not self.items

我们可以创建一个返回队列大小的方法。这可以告诉我们使用队列的大小，就像它对列表一样，并告诉我们已经添加了多少项目或队列中剩余多少项目。

    def size(self):
        """
        Returns the size of the stack         Runs in constant time O(1) as only checks size
        """        #len will return 0 if empty
        #so don't need to worry about empty condition
        return len(self.items)

最后，我们要确保我们尝试打印出 Queue 类的一个实例，它实际上对于个人来说是可读的，以查看它是 Queue 以及该 Queue 包含的内容。为此，我们使用类的特殊 __str__ dunder 方法告诉解释器我们要如何打印出该类的实例。在这种情况下，我们只想返回包含在堆栈中的整个列表，可以实现为：

    def __str__(self):
        """Return a string representation of the Stack""""        return str(self.items)

呸！那么把这一切放在一起怎么样？最终产品如下所示：

在这一点上，您可能在想为什么我需要知道这一点？好吧，这种数据结构在编程中的常见应用包括：

  • 在 CPU 中调度作业
  • Graph traversal algorithms
  • Order Processing
  • Printer Queues

当您构建这些程序以了解此数据结构在 Python 中的样子并为您提供能够应对这些挑战的功能时，知道这一点是件好事。

这也可能出现在软件工程师或数据科学面试中，例如要求您构建使用队列的打印机或创建图遍历算法（例如深度优先搜索）。

所以你去了，你知道如何在 Python 中实现一个队列以及它的一些用途！

这是探索数据结构及其在 Python 中的使用和实现的系列文章中的第七篇。如果您错过了 Python 中的链表、堆栈和字典的前三个，您可以在以下链接中找到它们：

该系列的未来文章将涵盖链接列表、队列和图表。为确保您不会错过任何邮件，请在邮件通知发布时注册：

如果您喜欢您阅读的内容但还不是 Medium 会员，那么请考虑通过使用下面的推荐代码注册来支持我自己和此平台上的其他出色作者：

感谢您的阅读！

文章出处登录后可见！

已经登录？立即刷新
退出移动版