Python中的队列|极客笔记

Python中的队列

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

什么是队列

队列是一种线性的数据结构，用于按顺序存储数据。队列的概念基于先进先出（FIFO）的原则。它也被称为“先来先服务”。队列有两端，前端（front）和后端（rear）。下一个元素从后端插入，从前端删除。

例如 – 计算机科学实验室有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)的时间。因此，在队列的地方推荐使用列表。让我们来看下面的示例，了解如何将列表用作队列。

示例

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

从队列中移除元素（Dequeue）

我们可以从队列的后端移除元素。这个过程叫做dequeue。在以下示例中，我们使用内置的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类

队列模块包含了几个类。队列是其中一个重要的类。在并行计算和多程序设计中非常有用。让我们理解下面的队列示例。Queue class0uii

示例

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

多进程队列类

多进程队列类用于通过多个并发工作进程实现并行处理的队列项目。多进程队列类在进程之间共享数据，并且可以存储任何可以序列化的对象。让我们了解以下示例。

示例

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

队列.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)

输出: