Python 中的队列

在本教程中，我们将讨论队列的基本概念和内置的队列类，并使用 Python 代码来实现它。

什么是队列？

队列是一种线性数据结构，用于按顺序存储数据。队列的概念基于 FIFO，即“先进先出”。它也被称为“先到先服务”。队列有两个端：前端和后端。下一个元素从后端插入，并从前端移除。

例如 - 计算机实验室有 20 台计算机，连接到一台打印机。学生们想打印他们的论文；打印机会打印第一个任务，然后是第二个，依此类推。如果我们是最后排队的人，我们就必须等到我们前面所有的任务都完成。

操作系统会管理队列来处理计算机内的各种进程。

Python 中的操作

我们可以在队列中执行以下操作。

• 入队 (Enqueue) - 入队是我们将项添加到队列中的操作。如果队列已满，则会出现队列溢出的状况。入队的时间复杂度为O(1)。
• 出队 (Dequeue) - 出队是从队列中移除元素的操作。元素按照插入的顺序移除。如果队列为空，则会出现队列下溢的状况。出队的时间复杂度为O(1)。
• 前端 (Front) - 元素从前端插入。前端操作的时间复杂度为O(1)。
• 后端 (Rear) - 元素从后端移除。后端操作的时间复杂度为O(1)。

队列中的可用方法

Python 提供了以下方法，这些方法常用于在队列中执行操作。

• put(item) - 此函数用于将元素插入队列。
• get() - 此函数用于从队列中提取元素。
• empty() - 此函数用于检查队列是否为空。如果队列为空，则返回 true。
• qsize - 此函数返回队列的长度。
• full() - 如果队列已满，则返回 true；否则返回 false。

我们将在下面的部分中学习这些函数。

内置的 Python 列表

列表可以用作队列，但从性能角度来看并不适合。Python 提供了内置的 insert() 和 pop() 函数来添加和删除元素。列表的性能很慢，因为如果我们向列表中插入一个新元素，所有元素都需要移动一位。这需要 O(n) 时间。因此，不推荐使用列表代替队列。让我们通过以下示例了解如何使用列表作为队列。

示例 -

输出

['Apple', 'Mango', 'Papaya']
Apple

解释 -

我们在上面的代码中定义了一个空列表，并使用 append() 方法插入了几个元素。它会将元素添加到列表的末尾。

向队列添加元素 (入队)

我们可以从后端添加元素。这个过程也称为入队。我们创建一个 Queue 类，在其中实现先进先出概念。让我们通过以下示例来理解。

示例 -

输出

The length of Queue:  4

从队列中移除元素 (出队)

我们可以从后端移除元素。这个过程称为出队。在下面的示例中，我们使用内置的 pop() 方法从列表中移除元素。

示例 -

输出

January
February

解释 -

在上面的代码中，我们定义了一个名为 Queue 的类以及其中的构造函数。我们将列表构造函数赋给了 queue 变量。然后，我们定义了两个方法 - add_element() 和 remove_element()。在 add_element() 块中，我们检查值是否不在队列中。如果值不存在，则插入元素。

在 remove_element() 函数块中，我们检查队列是否不为空。如果返回 false，则逐个移除元素。

对队列进行排序

在下面的示例中，我们对队列中的元素进行了排序。

示例 -

输出

1 4 11 14 27

Queue 模块

Python 提供了 queue 模块来实现多生产者、多消费者的队列。queue 模块提供了 Queue 类，该类特别用于多线程编程。Queue 类实现了所有必需的锁定语义。

我们可以使用内置的 queue 类执行所有操作。

使用 queue.Queue 类

queue 模块包含几个类。Queue 是其中一个重要的类。它在并行计算和多编程中非常有用。让我们通过以下队列示例来理解。Queue 类0uii

示例 -

输出

<queue.Queue object at 0x00000114B30656A0>
Apple
Mango
Papaya
Traceback (most recent call last):
  File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Queue.py", line 78, in <module>
    print(que.get_nowait())
  File "C:\Python\lib\queue.py", line 198, in get_nowait
    return self.get(block=False)
  File "C:\Python\lib\queue.py", line 167, in get
    raise Empty
_queue.Empty

使用 collection.deque 类

collection.deque 类用于实现双端队列，该队列支持在两端添加和移除元素。完成此过程需要 O(1) 时间。

deque 类既可以用于队列，也可以用于栈，因为它可以有效地移除和添加元素。

collection.deque 是 Python 标准库中队列数据结构的不错选择。

示例 -

输出

deque(['Apple', 'Mango', 'Banana'])
Apple
Mango
Banana
Traceback (most recent call last):
  File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Queue.py", line 101, in <module>
    que.popleft()
IndexError: pop from an empty deque

使用 multiprocessing.Queue 类

multiprocessing.Queue 类用于实现队列项，以便由多线程工作进程并行处理。multiprocessing.Queue 在进程之间共享数据，并且可以存储任何可 pickle 的对象。让我们通过以下示例来理解。

示例 -

输出

<multiprocessing.queues.Queue object at 0x000002CA073356A0>
Apple
Mango
Banana

Python 中的优先队列

优先队列是一种特殊类型的队列。顾名思义，它会根据元素的优先级对元素进行排序并出队。

与普通队列不同，它检索优先级最高的元素而不是下一个元素。单个元素的优先级由对其键应用的顺序决定。

优先队列在处理需要根据优先级发生的任务的调度问题时最有用。

例如 - 操作系统任务是优先队列的最佳示例 - 它比低优先级任务（在后台下载更新）执行高优先级任务。任务调度程序可以允许高优先级任务先运行。

在 Python 中实现优先队列有多种方法。让我们通过以下方法来理解。

手动排序列表

我们可以使用排序的 Python 列表作为优先队列，以便快速识别和删除最小和最大的元素。但是插入新元素很慢，因为它需要 O(n) 操作。

因此，当优先队列的插入次数很少时，排序列表会很有效。

让我们理解以下示例 -

示例 -

输出

(1, 'Mango')
(2, 'Apple')
(3, 'Banana')

queue.PriorityQueue 类

这个优先队列在内部使用 heapq 实现，并具有相同的时间和空间复杂度。

区别在于优先队列是协调的，并为后端的多个并发事件和消费者提供锁定语义。

示例 -

输出

(1, 'Banana')
(2, 'Apple')
(3, 'Mango')

我们可以在 Python 程序中选择任何优先队列实现，但请记住，queue.PriorityQueue 是一个不错的默认选择。

结论

我们已经讨论了队列的所有基本概念及其实现。它类似于标准列表，但在性能方面总是更好。我们还定义了优先队列及其各种实现方法。