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 程序中選擇任何優先級隊列實現，但是請記住隊列。優先級隊列是不錯的默認選擇。

結論

我們已經討論了隊列的所有基本概念及其實現。它類似於標準列表，但就性能而言，它總是更好。我們還定義了優先級隊列及其各種實現方式。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/242774.html