Python教程-Python中的队列

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

什么是队列？

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

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

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

Python中的操作

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

入队 - 入队是将项目添加到队列的操作。如果队列已满，它是队列的条件入队的时间复杂度为O(1)。
出队 - 出队是从队列中移除元素的操作。元素按插入的顺序移除。如果队列为空，它是队列下溢的条件。出队的时间复杂度为O(1)。
前端 - 元素被插入在前端。前端的时间复杂度为O(1)。
后端 - 元素从后端移除。后端的时间复杂度为O(1)。

队列中可用的方法

Python提供了以下常用于队列操作的方法。

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

我们将在以下部分学习这些函数。

内置的Python列表

列表可以用作队列，但从性能的角度来看不太适合。Python提供了内置方法insert()和pop()函数来添加和删除元素。列表相当慢，因为如果我们向列表插入新元素，所有元素都需要向前移动一个位置。它需要O(n)的时间。因此，建议使用队列而不是列表。让我们了解以下示例，说明列表可以用作队列。

示例 -

que = []  
  
que.append('Apple')  
que.append('Mango')  
que.append('Papaya')  
  
print(que)  
  
# List is slow!  
print(que.pop(0))

输出：

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

解释 -

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

向队列添加元素（入队）

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

示例 -

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的类和构造函数。我们将列表构造函数分配给queue变量。然后，我们定义了两个方法 - add_element() 和 remove_element()。在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

队列模块

Python提供了队列模块来实现多生产者、多消费者队列。队列模块提供了Queue类，特别用于线程编程。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:\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标准库中作为队列数据结构可以是一个不错的选择。

示例 -

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

multiprocessing.Queue类

multiprocessing.Queue类用于实现并行处理的队列项目，由多个工作者并行处理。multiprocessing.Queue在进程之间共享数据，并且可以存储任何可封送的对象。让我们了解以下示例。

示例 -

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')

queue.PriorityQueue类

这个优先队列类使用内部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程序中选择任何优先队列实现，但请记住queue.PriorityQueue是一个很好的默认选择。

结论

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

Python教程-Python中的队列

什么是队列？

Python中的操作

队列中可用的方法

内置的Python列表

向队列添加元素（入队）

从队列中删除元素（出队）

对队列进行排序

队列模块

使用queue.Queue类

使用collection.deque类

multiprocessing.Queue类

Python中的优先队列

手动排序的列表

queue.PriorityQueue类

结论

推荐文章

其它