在程式設計的廣闊天地中，資料結構扮演著不可或缺的角色。它們猶如組織大師，協助我們以高效的方式整理資料，以便後續有效運用。在眾多資料結構中，佇列因其簡潔明瞭而脫穎而出。
本文將深入探討佇列的概念，並展示如何在Python中實現它。
什麼是佇列？
佇列是一種線性資料結構，其運作遵循先進先出（FIFO）原則，這與堆疊資料結構的後進先出（LIFO）原則截然不同。
不妨將佇列想像成電影院售票處的排隊隊伍。觀察隊伍，可以發現只有當第一個人完成購票後，第二個人才能上前。這體現了先進先出的原則：先到的人先完成任務。生活中，我們經常遇到類似的佇列場景。
佇列資料結構亦遵循相同的原則。現在您對佇列及其運作原理有了初步認識，讓我們接著探討可以對佇列執行的各種操作。
佇列的常見操作
類似於堆疊，佇列資料結構也具備兩個主要操作。
入隊（enqueue(資料)）
將新的資料添加到佇列的末尾，這個位置稱為「尾部」。
出隊（dequeue()）
從佇列的前端移除資料，這個位置稱為「頭部」。
讓我們透過圖示來更深入理解佇列的操作。俗話說，一張圖片勝過千言萬語。
為了獲取更多關於佇列的資訊，我們可以編寫一些輔助函數。輔助函數的數量沒有限制，但我們將重點介紹以下幾個最重要的函數。
尾部（rear()）
返回佇列尾部的第一個元素。
頭部（front()）
返回佇列頭部的第一個元素。
是否為空（is_empty()）
返回佇列是否為空。
您是否覺得概念性的討論有些枯燥乏味？對我來說是肯定的！
然而，若不理解這些概念，我們將無法有效地進行後續的實作。在著手實作之前，我們必須透徹理解相關概念。別擔心，現在是時候開始親自編寫程式碼了。
假設您的電腦上已安裝Python，若沒有，您也可以使用線上編譯器。
佇列的實作
對於程式設計師來說，實現佇列通常不會超過15分鐘。一旦您掌握了竅門，就會覺得易如反掌。或許在看完本教程後，您就能在幾分鐘內完成實作。
在Python中有多種方法可以實現佇列，讓我們逐步探討不同的實作方式。
#1. 使用列表
列表是Python中的一種內建資料類型。我們將使用列表資料類型在類別中實現佇列。我們將引導您逐步完成從頭開始實作佇列資料結構的過程，無需任何模組。現在開始吧！
步驟一：
建立一個名為 Queue 的類別。
class Queue:
pass
步驟二：
我們需要一些變數來儲存類別中佇列的資料。讓我們將其命名為 elements，它將是一個列表。
class Queue:
def __init__(self):
self.elements = []
步驟三：
為了將資料插入佇列，我們需要在類別中定義一個方法。正如我們在本教程前一節討論的，這個方法被稱為 enqueue。
該方法接收一些資料，並將其添加到佇列（元素）中。我們可以利用列表資料類型的 append 方法將資料添加到佇列的尾部。
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
步驟四：
佇列需要有出口，這就是所謂的出隊操作。我想您已經猜到我們要使用列表資料類型的 pop 方法了。無論您猜没猜到，乾杯！
列表資料類型的 pop 方法會從指定索引的列表中刪除一個元素。如果我們沒有提供任何索引，它會刪除列表的最後一個元素。
在這裡，我們需要刪除列表的第一個元素，因此我們必須將索引 0 傳遞給 pop 方法。
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
這足以實現佇列的基本功能。然而，我們還需要輔助函數來測試佇列操作是否正常運作。讓我們也來編寫這些輔助函數。
步驟五：
rear() 方法用於取得佇列的最後一個元素。列表資料類型中的負索引可以幫助我們取得佇列的最後一個元素。
class Queue:
# ...
def rear(self):
return self.elements[-1]
步驟六：
front() 方法用於取得佇列的第一個元素。我們可以透過列表索引來取得佇列的第一個元素。
class Queue:
# ...
def front(self):
return self.elements[0]
步驟七：
is_empty() 方法用於檢查佇列是否為空。我們可以檢查列表的長度。
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
呼！佇列資料結構的實作部分完成了。現在，我們需要建立一個物件供 Queue 類別使用。
讓我們開始吧！
class Queue:
# ...
if __name__ == '__main__':
queue = Queue()
現在，我們有一個佇列物件了。讓我們用一些列操作來測試它。
- 使用 is_empty 方法檢查佇列是否為空，它應該返回 True。
- 使用 enqueue 方法將數字 1、2、3、4、5 添加到佇列中。
- is_empty 方法應該返回 False，請核實。
- 分別使用 front 和 rear 方法列印頭尾元素。
- 使用 dequeue 方法從佇列中刪除元素。
- 檢查頭部元素，它應該返回元素 2。
- 現在，從佇列中移除所有元素。
- is_empty 方法應該返回 True，請核實。
我認為這足以測試我們的佇列實作。請編寫程式碼來測試上述步驟中的每一個操作。
程式碼是您自己寫的嗎？
不用擔心，不是的。
請參考以下程式碼。
class Queue:
def __init__(self):
self.elements = []
def enqueue(self, data):
self.elements.append(data)
return data
def dequeue(self):
return self.elements.pop(0)
def rear(self):
return self.elements[-1]
def front(self):
return self.elements[0]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
queue = Queue()
## checking is_empty method -> True
print(queue.is_empty())
## adding the elements
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
## again checking is_empty method -> False
print(queue.is_empty())
## printing the front and rear elements using front and rear methods respectively -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())
## removing the element -> 1
queue.dequeue()
## checking the front and rear elements using front and rear methods respectively -> 2 5
print(queue.front(), end=' ')
print(queue.rear())
## removing all the elements
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
## checking the is_empty method for the last time -> True
print(queue.is_empty())
我想您已經執行了上述程式碼。您應該會獲得類似於以下結果的輸出。
True False 1 5 2 5 True
我們可以直接使用列表資料類型作為佇列資料結構。上述佇列的實作可以幫助大家更好地理解其他程式語言中的佇列實作。
您還可以透過簡單地建立物件，在專案的不同程式中使用上述佇列類別的實作。
我們已經使用列表資料類型從頭開始實作了佇列。那麼，佇列是否有內建模組呢？答案是肯定的！我們有內建的佇列實作，讓我們來看看它們。
#2. 使用 collections 模組的雙端佇列
雙端佇列可以被實現為佇列。由於它支援從兩端添加和刪除元素，因此我們可以將它用作堆疊和佇列。讓我們看看如何使用雙端佇列實現佇列。
它是使用雙向鏈表這種資料結構實現的。因此，元素的插入和刪除操作具有一致的效能。從中間鏈表訪問元素需要花費 O(n) 的時間。我們可以將它用作佇列，因為我們不需要訪問佇列中的中間元素。
讓我們檢視雙端佇列為我們提供的方法。
- append(data) – 用於將資料添加到佇列
- popleft() – 用於從佇列中刪除第一個元素
沒有直接對應的 front、rear 和 is_empty 方法。我們可以列印整個佇列來代替前後方法。接下來，我們可以使用 len 方法來檢查佇列是否為空。
我們已經依照一系列步驟來測試前一個佇列的實作。讓我們在這裡也遵循相同的一系列步驟。
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
您將會獲得類似於以下輸出的結果。
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. 使用 queue 模組的 Queue 類別
Python 有一個內建模組名為 queue，它提供了一個名為 Queue 的類別來實現佇列。它與我們先前實作的類似。
首先，讓我們檢查 Queue 類別的各種方法。
- put(data) – 將資料添加到佇列或推入佇列
- get() – 從佇列中移除第一個元素並返回它
- empty() – 返回佇列是否為空
- qsize() – 返回佇列的長度
讓我們使用上述方法來實作佇列。
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
請檢視以上程式碼的輸出。
True False 1 2 3 Size 2 4 5 True
Queue 類別中還有其他方法。您可以使用 dir 內建函數來探索它們。
結論
我希望您已經對佇列資料結構及其實作有了全面的了解。佇列就是這樣！您可以在需要以先進先出（FIFO）順序處理資料的不同情境中使用佇列。每當您需要使用佇列時，都可以將它應用於解決問題。
有興趣精通 Python 嗎？不妨參考這些學習資源。
祝您程式設計愉快！🙂👨💻