0. 學習目標

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

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

1. 隊列的基本概念

1.1 隊列的基本概念

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

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

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

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

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

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

1.3 隊列的應用場景

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

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

除了以上應用外，我們在之后的學習中還將看到隊列用作許多算法的輔助數(shù)據(jù)結構。

2. 隊列的實現(xiàn)

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

2.1 順序隊列的實現(xiàn)

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

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

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

同樣順序隊列可以是固定長度和動態(tài)長度，當隊列滿時，定長順序隊列會拋出棧滿異常，動態(tài)順序隊列則會動態(tài)申請空閑空間。

2.1.1 隊列的初始化

順序隊列的初始化需要 4 部分信息：queue 列表用于存儲數(shù)據(jù)元素，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 分別用于記錄隊頭元素和隊尾元素的索引，因此我們可以方便的計算出隊列的長度；同時我們需要考慮隊列為循環(huán)隊列，front 可能大于 rear，不能直接通過 rear-front，我們需要利用公式計算解決此問題：

Python 實現(xiàn)如下：

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

2.1.3 判隊列空

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

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

2.1.4 判隊列滿

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

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

2.1.5 入隊

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

[定長順序隊列的入隊操作] 如果隊滿，則引發(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")

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

    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)。這里需要注意的是，雖然當動態(tài)順序隊列滿時，原隊列中的元素需要首先復制到新隊列中，然后添加新元素，但參考《順序表及其操作實現(xiàn)》中順序表追加操作的介紹，由于 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 鏈隊列的實現(xiàn)

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

2.2.1 隊列結點

隊列的結點實現(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 隊列的初始化

隊列的初始化函數(shù)中，使其隊頭指針 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 判隊列空

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

    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 隊列的不同實現(xiàn)對比

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

3. 隊列應用

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

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 利用隊列基本操作實現(xiàn)復雜算法

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

我們使用隊列來模擬一個環(huán)，如下圖所示，從隊列的頭部開始，將位于隊首的人移出隊列并立刻將其插入隊列的尾部，之后此人會一直等待，直到其再次到達隊列的頭部。在出列和入列 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)

程序輸出結果如下：

幸存的人為 A