在上一期博客中我們學(xué)習(xí)了棧這種結(jié)構(gòu)，本期博客將學(xué)習(xí)一下跟棧很類似的一種結(jié)構(gòu)——隊列。

本期知識點：

1. 順序隊列
2. 循環(huán)隊列
3. 鏈?zhǔn)疥犃?/li>
4. 隊列的應(yīng)用

?? 順序隊列

??什么是隊列？
隊列是一種跟棧很相似的結(jié)構(gòu)。我們知道棧是一種先進(jìn)后出的結(jié)構(gòu)，那么隊列就像一個排隊的隊伍一樣，排在前面的買到東西后就離開，然后下一個繼續(xù)買，而后來的人只能按照規(guī)矩排到他們的后面，也就是說隊列是一種先進(jìn)先出的結(jié)構(gòu)。

?? 什么是順序隊列？
在順序棧中，我們用到了兩個指針“base”和“top”來表示棧底和棧頂元素的下一個位置，在隊列中呢我們也用兩個指針“front”和“rear”來分別表示隊頭元素和隊尾元素的下一個位置。看下圖理解：


從上圖可以看到順序隊列的特性：

• 隊空開始入隊時隊頭隊尾指針指向同一處
• 入隊時是隊尾指針在移動，類似于順序棧的top指針
• 出隊時是隊頭指針在移動
• 在出隊中，若隊頭隊尾指針相遇了，則表明隊空了

同時，它也有一個很明顯的缺點：在出隊的操作中，當(dāng)4出隊后，隊尾隊頭指針都已經(jīng)指向了這個順序隊列的末端，這時如果我們再進(jìn)行入隊的話肯定會發(fā)生隊尾指針的溢出。

但實際上，這個隊列此時明顯是空的。所以，如果我們照著前面那樣來設(shè)計順序隊列的結(jié)構(gòu)的話肯定會造成很大的存儲空間的浪費。對于這個缺點，我們可以在每次出隊后，將隊列中的元素往前移一位，也就是出隊是保持隊頭指針不動，隊尾指針再次移動。

但這樣設(shè)計的話操作又太過于繁瑣，于是，為了彌補(bǔ)順序隊列的不足，我們引入循環(huán)隊列。

?? 循環(huán)隊列

??思想實現(xiàn)

首先，我們需要明確設(shè)計循環(huán)隊列的目的：為了解決順序隊列元素完全出隊后，隊頭隊尾指針指向隊列的末尾而無法再入隊的問題。

那么下面以循環(huán)隊列接著處理上面遺留的問題，假如經(jīng)出隊后，此時隊頭隊尾指針指向了隊列的末尾。

因為是個循環(huán)隊列，所以我們此時再入隊，隊尾指針應(yīng)該繼續(xù)移動，然而隊尾后面已經(jīng)沒有存儲空間了，所以它應(yīng)該指向有空間的地方。那么我們就可以使它指向隊列的“頭部”（這里頭部是相對的頭部，本質(zhì)上來說是沒有頭部的，因為它是一個循環(huán)隊列）。

此時，原本的隊頭指針在尾部，原本的隊尾指針現(xiàn)在出現(xiàn)在了頭部。那么這種情況是不是又回到了一個空的順序隊列呢？

我們要實現(xiàn)的就是使尾部的指針加1后能夠跳到頭部去。實現(xiàn)代碼如下：

rear = (rear + 1) % length # length是隊列的長度

結(jié)合下圖來理解這行代碼的意思：

??初始化

這里我們創(chuàng)建一個關(guān)于隊列的類，所有的操作都通過這個類實例化出的對象調(diào)用相關(guān)的函數(shù)實現(xiàn)。首先是初始化：

class Queue:
    def __init__(self,length):
        self.length = length                # 隊列的長度
        self.elem = [None] * self.length    # 隊列存放的元素
        self.rear = 0                       # 隊尾指針
        self.front = 0                      # 對頭指針

在進(jìn)行其他的操作之前我們要考慮這樣一個問題，在上面所描述的循環(huán)隊列中，初始的空隊列，隊頭隊尾指針是相等的，當(dāng)持續(xù)入隊直至隊滿時，隊頭隊尾指針又是相等的。那么此時這個隊列到底是空的還是滿的呢？為了后續(xù)的操作，我們需要先解決這個問題。

一個初始化的隊列隊頭隊尾指針相等是母庸置疑的，于是我們就以隊頭隊尾指針相等時表示隊空。那么如何來表示隊滿呢？我們可以在隊列的尾部多設(shè)一個空間，當(dāng)將元素入隊至隊滿，隊尾指針就會指向這個另設(shè)的空間，當(dāng)隊滿時隊尾指針再加1就到了隊列頭部與隊頭指針相等，此時就可以以這個條件表示隊滿。

如下圖（紅色格子表示額外使用的空間）：
這個問題解決后，我們就繼續(xù)實現(xiàn)隊列的相關(guān)操作。

??求隊列長度

注意：在循環(huán)隊列中隊列的長度不能用隊尾指針與隊頭指針的差值來表示，因為是一個循環(huán)隊列，隊尾指針可能會出現(xiàn)在隊頭指針的“前面”（相對而言）。

	# 獲取隊列長度
    def get_length(self):
        count = 0           # 計數(shù)器，統(tǒng)計隊列中元素的個數(shù)
        m = self.front		# 為了不影響原本的指針，這里用m，n兩個變量來代替它們進(jìn)行遍歷
        n = self.rear
        while m != n:       # 當(dāng)隊頭隊尾指針不相等時作為循環(huán)執(zhí)行的條件
            count += 1      # 計數(shù)
            m = (m + 1) % self.length   # 隊頭指針向隊尾指針移動
        return count

??入隊

入隊前需要考慮隊列是否已滿，滿了就不能入隊了。判斷條件也就是我們在前面說的那樣，當(dāng)隊尾指針在循環(huán)意義上加1等于隊頭指針時，就表示隊列已滿。

若隊列未滿，則將元素入隊，而后隊尾指針加1

    # 入隊
    def queue_in(self,data):
        if (self.rear + 1) % self.length == self.front:         # 入隊時需考慮隊列是否已滿
            print('The queue if full!')
            return
        self.elem[self.rear] = data         # 元素入隊
        self.rear = (self.rear + 1) % self.length       # 隊尾指針移動

??出隊

與入隊相反，出隊則需要判斷隊列是否為空。我們在前面也說到過，當(dāng)隊頭隊尾指針相同時就表示隊空。此時我們將隊頭指針向后移動一位即可。因為出隊是將隊頭元素取出，而隊頭指針始終是指向隊頭的，出隊就是要讓隊頭的后一個元素成為隊頭就行了。

    # 出隊
    def queue_out(self):
        if self.rear == self.front:     # 判斷隊列是否為空
            raise Exception('The Queue is empty!!!')
        self.front = (self.front + 1) % self.length # 出隊就是往后移動隊頭指針

??打印隊列中的元素

在打印隊列中的元素的時候，一定是m也就是隊頭指針在移動，而隊尾指針?biāo)谔幰欢ㄊ强盏?，所以?dāng)隊頭隊尾指針相同時，就表示隊列中的元素已打印完成。

    # 打印隊列中的元素
    def queue_print(self):
        m = self.front                  # 用m來代替隊頭指針移動
        n = self.rear                   # 用n來代替隊尾指針移動
        while m != n:    # 循環(huán)執(zhí)行的條件
            print(self.elem[m],end=" ") # 繼續(xù)打印隊頭元素
            m = (m + 1) % self.length  # 隊頭指針向后移動

??驗證循環(huán)隊列的操作

# 輸入數(shù)據(jù)，這里以整型數(shù)字作為例子
a = list(map(int,input('Please input a series of datas:').split(" ")))

# 實例化Queue對象，為了方便表示隊空隊滿，我們另設(shè)一個額外的空間
queue = Queue(len(a) + 1)

# 入隊
for i in range(len(a)):
    queue.queue_in(a[i])

# 打印此時隊列中的元素
queue.queue_print()
# 此時隊列的長度
print('The length of the queue is: ',queue.get_length())
# 此時隊頭隊尾指針的值
print('front: %d,rear: %d' % (queue.front,queue.rear))
# 打印此時隊尾指針指向的元素
print('The element which the rear pointer points to is:',queue.elem[queue.rear])

print('------------------------------------------------')

# 依次將隊列中的元素出隊，每出隊一個元素就打印隊列中的元素和隊頭隊尾指針的值
for i in range(queue.get_length()):
    # 出隊一個元素
    queue.queue_out()
    # 打印出隊一個元素后隊列中剩余的元素
    queue.queue_print()
    print('front: %d,rear: %d' % (queue.front,queue.rear))

print('------------------------------------------------')

# 繼續(xù)入隊，因為我們已經(jīng)設(shè)置好循環(huán)隊列的大小了，所以這里就仍然用5個元素進(jìn)行入隊
b = [6,7,8,9,10]
for i in range(len(b)):
    queue.queue_in(b[i])
    queue.queue_print()
    print('front: %d,rear: %d' % (queue.front,queue.rear))

運行結(jié)果如下：

若此時再入隊一個元素：

queue.queue_in(11)

就會看到我們手動設(shè)置的報錯提示：隊列已滿。

?? 鏈?zhǔn)疥犃?/h2>

鏈隊同鏈棧是一個道理，相當(dāng)于是將順序隊列的中的每個元素分割成一個一個的個體，再用某種方式將這些個體連接起來，而指針仍然是獨立于鏈隊之外。

??初始化

因為說到指針是獨立于鏈隊之外的，所以我們?yōu)楣?jié)點單獨設(shè)一個類。在這里我們初始化鏈隊需要將隊頭隊尾指針指向一個空節(jié)點，這個空節(jié)點并無任何用處，僅僅只是為了初始化及后續(xù)操作而已。

同樣，大家也可以考慮一個問題：可不可以直接將兩個指針置為“None”呢？（這樣設(shè)置不方便后續(xù)的入隊出隊操作）。

下面話也不多說，直接看。

# 節(jié)點
class QNode:
    def __init__(self,data):
        self.elem = data
        self.next = None
# 鏈隊
class Queue:
    def __init__(self):
        # 隊頭隊尾指針初始化指向空節(jié)點
        self.front = self.rear = QNode(None)

??入隊

入隊的操作其實很簡單，也是移動隊尾指針即可，但是不需要考慮隊列是否滿的問題，因為是隊列是通過生成節(jié)點動態(tài)增加的。

    # 入隊
    # 入隊是隊尾指針移動，隊尾指針始終指向鏈隊中的最后一個元素
    def Queue_in(self,data):
        # 生成一個新節(jié)點
        node = QNode(data)
        # 隊尾指針?biāo)诠?jié)點指向新生成的節(jié)點
        self.rear.next = node
        # 隊尾指針指向新生成的節(jié)點
        self.rear = node

??出隊

出隊操作就比較復(fù)雜。在出隊時我們還是需要判斷隊列是否為空，這里還是隊頭隊尾指針相同時就表示隊空。

同時還要考慮一個問題，當(dāng)鏈隊中剩余最后一個元素時，若要繼續(xù)出隊，按照上面隊空的概念，此時應(yīng)該是隊頭隊尾指針相同，同時指向最后一個元素，但是按照更上面的說法，隊尾指針始終指向的是鏈隊中的最后一個元素，這樣就矛盾了。

那么我們該如何去處理呢？這時只需要單獨地操作一下即可：當(dāng)要將最后一個元素出隊時，我們直接將那個節(jié)點變成空節(jié)點即可，這里又回到了鏈隊初始化的時候了。

    # 出隊
    # 出隊是隊頭指針進(jìn)行移動，隊頭指針始終指向第一個節(jié)點（空節(jié)點）
    # 隊頭指針移動到下一個節(jié)點，相對而言下一個節(jié)點也就成了“空節(jié)點”
    def Queue_out(self):
        # 判斷鏈隊是否為空，若隊頭隊尾指針相同就表示鏈隊是空的
        if self.front == self.rear:
            raise Exception('The Queue is empty!!!')
        # 若將要出隊的元素是最后一個元素，那么此時直接將隊尾指針?biāo)腹?jié)點變成空節(jié)點即可
        if self.rear.next == None:
            self.rear = QNode(None)
        # 用cur表示隊頭指針指向節(jié)點的上一個節(jié)點，后面需要將其釋放掉
        cur = self.front
        self.front = self.front.next
        # 釋放cur所占用的內(nèi)存
        del cur

??獲取鏈隊的長度

    def get_length(self):
        # 用cur來代替指針進(jìn)行遍歷，此時cur指向隊列中第一個元素（第一個元素也可以為空）
        cur = self.front.next
        # 計數(shù)器
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

??打印鏈隊中的元素

    # 打印隊列中的元素
    def Queue_print(self):
        cur = self.front.next
        while cur is not None:
            print(cur.elem,end=" ")
            cur = cur.next

??驗證鏈隊的操作

a = list(map(int,input('Please input a series of datas:').split(" ")))
print(a)
# 實例化Queue對象
queue = Queue()

# 入隊
for i in range(len(a)):
    queue.Queue_in(a[i])

# 打印此時隊列中的元素
queue.Queue_print()
print("\n")

# 依次出隊，每出隊一個元素就打印依次隊列中的元素
while queue.front.next != None:
    queue.front = queue.front.next
    queue.Queue_print()
    print('The length of the Queue is:',queue.get_length())
    print("\n")

if queue.front.next == None and queue.rear.next == None:
    print('yes')

執(zhí)行結(jié)果如下：

?? 總結(jié)

隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。有順序隊列、循環(huán)隊列、鏈隊三種形式。

順序隊列結(jié)構(gòu)簡單，但是存儲空間有限，且不利于對存儲空間的利用，入隊后出隊都需要重新移動指針。

循環(huán)隊列其實也是順序隊列，不過就是增強(qiáng)了對存儲空間的利用，入隊后出隊不用重新移動指針。

鏈?zhǔn)疥犃芯褪遣挥萌藶榉峙淇臻g，是自動增長的。讀者們可以考慮考慮循環(huán)的鏈?zhǔn)疥犃腥绾螌崿F(xiàn)？

這期博客就到這里啦～下次再見文章來源地址http://www.zghlxwxcb.cn/news/detail-735397.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之Python實現(xiàn)——隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！