在本教程中，我们将讨论队列的基本概念和内置队列类，并使用 Python 代码实现它。
什么是队列？
队列是一种线性类型的数据结构，用于按顺序存储数据。队列的概念基于先进先出，意思是“先进先出”。它也被称为“先到先得”。队列有前后两端。下一个元素从后端插入，从前端移除。
例如- 计算机科学实验室有 20 台计算机，连接到一台打印机。学生们想打印他们的论文；打印机将打印第一个任务和第二个任务，依此类推。如果我们是最后一个，我们需要等待，直到所有其他的任务完成，在我们之前。
操作系统管理用于处理计算机内各种进程的队列。
Python 中的操作
我们可以在队列中执行以下操作。
- 入队- 入队是我们向队列中添加项目的操作。如果队列已满，则是队列的一个条件，排队的时间复杂度为 O(1) 。
- 出列- 出列是我们从队列中移除一个元素的操作。元素的移除顺序与插入顺序相同。如果队列为空，这是队列下溢的一个条件。出列的时间复杂度为 O(1) 。
- 前端- 在前端插入一个元素。战线的时间复杂性是 O(1) 。
- 后端- 从后端移除元件..后方的时间复杂度是 O(1) 。
队列中可用的方法
Python 提供了以下方法，常用于执行 Queue 中的操作。
- put(item) - 该函数用于将元素插入队列。
- get() - 这个函数用于从队列中提取元素。
- 空()- 该功能用于检查队列是否为空。如果队列为空，则返回 true。
- qsize - 这个函数返回队列的长度。
- full() - 如果队列已满则返回 true 否则为假。
我们将在下面的章节中学习这些功能。
内置的 Python 列表
该列表可以用作队列，但不适合性能角度。Python 提供了内置方法 insert() 和 pop() 功能来添加和移除元素。列表非常慢，因为如果我们向列表中插入一个新元素，所有元素都需要移位一位。这需要时间。所以建议用列表代替队列。让我们理解下面这个列表如何被用作队列的例子。
示例-
que = []
que.append('Apple')
que.append('Mango')
que.append('Papaya')
print(que)
# List is slow!
print(que.pop(0))
输出:
['Apple', 'Mango', 'Papaya']
Apple
解释-
我们已经在上面的代码中定义了空列表，并使用 append() 方法插入了一些元素。它会在列表的末尾添加一个元素。
将元素添加到队列(入队)
我们可以将元素从添加到后端。这个过程也被称为入队。我们创建了一个队列类，在这里我们将实现先进先出的概念。让我们理解下面的例子。
示例-
class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# Insert method to add element
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
def size(self):
return len(self.queue)
TheQueue = Queue()
TheQueue.add_element("Apple")
TheQueue.add_element("Mango")
TheQueue.add_element("Guava")
TheQueue.add_element("Papaya")
print("The length of Queue: ",TheQueue.size())
输出:
The length of Queue: 4
从队列中删除元素(出列)
我们可以从后端移除元素。这个过程称为出列。在下面的示例中，我们使用内置的 pop()方法从列表中移除一个元素。
示例-
class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# Insert method to add element
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
# Pop method to remove element
def remove_element(self):
if len(self.queue)>0:
return self.queue.pop()
return ("Queue is Empty")
que = Queue()
que.add_element("January")
que.add_element("February")
que.add_element("March")
que.add_element("April")
print(que)
print(que.remove_element())
print(que.remove_element())
输出:
January
February
解释-
在上面的代码中，我们定义了一个名为 Queue 的类和其中的构造器。我们给队列变量分配了一个列表构造器。然后，我们定义了两种方法- 添加 _ 元素()和移除 _ 元素()。在 add_element() 块中，我们检查该值是否不在队列中。如果值不存在，则插入元素。
在 remove_element() 功能块中，我们检查队列是否下溢的条件。如果返回 false，则逐个移除该元素。
对队列排序
在下面的例子中，我们已经对队列的元素进行了排序。
示例-
import queue
q = queue.Queue()
q.put(14)
q.put(27)
q.put(11)
q.put(4)
q.put(1)
# Here, we use bubble sort algorithm for sorting
n = q.qsize()
for i in range(n):
# Remove the element
x = q.get()
for j in range(n-1):
# Remove the element
y = q.get()
if x > y :
# put the smaller element at the beginning of the queue
q.put(y)
else:
# the smaller one is put at the start of the queue
q.put(x)
x = y # The greater element is replaced by the x and check again
q.put(x)
while (q.empty() == False):
print(q.queue[0], end = " ")
q.get()
输出:
1 4 11 14 27
queue模块
Python 提供了queue模块来实现多生产者、多消费者队列。queue模块提供了专门用于线程编程的队列类。队列类实现了所有必需的锁定语义。
我们可以使用内置队列类执行所有操作。
使用队列。队列类
queue模块包含几个类。队列是其中重要的一类。这在并行计算和多道程序设计中非常有用。让我们理解下面的队列示例。队列类 0uii
示例-
from queue import Queue
que = Queue()
que.put('Apple')
que.put('Mango')
que.put('Papaya')
print(que)
print(que.get())
print(que.get())
print(que.get())
print(que.get_nowait())
print(que.get())
输出:
<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:Pythonlibqueue.py", line 198, in get_nowait
return self.get(block=False)
File "C:Pythonlibqueue.py", line 167, in get
raise Empty
_queue.Empty
使用集合
collection.deque 类用于实现双端队列，支持从两端添加和移除元素。完成这个过程需要 O(1)个时间。
deque 类可以在 Queue 中使用，也可以作为栈使用，因为它可以有效地移除和添加元素。
对于 Python 标准库中的队列数据结构来说， collection.deque 可以是一个不错的选择。
示例-
from collections import deque
que = deque()
que.append('Apple')
que.append('Mango')
que.append('Banana')
print(que)
deque(['Apple ', 'Mango', 'Banana'])
print(que.popleft())
print(que.popleft())
print(que.popleft())
que.popleft()
输出:
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
多进程。队列类
多进程。队列类用于实现由多流工作人员并行处理的排队项目。多进程。队列在进程之间共享数据，并且可以存储任何可酸洗的对象。让我们理解下面的例子。
示例-
from multiprocessing import Queue
que = Queue()
que.put('Apple')
que.put('Mango')
que.put('Banana')
print(que)
print(que.get())
print(que.get())
print(que.get())
输出:
<multiprocessing.queues.Queue object at 0x000002CA073356A0>
Apple
Mango
Banana
Python 中的优先级队列
优先级队列是数据结构中一种特殊类型的队列。顾名思义，它根据元素的优先级排序元素和出列。
与普通队列不同，它检索优先级最高的元素，而不是下一个元素。单个元素的优先级由应用于它们的键的顺序决定。
优先级队列最有利于处理基于优先级的任务调度问题。
例如- 操作系统任务是优先级队列的最佳示例-它执行优先级较高的任务，而不是优先级较低的任务(在后台下载更新)。任务计划程序可以允许优先级最高的任务先运行。
在 Python 中，有多种方法可以实现优先级队列。让我们从以下几个方面来理解。
手动排序列表
我们可以使用排序后的 Python 列表作为优先级队列，快速识别和删除较小和最大的元素。但是插入新元素很慢，因为它需要 O(n) 个操作。
因此，当优先级队列中的插入很少时，排序列表会很有效。
让我们理解下面的例子-
示例-
pri_que = []
pri_que.append((2, 'Apple'))
pri_que.append((1, 'Mango'))
pri_que.append((3, 'Banana'))
# NOTE: Remember to re-sort every time
# a new element is inserted.
pri_que.sort(reverse=True)
while pri_que:
next_item = pri_que.pop()
print(next_item)
输出:
(1, 'Mango')
(2, 'Apple')
(3, 'Banana')
排队。优先级队列类
这个优先级队列实现在内部使用 heapq ，并且共享相同的时间和空间复杂度。
不同之处在于优先级队列是协调的，并提供锁定语义来支持多个并发事件和消费者。
示例-
from queue import PriorityQueue
q = PriorityQueue()
q.put((2, 'Apple'))
q.put((1, 'Banana'))
q.put((3, 'Mango'))
while not q.empty():
next_item = q.get()
print(next_item)
输出:
(1, 'Banana')
(2, 'Apple')
(3, 'Mango')
我们可以在 Python 程序中选择任何优先级队列实现，但是请记住队列。优先级队列是不错的默认选择。
结论
我们已经讨论了队列的所有基本概念及其实现。它类似于标准列表，但就性能而言，它总是更好。我们还定义了优先级队列及其各种实现方式。