了解 Python 中的队列实现

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

在本文中,我们将了解 Queue 及其在 Python 中的实现。

什么是队列?

队列是遵循先进先出(FIFO)原则的线性数据结构。 它与 Stack 数据结构相反。

我们可以将队列与现实生活中电影院售票处的队列进行比较。 让我们看一下队列的图示,如下所示。

如果你观察柜台前的排队情况,第二个人只能在第一个人完成工作后才能去柜台。 在这里,第一个人来到柜台,然后是第二个人。 因此,这里的人们遵循 FIFO(先进先出)原则。 谁先来,他/她就先完成工作。 我们可以在日常生活中看到类似的队列。

Queue数据结构也遵循同样的原则。 现在,你知道队列是什么以及它的原理了。 让我们看看可以对队列数据结构执行的操作。

队列中的操作

与堆栈类似,我们会在队列数据结构中发现两个主要操作。

排队(数据)

最后将新数据添加到队列中。 侧面称为背面。

出列()

从队列的前面删除数据。 侧面称为正面。

让我们看一下队列操作插图以便更好地理解。 一张照片说一千个字。

我们可以编写一些辅助函数来获取有关队列的更多信息。 您将拥有的辅助函数的数量没有限制。 现在让我们坚持下面提到的最重要的一次。

后部()

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

正面()

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

是空的()

返回队列是否为空。

你不觉得无聊吗? 我的意思是概念性主题。

对我来说是的!

但是,如果不了解这些概念,我们将无能为力。 我们必须在实施之前完全了解它。 别担心,是时候亲自动手编写一些代码了。

我假设您的 PC 上安装了 python,如果没有,您也可以尝试使用在线编译器。

队列实现

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

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

#1。 列表

列表是 Python 中的一种内置数据类型。 我们将使用列表数据类型在类中实现队列。 我们将引导您通过不同的步骤从头开始实现队列数据结构,无需任何模块。 让我们开始吧。

步骤1:

编写一个名为 Queue 的类。

class Queue:
	pass

第2步:

必须有一些变量来存储类中队列的数据。 让我们将其命名为元素。 这当然是一个列表。

class Queue:

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

第三步:

要将数据插入队列,我们​​需要类中的一个方法。 正如我们在本教程的前一节中讨论的那样,该方法称为 enqueue。

该方法获取一些数据并将其添加到队列(元素)中。 我们可以使用list数据类型的append方法在队列尾部添加数据。

class Queue:

	# ...

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

第4步:

队列需要有出口。 这就是所谓的出队。 我想你已经猜到我们要用到list数据类型的pop方法了。 不管你猜不猜,干杯!

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

  如何在 Ubuntu 上安装 DBeaver MySQL 客户端

在这里,我们需要删除列表的第一个元素。 所以,我们必须将索引 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()

现在,我们有一个队列对象。 让我们用一些系列的操作来测试它。

  • 使用 is_empty 方法检查队列是否为空。 它应该返回 True。
  • 使用 enqueue 方法将数字 1、2、3、4、5 添加到队列中。
  • is_empty 方法应该返回 False。 核实。
  • 分别使用front和rear方法打印前后元素。
  • 使用 dequeue 方法从队列中删除元素。
  • 检查前面的元素。 它应该返回元素 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()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

我想你运行上面的程序。 您可以获得类似于以下结果的输出。

True
False
1 5
2 5
True

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

  NVMe 与 SATA:哪种 SSD 技术更快?

您还可以通过像我们之前那样简单地创建对象,在项目的不同程序中使用上述队列的类实现。

我们已经使用列表数据类型从头开始实现了队列。 队列有内置模块吗? 是的! 我们有内置的队列实现。 让我们看看他们。

#2。 来自集合的双端队列

它被实现为一个双端队列。 由于它支持从两端添加和删除元素,所以我们可以将它用作堆栈和队列。 让我们看看使用 dequeue 的队列实现。

它是使用称为双向链表的其他数据结构实现的。 所以元素的插入和删除的表现是一致的。 从中间链表访问元素花费了 O(n) 时间。 我们可以将它用作队列,因为不需要访问队列中的中间元素。

让我们检查 dequeue 为我们提供的不同方法。

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

front、rear 和 is_empty 没有替代方法。 我们可以打印整个队列来代替前后方法。 接下来,我们可以使用 len 方法来检查队列是否为空。

我们已经按照一系列步骤来测试前面的队列实现。 让我们在这里也遵循相同的一系列步骤。

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

您将获得类似于以下输出的结果。

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3。 从队列中排队

Python 有一个名为 queue 的内置模块,它为队列实现提供了一个名为 Queue 的类。 它类似于我们之前实现的那个。

  修复 Virtualbox 无法插入虚拟光盘

首先,让我们检查 Queue 类的不同方法。

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

让我们用上面的方法来实现队列。

from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

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

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

检查以上代码的输出。

True
False
1
2
3
Size 2
4
5
True

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

结论

我希望您已经了解了队列数据结构及其实现。 队列就是这样。 您可以在需要以 FIFO(先进先出)顺序处理的不同地方使用队列。 每当您需要使用队列时,都可以在解决问题时使用它。

有兴趣掌握 Python 吗? 查看这些学习资源。

快乐编码🙂👨‍💻