理解Python中的队列实现

数据结构在编程世界中发挥着关键作用。它们帮助我们以高效的方式组织数据。队列是最简单的数据结构之一。

在本文中，我们将学习队列及其在Python中的实现。

什么是队列？

队列是一种遵循先进先出（FIFO）原则的线性数据结构。它与栈相反。

我们可以将队列与电影票柜台的现实生活队列进行比较。让我们看一下队列的示例。

如果您观察柜台上的队列，第二个人只有在第一个人完成工作后才能去柜台。第一个人来到柜台，然后是第二个人。因此，人们遵循先进先出的原则。谁先来，谁先完成工作。我们在日常生活中可以看到类似的队列。

队列数据结构也遵循相同的原则。现在，您知道队列是什么以及它的原则。让我们看看可以在队列数据结构上执行的操作。

队列的操作

与栈类似，队列数据结构中有两个主要操作。

enqueue(data)

将新数据添加到队列的末尾。一侧称为“rear”。

dequeue()

从队列的前面删除数据。一侧称为“front”。

让我们看看队列操作的示例，以便更好地理解。一图胜过千言万语。

我们可以编写一些辅助函数来获取有关队列的更多信息。您可以有任意数量的辅助函数。让我们现在先坚持最重要的一些。

rear()

返回队列末尾的第一个元素。

front()

返回队列开头的第一个元素。

is_empty()

返回队列是否为空。

这对您来说是不是很无聊？我的意思是概念性的话题。

对我来说是的！

但是，如果不了解这些概念，我们什么也做不了。在实现之前，我们必须完全了解它。不用担心，现在是用一些代码开始的时候了。

我假设您的电脑上有Python安装，如果没有，您也可以尝试在线编辑器。

队列的实现

对于程序员来说，实现队列不会超过15分钟。一旦学会了，您将会说出来。也许在本教程之后的几分钟内您就可以实现它。

有多种方法可以在Python中实现队列。让我们逐步看看不同的队列实现。

#1. 列表

列表是Python中的内置数据类型。我们将使用列表数据类型来在类中实现队列。我们将逐步为您讲解如何从头开始实现队列数据结构，而无需使用任何模块。让我们开始吧。

步骤1：

编写一个名为Queue的类。

class Queue:
    pass

步骤2：

在类中必须有某些变量来存储队列的数据。让我们称其为elements。当然，它是一个列表。

class Queue:

    def __init__(self):
        self.elements = []

步骤3：

要向队列中插入数据，我们需要一个类中的方法。该方法称为enqueue，如上一节教程中已经讨论过的那样。

该方法接受一些数据并将其添加到队列（元素）中。我们可以使用列表数据类型的append方法将数据添加到队列的末尾。

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

第四步：

队列需要有一个出口。它被称为dequeue。我想你已经猜到了我们将要使用列表数据类型的pop方法。无论你猜对与否，干杯！

列表数据类型的pop方法从给定索引的列表中删除一个元素。如果我们没有给出任何索引，那么它将删除列表的最后一个元素。

在这里，我们需要删除列表的第一个元素。所以，我们必须将索引0传递给pop方法。

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

至此，队列已经完成。但是，我们需要辅助函数来测试队列操作是否正常工作。让我们也写下这些辅助函数。

第五步：

方法rear()用于获取队列的最后一个元素。列表数据类型中的负索引帮助我们获取队列的最后一个元素。

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

第六步：

方法front()用于获取队列的第一个元素。我们可以使用列表索引获取队列的第一个元素。

class Queue:

	# ...

	def front(self):
		return self.elements[0]

第七步：

方法is_empty()用于检查队列是否为空。我们可以检查列表的长度。

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

呼！完成了队列数据结构的实现部分。我们需要为Queue 类创建一个对象才能使用。

让我们来做吧。

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

现在，我们有一个Queue对象。让我们用一系列操作来测试它。

• 使用is_empty方法检查队列是否为空。它应该返回True。
• 使用enqueue方法将数字1、2、3、4、5添加到queue中。
• is_empty方法应返回False。检查一下。
• 使用front和rear方法分别打印front和rear元素。
• 使用dequeue方法从队列中删除元素。
• 检查front元素。它应该返回元素2。
• 现在，将队列中的所有元素都删除。
• is_empty方法应返回True。检查一下。

我想测试我们的队列实现已经足够了。按照上面提到的每个步骤编写代码来测试队列。

你写好代码了吗？

不，别担心。

检查下面的代码。

class Queue:

def __init__(self):
self.elements = []

def enqueue(self, data):
self.elements.append(data)
return data

def dequeue(self):
return self.elements.pop(0)

def rear(self):
return self.elements[-1]

def front(self):
return self.elements[0]

def is_empty(self):
return len(self.elements) == 0

if __name__ == ‘__main__':
queue = Queue()

## 检查 is_empty 方法 -> True
print(queue.is_empty())

## 添加元素
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

## 再次检查 is_empty 方法 -> False
print(queue.is_empty())

## 使用 front 和 rear 方法分别打印队列的头部和尾部元素 -> 1, 5
print(queue.front(), end=' ‘)
print(queue.rear())

## 移除元素 -> 1
queue.dequeue()

## 使用 front 和 rear 方法分别打印队列的头部和尾部元素 -> 2 5
print(queue.front(), end=' ‘)
print(queue.rear())

## 移除所有元素
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()

## 最后一次检查 is_empty 方法 -> True
print(queue.is_empty())

我认为你运行了上述程序。你可以得到类似以下结果的输出。

True
False
1 5
2 5
True

我们可以直接使用列表数据类型作为队列数据结构。上述队列的实现可以帮助你更好地理解其他编程语言中的队列实现。

你也可以通过创建对象的方式在项目的不同程序中使用上述类实现的队列。

我们已经从头开始实现了使用列表数据类型的队列。是否有任何内置模块用于队列？是的！我们有内置的队列实现。让我们来看看它们。

#2. collections 中的 deque

它是作为双端队列实现的。由于它支持在两端添加和删除元素，我们可以将其用作栈和队列。让我们看看使用 deque 实现队列。

它是使用其他数据结构（称为双向链表）实现的。因此，插入和删除元素的性能是一致的。从链表中间访问元素需要 O(n) 的时间。由于不需要访问队列的中间元素，我们可以将其用作队列。

我们来看看 deque 提供给我们的不同方法。

• append(data) – 用于将数据添加到队列
• popleft() – 用于从队列中删除第一个元素

对于 front、rear 和 is_empty 方法，没有其他的替代方法。我们可以打印整个队列来代替 front 和 rear 方法。然后，我们可以使用 len 方法来检查队列是否为空。

我们在前面的测试队列实现中按照一系列步骤进行了测试。在这里，我们将按照相同的一系列步骤进行测试。

from collections import deque

## 创建deque对象
queue = deque()

## 检查队列是否为空->True
print(len(queue) == 0)

## 添加元素
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## 再次检查队列是否为空->False
print(len(queue) == 0)

## 打印队列
print(queue)

## 移除元素->1
queue.popleft()

## 打印队列
print(queue)

## 移除所有元素
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## 最后一次检查队列是否为空->True
print(len(queue) == 0)

#3. 从queue导入Queue
# Python有一个内置模块称为queue，它提供了一个名为Queue的类用于队列实现。它与我们之前实现的类似。

# 首先，让我们查看Queue类的不同方法。

# put(data) – 添加或推送数据到队列
# get() – 从队列中删除第一个元素并返回
# empty() – 返回栈是否为空
# qsize() – 返回队列的长度。

# 让我们使用上述方法实现队列。

from queue import Queue

## 创建Queue对象
queue_object = Queue()

## 检查队列是否为空->True
print(queue_object.empty())

## 添加元素
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## 再次检查队列是否为空->False
print(queue_object.empty())

## 移除所有元素
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## 检查队列大小
print(“Size”, queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## 最后一次检查队列是否为空->True
print(queue_object.empty())

# Queue类中还有其他一些方法。您可以使用dir内置函数来探索它们。

# 结论
# 希望您已经学会了队列数据结构及其实现。这就是队列的全部内容。您可以在需要按FIFO（先进先出）顺序处理的不同位置使用队列。在问题解决中使用队列时，优先考虑使用队列。

# 对Python感兴趣吗？查看这些链接。

# 快乐编程🙂👨‍💻