Python資料結構之佇列詳解

2022-03-21 13:02:01

0. 學習目標

棧和佇列是在程式設計中常見的資料型別，從資料結構的角度來講，棧和佇列也是線性表，是操作受限的線性表，它們的基本操作是線性表操作的子集，但從資料型別的角度來講，它們與線性表又有著巨大的不同。本節將介紹佇列的定義及其不同實現，並且給出佇列的一些實際應用。
通過本節學習，應掌握以下內容：

佇列的基本概念及不同實現方法
佇列基本操作的實現及時間複雜度
利用佇列的基本操作實現複雜演演算法

1. 佇列的基本概念

1.1 佇列的基本概念

佇列 (Queue) 是插入和刪除操作分別被限制在序列兩端的線性表(新元素從一段插入其中，則只能從另一端刪除已有元素)，對於佇列而言，允許插入元素的一端稱為隊尾 (rear)，而允許取出元素的一段則稱為隊頭 (front)。

在佇列中，資料到達的順序很重要。最新新增的元素位於必須在隊尾，在佇列中時間最長的元素則排在最前面，這種排序原則被稱作先進先出 (first in first out，FIFO），或後進後出 (last in first out, LILO)。

佇列在現實中的例子隨處可見，我們生活中就餐所需要進行的排隊就是一個佇列的現範例子，最早進入佇列的人可以首先就餐，而後來者需要排於隊尾等待。假設佇列為 Q=(a₀,a₁,...,a_n)，則隊頭元素為a₀,a_n為隊尾元素，佇列中元素按a₀,a₁,...,a_n的順序入隊 (enqueue)，出隊 (dequeue) 也只能按照這個順序依次退出，隊頭元素是第一個出隊 (dequeue) 的元素，而只有a₀,a₁,...,a_n-1在都出隊後，才a_n 能退出佇列。下圖是一個簡單的佇列範例：

通過觀察元素的新增和移除順序，就可以快速理解佇列所蘊含的思想。下圖展示了佇列元素的入隊和出隊過程，佇列中元素的插入順序和移除順序是完全相同的。

1.2 佇列抽象資料型別

除了主要的操作(入隊和出隊)外，佇列還具有初始化、判隊空和求隊長度等輔助操作。具體而言，佇列的抽象資料型別定義如下：

1.3 佇列的應用場景

佇列具有廣泛的應用場景，例如：

在作業具有相同優先順序的前提下，作業系統會按照作業的到達順序安排作業；
擊鍵操作被放入一個類似於佇列的緩衝區，以便對應的字元按正確的順序顯示；
模擬現實世界的佇列；
多道程式設計；
非同步資料傳輸；

除了以上應用外，我們在之後的學習中還將看到佇列用作許多演演算法的輔助資料結構。

2. 佇列的實現

和線性表一樣，佇列同樣有順序儲存和鏈式儲存兩種儲存表示方式。

2.1 順序佇列的實現

類似於順序棧，佇列的順序儲存結構利用一組地址連續的儲存單元依次存放從佇列頭到佇列尾依次存放，同時需要用兩個指標 front 和 rear 分別指示佇列頭元素和佇列尾元素的位置。初始化空佇列時，front=rear=0，當元素入隊時，rear 加 1，而元素出隊時，front 加 1，如下所示：

從以上範例中，可以很清楚地看到位於隊頭之前的空間被浪費了，為了解決這一問題，我們可以假設順序佇列為環狀空間，將最後一個元素和第一個元素視為連續的，如下圖所示：

從上圖可以看出，當佇列滿時與佇列空時，都有front=rear，因此無法通過 front==rear 來判斷佇列是否已滿。針對這一問題，有兩種解決方法：1) 設定標誌來指示佇列中是否還有空閒空間；2) 放棄一個元素空間，即當 front 指標在 rear 指標的下一位時 ((rear+1)%max_size=front) 佇列為滿。以下實現使用第二種方案。

同樣順序佇列可以是固定長度和動態長度，當佇列滿時，定長順序佇列會丟擲棧滿異常，動態順序佇列則會動態申請空閒空間。

2.1.1 佇列的初始化

順序佇列的初始化需要 4 部分資訊：queue 列表用於儲存資料元素，max_size 用於儲存 queue 列表的最大長度，以及 front 和 rear 分別用於記錄隊頭元素和隊尾元素的索引：

class Queue:
    def __init__(self, max_size=5):
        self.max_size = max_size
        self.queue = [None] * self.max_size
        self.front = 0
        self.rear = 0

2.1.2 求佇列長度

由於 front 和 rear 分別用於記錄隊頭元素和隊尾元素的索引，因此我們可以方便的計算出佇列的長度；同時我們需要考慮佇列為迴圈佇列，front 可能大於 rear，不能直接通過 rear-front，我們需要利用公式計算解決此問題：

Python 實現如下：

    def size(self):
        return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判佇列空

根據 front 和 rear 的值可以方便的判斷佇列是否為空：

    def isempty(self):
        return self.rear==self.front

2.1.4 判佇列滿

根據 front 和 rear 的值可以方便的判斷佇列是否還有空餘空間：

    def isfull(self):
        return ((self.rear+1) % self.max_size == self.front)

2.1.5 入隊

入隊時，需要首先判斷佇列中是否還有空閒空間，然後根據佇列為定長順序佇列或動態順序佇列，入隊操作稍有不同：

[定長順序佇列的入隊操作] 如果隊滿，則引發異常：

    def enqueue(self, data):
        if not self.isfull():
            self.queue[self.rear] = data
            self.rear = (self.rear+1) % self.max_size
        else:
            raise IndexError("Full Queue Exception")

[動態順序佇列的入隊操作] 如果佇列滿，則首先申請新空間，然後再執行入隊操作：

    def resize(self):
        new_size = 2 * self.max_size
        new_queue = [None] * new_size
        for i in range(self.max_size):
            new_queue[i] = self.queue[i]
        self.queue = new_queue
        self.max_size = new_size

    def enqueue(self, data):
        if self.isfull():
            self.resize()
        self.queue[self.rear] = data
        self.rear = (self.rear+1) % self.max_size

入隊的時間複雜度為O(1)。這裡需要注意的是，雖然當動態順序佇列滿時，原佇列中的元素需要首先複製到新佇列中，然後新增新元素，但參考《順序表及其操作實現》中順序表追加操作的介紹，由於 n 次入隊操作的總時間T(n) 與)O(n) 成正比，因此隊棧的攤銷時間複雜度可以認為是O(1)。

2.1.6 出隊

若佇列不空，則刪除並返回隊頭元素：

    def dequeue(self):
        if not self.isempty():
            result = self.queue[self.front]
            self.front = (self.front+1) % self.max_size
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.1.7 求隊頭元素

若佇列不空，則返回隊頭元素：

    def head(self):
        if not self.isempty():
            result = self.queue[self.front]
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.2 鏈佇列的實現

佇列的另一種儲存表示方式是使用鏈式儲存結構，因此也常稱為鏈佇列，其中 enqueue 操作是通過在連結串列尾部插入元素來實現的，dequeue 操作是通過從頭部刪除節點來實現的。

2.2.1 佇列結點

佇列的結點實現與連結串列並無差別：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.2 佇列的初始化

佇列的初始化函數中，使其隊頭指標 front 和 rear 均指向 None，並初始化佇列長度：

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.num = 0

2.2.3 求佇列長度

返回 size 的值用於求取佇列的長度，如果沒有 size 屬性，則需要遍歷整個連結串列才能得到佇列長度：

    def size(self):
        return self.num

2.2.4 判佇列空

根據佇列的長度可以很容易的判斷佇列是否為空佇列：

    def isempty(self):
        return self.num <= 0

2.2.5 入隊

入隊時，在隊尾插入新元素，並且需要將隊尾指標 rear 指向新元素，如果佇列為空，需要將隊頭指標 front 也指向此元素：

    def enqueue(self, data):
        node = Node(data)
        if self.front is None:
            self.rear = node
            self.front = self.rear
        else:
            self.rear.next = node
            self.rear = node
        self.num += 1

2.2.6 出隊

若佇列不空，則刪除並返回隊頭元素，並且需要更新隊頭指標 front 指向原隊頭結點的後繼結點，若出隊元素尾隊中最後一個結點，則更新隊尾指標 rear：

    def dequeue(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        self.front = self.front.next
        self.num -= 1
        if self.isempty():
            self.rear = self.front
        return result

2.2.7 求隊頭元素

若佇列不空，則返回隊頭元素：

    def head(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        return result

2.3 佇列的不同實現對比

佇列的不同實現對比與棧的不同實現類似，可以參考《棧及其操作實現》。

3. 佇列應用

接下來，我們首先測試上述實現的佇列，以驗證操作的有效性，然後利用實現的基本操作來解決實際演演算法問題。

3.1 順序佇列的應用

首先初始化一個順序佇列 queue，然後測試相關操作：

# 初始化一個最大長度為5的佇列
q = Queue(5)
print('佇列空?', q.isempty())
for i in range(4):
    print('入隊元素：', i)
    q.enqueue(i)
print('佇列滿?', q.isfull())
print('隊頭元素：', q.head())
print('佇列長度為：', q.size())
while not q.isempty():
    print('出隊元素：', q.dequeue())

測試程式輸出結果如下：

佇列空? True
入隊元素： 0
入隊元素： 1
入隊元素： 2
入隊元素： 3
# 佇列中棄用一個空間，因此佇列中有4個元素即滿
佇列滿? True
隊頭元素： 0
佇列長度為： 4
出隊元素： 0
出隊元素： 1
出隊元素： 2
出隊元素： 3

3.2 鏈佇列的應用

首先初始化一個鏈佇列 queue，然後測試相關操作：

# 初始化新佇列
q = Queue()
print('佇列空?', q.isempty())
for i in range(4):
    print('入隊元素：', i)
    q.enqueue(i)
print('隊頭元素：', q.head())
print('佇列長度為：', q.size())
while not q.isempty():
    print('出隊元素：', q.dequeue())

測試程式輸出結果如下：

佇列空? True
入隊元素： 0
入隊元素： 1
入隊元素： 2
入隊元素： 3
隊頭元素： 0
佇列長度為： 4
出隊元素： 0
出隊元素： 1
出隊元素： 2
出隊元素： 3

3.3 利用佇列基本操作實現複雜演演算法

考慮經典的約瑟夫斯環問題，n 個人圍成一圈，從第 1 個人開始報數，第 m 個將被淘汰，重複上述過程，直到只剩下一個人，其餘人都將被淘汰。

我們使用佇列來模擬一個環，如下圖所示，從佇列的頭部開始，將位於隊首的人移出佇列並立刻將其插入佇列的尾部，之後此人會一直等待，直到其再次到達佇列的頭部。在出列和入列 m-1 次之後，位於佇列頭部的人出局(即第 m 個人)，然後新一輪遊戲開始；如此反覆，直到佇列中只剩下一個人(佇列的大小為 1 )。

def Josephus(name_list, m):
    queue = Queue()
    for name in name_list:
        queue.enqueue(name)
    while queue.size() > 1:
        for i in range(m-1):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.head()
# n=6, m=5
result = Josephus(["A", "B", "C", "D", "E", "F"], 5)
print('倖存的人為', result)

程式輸出結果如下：