您的位置:

Python 中的队列

在本教程中,我们将讨论队列的基本概念和内置队列类,并使用 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:\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 类用于实现双端队列,支持从两端添加和移除元素。完成这个过程需要 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 程序中选择任何优先级队列实现,但是请记住队列。优先级队列是不错的默认选择。

结论

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