資料結構系列：佇列？迴圈佇列？優先佇列？這三貨有啥不一樣的

rear是什麼意思

上文

資料結構系列：棧？佇列？這倆貨應該這麼理解和掌握

我們分享了棧和佇列最最基礎的特點和應用，本篇將拓展一下關於普通佇列結構的不同變體，如何實現（基於python），以及相關的應用。始終記住：

資料結構只是一種抽象的概念，是具有某種特點的資料集合，並不是指某一個單獨的資料型別

。

01

普通佇列

普通佇列的特點就是“FIFO”，上文我們已經分享了基於python的內建列表結構實現一個簡單的佇列結構，所以這裡我們將會分享基於連結串列結構的實現

普通佇列已經能實現大部分的功能了，但是不夠用。

舉個例子來說，醫院看病排號，正常來講，就先掛號的先看病，這是沒有毛病的，但是突然間來了個需要急救的，你還能讓他掛個號，再等著排到號看病嗎？肯定他是要先被救治的，畢竟在生死之間，時間就是生命！

所以這時候普通的佇列就不夠用了，需要給佇列搞點變體，比如說在

正常佇列特點(FIFO)上增加優先順序的特點，可以讓具有優先順序較高的資料體插隊到隊首

，所以優先佇列就誕生了。

02

優先佇列

概念理解

優先佇列和普通佇列結構一樣，資料從邏輯隊尾進入佇列，資料從邏輯隊首移除。不同的是，

從隊首移除資料總會移除優先順序最高的資料，而從隊尾加入資料，也是根據某種順序新增到佇列中

原理

優先佇列的資料結構是

基於完全二叉樹(有關樹的結構，後面的文章會寫)的特點：從任一葉子節點開始到根節點的一條路徑是有序列表，

如果是最大堆，則由葉子結點到根節點的路徑上的所有節點資料呈現從小到大的變化，而最小堆則剛好相反。完全二叉堆（樹）又是二叉樹型別中的一種，所以要理解原理，需要理解樹結構相關的知識

上面所說的樹結構為

二叉堆

（不論是最小堆還是最大堆結構），一般都會提供如下幾個介面，用來構建優先佇列，二叉堆的資料插入，二叉堆的資料刪除，二叉堆的根節點元素的值，以及將雜亂的序列（列表等資料結構）轉化為堆結構。

優先佇列也是透過二叉堆內部的這幾個介面達成目的

實現(基於python內建庫heapq)

heapq本就是一個二差堆的結構，優先佇列一般都是基於二差堆實現。

原則上講，一般佇列都是基於陣列實現，因為簡單，且介面效能更好，但是有一個問題：因為順序儲存（底層為陣列）的結構特點，資料只能在隊首位置出隊，那麼出隊操作需要先將刪除的資料從陣列中刪除，然後將剩下的所有元素前移一位，故而

時間複雜度為O(n)，消耗了比較大的效能，

所以就將佇列做了一次變體，稱之為

迴圈佇列

03

迴圈佇列

概念

迴圈佇列是

頭尾相連的順序儲存結構，

迴圈佇列是佇列的一種實現方式，並不是一種全新的資料結構

為什麼要創造迴圈佇列

為了降低時間複雜度，

將入隊和出隊的操作都可以透過索引以常數時間定位，然後進行入隊或出隊的操作，而陣列的特性決定了這兩個操作的時間複雜度都是O（1）

實現迴圈佇列的整體思路

維護兩個指標（最開始都指向下標為0的位置），分別代表著隊首位置以及隊尾的下一個元素位置，入隊，則移動隊尾指標，隊首指標不動；出隊，則移動隊首指標，隊尾指標不動

迴圈佇列特點及實現的詳細思路(感覺解釋異常清晰了)

迴圈佇列的出隊，入隊操作的時間複雜度都是O(1)

這裡約定，

指向隊首的指標變數命名為front,指向隊尾的下一個元素位置的變數指標命名為rear

front和rear理解為佇列的索引，空佇列（最開始的時候）,此時front=rear=0

；由於front 和rear會隨著出隊、入隊的操作執行索引+1的操作，這裡假設不出隊，一直入隊，直到隊滿的時候，此時rear已經超過了佇列的最大索引值，那麼假設rear可以從隊首索引重新開始計算，那麼此時rear指向隊首位置，那麼此時front=rear，那麼就造成一種尷尬的局面，隊空，隊滿都是一個判斷條件（front=rear），

為了對這種情況的處理，提出了新的解決方案：將佇列長度增加一，佔據一個記憶體單元，但是不儲存資料

，只是為了透過這個方法判斷佇列為滿還是空的情況

舉例來說

：比如說佇列長度為5，開始front=0，rear=0，那麼新增5個數據入隊，此時rear=5， 但是此時滿佇列的索引最大才能是4，所以假設rear可以從尾部移動到隊首，那麼此時rear指向0，那麼front=rear=0，此時佇列為滿。但同時思考一下前面說到的，隊為空也是front=rear=0，所以透過front=rear的條件無法分清楚目前是滿佇列還是空佇列，由此提出了以下新的解決方案：

將佇列長度增加一，佔據一個記憶體單元，但是不儲存資料

**

新定義的判斷隊滿的計算方法就是 ，如果 (rear + 1) % queue_max_size == front,此時隊滿

舉例來說：假設佇列最大長度為5，比如入隊4個數據，那麼此時佇列就是滿佇列，rear=4（意思是指向索引位置為4的記憶體空間，也就是佇列的最後一個不儲存資料的空間位置），此時（4 + 1） % 5 = 0 =front，就可以說是隊滿（增加的一個額外空間用來判斷隊滿的條件）

透過增加一個額外空間的方式判斷隊滿的情況，對於當前佇列的長度有兩種情況

Rear > front： current_queue_size = rear - front

Rear > front： current_queue_size = rear + max_queue_size - front

由於rear可能大於front，也可能小於front，以下為兩種情況分析

綜上所述：current_queue_size = （rear - front + max_queue_size）% max_queue_size

實現程式碼

好好的看下我上面的詳細思路，其實程式碼也比較好理解，本篇<完>。

我是一名奮戰在程式設計界的pythoner，工作中既要和資料打交道，也要和erp系統，web網站保持友好的溝通……時不時的會分享一些提高效率的程式設計小技巧，在實際應用中遇到的問題以及解決方案，或者原始碼的閱讀等等，歡迎大家一起來討論！如果覺得寫得還不錯，歡迎關注點贊，謝謝