【算法與數據結構 06】先進先出的隊列 —— 順序隊列 || 循環隊列 || 鏈式隊列 大盤點

寫在前面：大家好！我是【AI 菌】，一枚愛彈吉他的程序員。我熱愛AI、熱愛分享、熱愛開源！ 這博客是我對學習的一點總結與思考。如果您也對 深度學習、機器視覺、算法、C++、Python 感興趣，可以關注我的動態，我們一起學習，一起進步~

我的博客地址為：【AI 菌】的博客

上一篇：【算法與數據結構 05】“霸道“ 的棧——先進后出

在上一篇中，我們學習了后進先出的數據結構——棧，與之對應的是一種先進先出的數據結構——隊列。今天，我們就一起來學習隊列，掌握順序隊列、循環隊列和鏈式隊列中數據的基本操作。

文章目錄

1. 什么是隊列

2. 順序隊列中的數據操作

（1）增操作

（2）刪操作

（3）越界問題

3. 循環隊列的數據操作

4. 鏈式隊列的數據操作

（1）增操作

（2）刪操作

（3）查操作

1. 什么是隊列

簡單來說，隊列就是一個FIFO（先進先出）的系統。元素只能從隊尾插入，且最先插入的元素最先被刪除。

就如同在食堂排隊就餐，先進入隊伍的人先取到餐，且從隊首離開，即先進先出；而所有人只能從隊尾加入隊列，從隊首離開，即元素只能從隊尾插入，隊首刪除。

相信說到這里，大家對隊列已經有了一個基本的了解！那么，下面我們更深一步挖掘~

從本質上來說，隊列也是一種特殊的線性表，與線性表的不同之處體現在對數據的增刪操作上。

隊列的特點是先進先出：

先進，表示隊列的數據新增操作只能在末端進行，不允許在隊列的中間某個結點后新增數據;

先出，隊列的數據刪除操作只能在始端進行，不允許在隊列的中間某個結點后刪除數據。

也就是說，隊列的增和刪的操作只能分別在這個隊列的隊尾和隊頭進行。

除此之外，與線性表、棧一樣，隊列也存在這兩種存儲方式，即順序隊列和鏈式隊列：

順序隊列，依賴數組來實現，其中的數據在內存中也是順序存儲。

鏈式隊列，則依賴鏈表來實現，其中的數據依賴每個結點的指針互聯，在內存中并不是順序存儲。鏈式隊列，實際上就是只能尾進頭出的線性表的單鏈表。

對單鏈表、鏈式結構還不了解的同學，墻裂建議先看看這篇文章：【算法與數據結構 04】多圖講解——線性表、順序表、鏈表

在學習隊列的增刪查操作之前，我們需要簡單了解一下隊列中指針與節點的關系，下面以鏈式隊列為例：

如下圖所示，一般情況，我們將隊頭指針front指向鏈式隊列的頭結點，隊尾指針rear指向終端結點。

當隊列為空時，front 和 rear 必須都指向頭結點，如下圖所示：

實際上，不管是哪種實現方式，一個隊列都依賴隊頭（front）和隊尾（rear）兩個指針進行唯一確定。

理解了這個之后，我們正式進入：隊列對于數據的增刪查處理！

2. 順序隊列中的數據操作

隊列從隊頭（front）刪除元素，從隊尾（rear）插入元素

。前面已經談到過鏈式列表；那么，對于一個順序隊列的數組來說，也會設置一個 front 指針來指向隊頭，并設置另一個 rear 指針指向隊尾。當我們不斷進行插入刪除操作時，頭尾兩個指針都會不斷向后移動。

（1）增操作

下面以順序鏈表為例，為了實現一個有 k 個元素的順序存儲的隊列，我們需要建立一個長度比 k 大的數組，以便把所有的隊列元素存儲在數組中。

隊列新增數據的操作，就是利用 rear 指針在隊尾新增一個數據元素

。過程如下圖所示：

因為這個過程不會影響其他數據，所以時間復雜度為 O(1)。

（2）刪操作

隊列刪除數據的操作與棧不同。隊列元素出口在隊列頭部，即下標為 0 的位置。當利用 front 指針刪除一個數據時，隊列中剩余的元素都需要向前移動一個位置，以保證隊列頭部下標為 0 的位置不為空，過程如下圖所示：

因為剩余的元素都需要向前移動一個位置，此時時間復雜度就變成 O(n) 。

我們看到，front 指針刪除數據的操作引發了時間復雜度過高的問題，那么我們該如何解決呢？

（3）越界問題

我們可以通過移動指針的方式來刪除數據，這樣就不需要移動剩余的數據了。但是，這樣的操作，也可能會產生數組越界的問題。接下來，我們來詳細討論一下。

首先，我們來看一個例子：利用順序隊列，持續新增數據和刪除數據

1）初始時，定義了長度為 5 的數組，front 指針和 rear 指針相等，且都指向下標為 0 的位置，隊列為空隊列。

2）當 A、B、C、D 四條數據加入隊列后，front 依然指向下標為 0 的位置，而 rear 則指向下標為 4 的位置。過程如下圖所示：

3）當 A 出隊列時，front 指針指向下標為 1 的位置，rear 保持不變。其后 E 加入隊列，front 保持不變，rear 則移動到了數組以外，如下圖所示：

假設這個列隊的總個數不超過 5 個，但是目前繼續接著入隊，因為數組末尾元素已經被占用，再向后加，就會產生我們前面提到的數組越界問題。而實際上，我們列隊的下標 0 的地方還是空閑的，這就產生了一種 “假溢出” 的現象。

這種問題在采用順序存儲的隊列時，是一定要小心注意的。兩個簡單粗暴的解決方法就是：

不惜消耗 O(n) 的時間復雜度去移動數據；

或者開辟足夠大的內存空間確保數組不會越界。

3. 循環隊列的數據操作

顯然，上面的兩個方法都不太友好。其實，數組越界問題可以通過隊列的一個特殊變種來解決，叫作循環隊列。

循環隊列進行新增數據元素操作時，首先判斷隊列是否為滿。如果不滿，則可以將新元素賦值給隊尾，然后讓 rear 指針向后移動一個位置。如果已經排到隊列最后的位置，則 rear指針重新指向頭部。

循環隊列進行刪除操作時，首先判斷隊列是否為空，然后將隊頭元素賦值給返回值，front 指針向后移一個位置。如果已經排到隊列最后的位置，就把 front 指針重新指向到頭部。這個過程就好像鐘表的指針轉到了表盤的尾部 12 點的位置后，又重新回到了表盤頭部 1 點鐘的位置。這樣就能在不開辟大量存儲空間的前提下，不采用 O(n) 的操作，也能通過移動數據來完成頻繁的新增和刪除數據。

好啦，我們繼續回到前面提到的例子中。對于一般的隊列，末尾元素已經被占用，再向后加，就會產生我們前面提到的越界問題。

當我們使用循環隊列時，rear 指針就可以重新指向下標為 0 的位置，如下圖所示：

如果這時再新增了 F 進入隊列，就可以放入在下標為 0 的位置，rear 指針指向下標為 1 的位置。這時的 rear 和 front 指針就會重合，指向下標為 1 的位置，如下圖所示：

此時，又會產生新的問題，即當隊列為空時，有 front 指針和 rear 指針相等。而現在的隊列是滿的，同樣有 front 指針和 rear 指針相等。那么怎樣判斷隊列到底是空還是滿呢？常用的方法是，設置一個標志變量 flag 來區別隊列是空還是滿。

4. 鏈式隊列的數據操作

我們再看一下鏈式隊列的數據操作。鏈式隊列就是一個單鏈表，同時增加了 front 指針和 rear 指針。鏈式隊列和單鏈表一樣，通常會增加一個頭結點，并讓 front 指針指向頭結點。頭結點不存儲數據，只是用來輔助標識。

（1）增操作

鏈式隊列進行新增數據操作時，比如要新增數據X，要將擁有數值 X 的新結點 s 賦值給原隊尾結點的后繼，即 rear.next。然后把當前的 s 設置為隊尾結點，指針 rear 指向 s。如下圖所示：

（2）刪操作

當鏈式隊列進行刪除數據操作時，實際刪除的是頭結點的后繼結點。這是因為頭結點僅僅用來標識隊列，并不存儲數據。因此，出隊列的操作，就需要找到頭結點的后繼，這就是要刪除的結點。接著，讓頭結點指向要刪除結點的后繼。過程如下圖所示：

需要注意的是：如果這個鏈表除去頭結點外只剩一個元素，那么刪除僅剩的一個元素后，rear 指針就變成野指針了。這時候，需要讓 rear 指針指向頭結點。也許你前面會對頭結點存在的意義產生懷疑，似乎沒有它也不影響增刪的操作。那么為何隊列還特被強調要有頭結點呢？

這主要是為了防止刪除最后一個有效數據結點后， front 指針和 rear 指針變成野指針，導致隊列沒有意義了。有了頭結點后，哪怕隊列為空，頭結點依然存在，能讓 front 指針和 rear 指針依然有意義。

（3）查操作

對于隊列的查找操作，不管是順序還是鏈式，隊列都沒有額外的改變。跟線性表一樣，它也需要遍歷整個隊列來完成基于某些條件的數值查找。因此時間復雜度也是 O(n)。

相關文章推薦

【C++養成計劃】隊列 —— 快速上手STL queue類（Day13）

【算法與數據結構 04】多圖講解——線性表、順序表、鏈表

【算法與數據結構 05】“霸道“ 的棧——先進后出

AI 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。