0. 學(xué)習(xí)目標(biāo)

棧和隊(duì)列是在程序設(shè)計(jì)中常見的數(shù)據(jù)類型，從數(shù)據(jù)結(jié)構(gòu)的角度來講，棧和隊(duì)列也是線性表，是操作受限的線性表，它們的基本操作是線性表操作的子集，但從數(shù)據(jù)類型的角度來講，它們與線性表又有著巨大的不同。本節(jié)將介紹隊(duì)列的定義及其不同實(shí)現(xiàn)，并且給出隊(duì)列的一些實(shí)際應(yīng)用。
通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

• 隊(duì)列的基本概念及不同實(shí)現(xiàn)方法
• 隊(duì)列基本操作的實(shí)現(xiàn)及時(shí)間復(fù)雜度
• 利用隊(duì)列的基本操作實(shí)現(xiàn)復(fù)雜算法

1. 隊(duì)列的基本概念

1.1 隊(duì)列的基本概念

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

在隊(duì)列中，數(shù)據(jù)到達(dá)的順序很重要。最新添加的元素位于必須在隊(duì)尾，在隊(duì)列中時(shí)間最長的元素則排在最前面，這種排序原則被稱作先進(jìn)先出 (first in first out，F(xiàn)IFO），或后進(jìn)后出 (last in first out, LILO)。

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

通過觀察元素的添加和移除順序，就可以快速理解隊(duì)列所蘊(yùn)含的思想。下圖展示了隊(duì)列元素的入隊(duì)和出隊(duì)過程，隊(duì)列中元素的插入順序和移除順序是完全相同的。

1.2 隊(duì)列抽象數(shù)據(jù)類型

除了主要的操作(入隊(duì)和出隊(duì))外，隊(duì)列還具有初始化、判隊(duì)空和求隊(duì)長度等輔助操作。具體而言，隊(duì)列的抽象數(shù)據(jù)類型定義如下：

1.3 隊(duì)列的應(yīng)用場景

隊(duì)列具有廣泛的應(yīng)用場景，例如：

• 在作業(yè)具有相同優(yōu)先級(jí)的前提下，操作系統(tǒng)會(huì)按照作業(yè)的到達(dá)順序安排作業(yè)；
• 擊鍵操作被放入一個(gè)類似于隊(duì)列的緩沖區(qū)，以便對(duì)應(yīng)的字符按正確的順序顯示；
• 模擬現(xiàn)實(shí)世界的隊(duì)列；
• 多道程序設(shè)計(jì)；
• 異步數(shù)據(jù)傳輸；

除了以上應(yīng)用外，我們?cè)谥蟮膶W(xué)習(xí)中還將看到隊(duì)列用作許多算法的輔助數(shù)據(jù)結(jié)構(gòu)。

2. 隊(duì)列的實(shí)現(xiàn)

和線性表一樣，隊(duì)列同樣有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)表示方式。

2.1 順序隊(duì)列的實(shí)現(xiàn)

類似于順序棧，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)利用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾依次存放，同時(shí)需要用兩個(gè)指針 front 和 rear 分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。初始化空隊(duì)列時(shí)，front=rear=0，當(dāng)元素入隊(duì)時(shí)，rear 加 1，而元素出隊(duì)時(shí)，front 加 1，如下所示：

從以上示例中，可以很清楚地看到位于隊(duì)頭之前的空間被浪費(fèi)了，為了解決這一問題，我們可以假設(shè)順序隊(duì)列為環(huán)狀空間，將最后一個(gè)元素和第一個(gè)元素視為連續(xù)的，如下圖所示：

從上圖可以看出，當(dāng)隊(duì)列滿時(shí)與隊(duì)列空時(shí)，都有front=rear，因此無法通過 front==rear 來判斷隊(duì)列是否已滿。針對(duì)這一問題，有兩種解決方法：1) 設(shè)置標(biāo)志來指示隊(duì)列中是否還有空閑空間；2) 放棄一個(gè)元素空間，即當(dāng) front 指針在 rear 指針的下一位時(shí) ((rear+1)%max_size=front) 隊(duì)列為滿。以下實(shí)現(xiàn)使用第二種方案。

同樣順序隊(duì)列可以是固定長度和動(dòng)態(tài)長度，當(dāng)隊(duì)列滿時(shí)，定長順序隊(duì)列會(huì)拋出棧滿異常，動(dòng)態(tài)順序隊(duì)列則會(huì)動(dòng)態(tài)申請(qǐng)空閑空間。

2.1.1 隊(duì)列的初始化

順序隊(duì)列的初始化需要 4 部分信息：queue 列表用于存儲(chǔ)數(shù)據(jù)元素，max_size 用于存儲(chǔ) queue 列表的最大長度，以及 front 和 rear 分別用于記錄隊(duì)頭元素和隊(duì)尾元素的索引：

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 求隊(duì)列長度

由于 front 和 rear 分別用于記錄隊(duì)頭元素和隊(duì)尾元素的索引，因此我們可以方便的計(jì)算出隊(duì)列的長度；同時(shí)我們需要考慮隊(duì)列為循環(huán)隊(duì)列，front 可能大于 rear，不能直接通過 rear-front，我們需要利用公式計(jì)算解決此問題：

Python 實(shí)現(xiàn)如下：

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

2.1.3 判隊(duì)列空

根據(jù) front 和 rear 的值可以方便的判斷隊(duì)列是否為空：

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

2.1.4 判隊(duì)列滿

根據(jù) front 和 rear 的值可以方便的判斷隊(duì)列是否還有空余空間：

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

2.1.5 入隊(duì)

入隊(duì)時(shí)，需要首先判斷隊(duì)列中是否還有空閑空間，然后根據(jù)隊(duì)列為定長順序隊(duì)列或動(dòng)態(tài)順序隊(duì)列，入隊(duì)操作稍有不同：

[定長順序隊(duì)列的入隊(duì)操作] 如果隊(duì)滿，則引發(fā)異常：

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

[動(dòng)態(tài)順序隊(duì)列的入隊(duì)操作] 如果隊(duì)列滿，則首先申請(qǐng)新空間，然后再執(zhí)行入隊(duì)操作：

    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

入隊(duì)的時(shí)間復(fù)雜度為O(1)。這里需要注意的是，雖然當(dāng)動(dòng)態(tài)順序隊(duì)列滿時(shí)，原隊(duì)列中的元素需要首先復(fù)制到新隊(duì)列中，然后添加新元素，但參考《順序表及其操作實(shí)現(xiàn)》中順序表追加操作的介紹，由于 n 次入隊(duì)操作的總時(shí)間T(n) 與)O(n) 成正比，因此隊(duì)棧的攤銷時(shí)間復(fù)雜度可以認(rèn)為是O(1)。

2.1.6 出隊(duì)

若隊(duì)列不空，則刪除并返回隊(duì)頭元素：

    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 求隊(duì)頭元素

若隊(duì)列不空，則返回隊(duì)頭元素：

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

2.2 鏈隊(duì)列的實(shí)現(xiàn)

隊(duì)列的另一種存儲(chǔ)表示方式是使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此也常稱為鏈隊(duì)列，其中 enqueue 操作是通過在鏈表尾部插入元素來實(shí)現(xiàn)的，dequeue 操作是通過從頭部刪除節(jié)點(diǎn)來實(shí)現(xiàn)的。

2.2.1 隊(duì)列結(jié)點(diǎn)

隊(duì)列的結(jié)點(diǎn)實(shí)現(xiàn)與鏈表并無差別：

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

2.2.2 隊(duì)列的初始化

隊(duì)列的初始化函數(shù)中，使其隊(duì)頭指針 front 和 rear 均指向 None，并初始化隊(duì)列長度：

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

2.2.3 求隊(duì)列長度

返回 size 的值用于求取隊(duì)列的長度，如果沒有 size 屬性，則需要遍歷整個(gè)鏈表才能得到隊(duì)列長度：

    def size(self):
        return self.num

2.2.4 判隊(duì)列空

根據(jù)隊(duì)列的長度可以很容易的判斷隊(duì)列是否為空隊(duì)列：

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

2.2.5 入隊(duì)

入隊(duì)時(shí)，在隊(duì)尾插入新元素，并且需要將隊(duì)尾指針 rear 指向新元素，如果隊(duì)列為空，需要將隊(duì)頭指針 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 出隊(duì)

若隊(duì)列不空，則刪除并返回隊(duì)頭元素，并且需要更新隊(duì)頭指針 front 指向原隊(duì)頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)，若出隊(duì)元素尾隊(duì)中最后一個(gè)結(jié)點(diǎn)，則更新隊(duì)尾指針 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 求隊(duì)頭元素

若隊(duì)列不空，則返回隊(duì)頭元素：

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

2.3 隊(duì)列的不同實(shí)現(xiàn)對(duì)比

隊(duì)列的不同實(shí)現(xiàn)對(duì)比與棧的不同實(shí)現(xiàn)類似，可以參考《棧及其操作實(shí)現(xiàn)》。

3. 隊(duì)列應(yīng)用

接下來，我們首先測試上述實(shí)現(xiàn)的隊(duì)列，以驗(yàn)證操作的有效性，然后利用實(shí)現(xiàn)的基本操作來解決實(shí)際算法問題。

3.1 順序隊(duì)列的應(yīng)用

首先初始化一個(gè)順序隊(duì)列 queue，然后測試相關(guān)操作：

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

測試程序輸出結(jié)果如下：

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

3.2 鏈隊(duì)列的應(yīng)用

首先初始化一個(gè)鏈隊(duì)列 queue，然后測試相關(guān)操作：

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

測試程序輸出結(jié)果如下：

隊(duì)列空? True
入隊(duì)元素： 0
入隊(duì)元素： 1
入隊(duì)元素： 2
入隊(duì)元素： 3
隊(duì)頭元素： 0
隊(duì)列長度為： 4
出隊(duì)元素： 0
出隊(duì)元素： 1
出隊(duì)元素： 2
出隊(duì)元素： 3

3.3 利用隊(duì)列基本操作實(shí)現(xiàn)復(fù)雜算法

考慮經(jīng)典的約瑟夫斯環(huán)問題，n 個(gè)人圍成一圈，從第 1 個(gè)人開始報(bào)數(shù)，第 m 個(gè)將被淘汰，重復(fù)上述過程，直到只剩下一個(gè)人，其余人都將被淘汰。

我們使用隊(duì)列來模擬一個(gè)環(huán)，如下圖所示，從隊(duì)列的頭部開始，將位于隊(duì)首的人移出隊(duì)列并立刻將其插入隊(duì)列的尾部，之后此人會(huì)一直等待，直到其再次到達(dá)隊(duì)列的頭部。在出列和入列 m-1 次之后，位于隊(duì)列頭部的人出局(即第 m 個(gè)人)，然后新一輪游戲開始；如此反復(fù)，直到隊(duì)列中只剩下一個(gè)人(隊(duì)列的大小為 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)

程序輸出結(jié)果如下：

幸存的人為 A

以上就是Python數(shù)據(jù)結(jié)構(gòu)之隊(duì)列詳解的詳細(xì)內(nèi)容，更多關(guān)于Python隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論