佇列的概念
首先我們聯想一下鏈表，在單鏈表中，我們只能對他的鏈表表尾進行插入，對鏈表的表頭進行結點的洗掉，這樣強限制性的鏈表，就是我們所說的佇列，
也就是說，佇列（queue）是限定在表的一端進行插入，表的另一端進行洗掉的資料結構，
如下圖所示，假如你去買票排隊，每一列隊伍都有一個隊尾和對頭，先來的先買票，后來的后買，買好的就從對頭出去，新來買票的就需要從隊尾繼續排隊，
通常，稱進資料的一端為 隊尾，出資料的一端為 隊頭，資料元素進佇列的程序稱為 入隊，出佇列的程序稱為 出隊，
ID：技術讓夢想更偉大
作者:李肖遙
我們可以總結如下：
佇列是一個線性的資料結構，并且這個資料結構只允許在一端進行插入，另一端進行洗掉，禁止直接訪問除這兩端以外的一切資料，且佇列是一個先進先出的資料結構，
如上圖，佇列就像一個兩端相通的水管，只允許一端插入，另一端取出，取出的球就不在水管里面了，而先放入管中的球就會先從管中拿出，
佇列存盤結構的實作有以下兩種方式：
（1）順序佇列：在順序表的基礎上實作的佇列結構
（2）鏈佇列：在鏈表的基礎上實作的佇列結構
兩者的區別僅是順序表和鏈表的區別，即在實際的物理空間中，資料集中存盤的佇列是順序佇列，分散存盤的佇列是鏈佇列，
佇列的結點設計與初始化
佇列只有鏈式的設計方法，其本身分為多種佇列，如順序佇列和回圈佇列，還有衍生的優先佇列等等，我們以順序佇列的設計為例，
首先是佇列的結點設計，我們可以設計出兩個結構體，一個結構體Node表示結點，其中包含有一個data域和next指標，如圖所示：
其中data表示資料，其可以是簡單的型別，也可以是復雜的結構體，
next指標表示，下一個的指標，其指向下一個結點，通過next指標將各個結點鏈接，
然后我們再添加一個結構體，其包括了兩個分別永遠指向佇列的隊尾和隊頭的指標，看到這里是不是覺得和堆疊很像？
我們主要的操作只對這兩個指標進行操作，如圖所示：
其結構體設計的代碼可以表示為：
對于初始化需要初始化兩個型別，一個是初始化結點，一個是初始化佇列，
我們看到代碼中的描述，初始化佇列有些不同，當初始化佇列的時候，需要將頭尾兩個結點指向的內容統統置為空，表示是一個空佇列，兩個創建的函式代碼可以表示為：
判斷佇列是否為空
這是一個既簡單也很要緊的操作，判斷佇列是否為空直接就是判斷佇列頭指標是否是空值即可，判斷佇列是否為空是比較常用的操作，切勿忘記，
其代碼可以表示為：
或者直接利用回傳值進行更簡單的判斷也可以，代碼如下：
入隊操作
入隊操作變化如下圖:
進行入隊（push）操作的時候，同樣的，我們首先需要特判佇列是否為空，如果佇列為空的話，需要將頭指標和尾指標一同指向第一個結點，代碼如下
如圖所示：
當如果佇列不為空的時候，這時我們只需要將尾結點向后移動，通過不斷移動next指標指向新的結點構成佇列即可，如圖所示：
其代碼可以表示為：
出隊操作
出隊操作變化如下圖:
出隊（pop）操作，是指在佇列不為空的情況下進行的一個判斷，當然我們在此也一定要進行佇列判空的操作，你懂的，
如圖，如果佇列只有一個元素了，也就是說頭尾指標均指向了同一個結點，那么我們直接將頭尾兩指標制空NULL，并釋放這一個結點即可，如下圖所示：
當佇列含有以上個元素時，我們需要將佇列的頭指標指向頭指標當前指向的下一個元素，并釋放掉當前元素即可，如下圖所示
其代碼可以表示為：
列印佇列元素（遍歷）
列印佇列的全部元素可以幫助我們除錯，看到佇列中具體的資料，在佇列不為空的情況下，通過結點的next指向依次遍歷并輸出元素既可，
其代碼可以表示為
遍歷操作還有很多別的表示方法，比如說進行計算佇列中含有多少元素，代碼如下：
順序佇列的假溢位
什么是假溢位？我們可能會有疑問，溢位還有假的！
這里我們也需要考慮到順序佇列有什么缺點，對于順序佇列而言，其存在已經足夠解決大多時候的設計問題了，但是其依舊存在一些缺陷和不足，
從上面的決議中我們看到，入隊和出隊操作均是直接在其后面進行結點的鏈接和洗掉，這種操作會造成其使用空間不斷向出隊的那一邊偏移，產生假溢位，
我們來打打一個比方，先看看下面的圖：
示例順序佇列
上圖所示，有一個順序佇列，這個佇列的大小為5，其已經包含了四個元素data1,data2,data3,data4，
接著，我們對這個佇列進行出隊操作，出隊2個元素，佇列就變成了這個樣子，如下圖所示：
從圖上看到似乎沒有什么問題，但是當我們接著再進行入隊操作，比如我們入隊2個元素，分別是data5和data6，
此時我們已經發現問題了，尾指標移動到我們可以進行佇列操作的范圍之外去了，有沒有發現？
這種現象我們稱呼作為佇列用的存盤區還沒有滿，但佇列卻發生了溢位，我們把這種現象稱為假溢位，如下圖所示：
出隊產生假溢位
那么我們有什么辦法解決這個問題呢？這就要涉及到回圈佇列的性質了！
回圈佇列的概念
可能這個時候會產生一個疑問，我們學習的佇列不是使用鏈表實作的動態佇列么？
沒有空間的時候會開辟空間，這難道還會產生假溢位么？
的確，當進行動態創建佇列的時候，也只不過是向后繼續不斷的申請記憶體空間；
即使前面出隊操作釋放掉了前面的空間，但是指標依舊會向后進行移動，直到達到系統預留給程式的記憶體上界被強行終止；
這對于極為頻繁的佇列操作和程式而言是致命的，這時候，就需要對我們的佇列進行優化，使用更為優秀的結構——回圈佇列，
回圈佇列就是將佇列存盤空間的最后一個位置轉而繞到第一個位置，形成邏輯上的環狀空間，以此來供佇列回圈使用，如下圖，
回圈佇列就是給定我們佇列的大小范圍，在原有佇列的基礎上，只要佇列的后方滿了，就從這個佇列的前面開始進行插入，以達到重復利用空間的效果；
由于回圈佇列的設計思維更像一個環，因此常使用一個環圖來表示，但我們需要注意，實際上回圈佇列不是一個真正的環，它依舊是單線性的，
回圈佇列的結構設計
由于回圈對列給定了資料范圍的大小，所以不需要使用鏈式的動態創建方法了，
因為如果使用鏈式存盤，會無法確定何時再回到隊頭進行插入操作，所以我們采用模擬的方法，如圖所示：
其中，data表示一個資料域，int為型別，其可以修改為任意自定義的型別，比如說簡單的char,float型別等等，也可以是復雜的結構體型別，
（1）maxsize表示回圈佇列的最大容納量，其表示佇列的全部可操作空間，
（2）rear代表尾指標，入隊時移動，
（3）front代表頭指標，出隊時移動，
其代碼可以表示為：
回圈佇列的初始化
回圈佇列的初始化核心就在于申請空間，并且將front指標和rear指標內容賦值為0，即指向第0個元素即可，這里要注意第 0個元素內容為空，如下圖所示：
其代碼可以表示為：
入隊操作
入隊操作同順序佇列的方法，直接將rear向后移動即可，
但是要注意判斷，如果rear達到了佇列的空間上線，將要從頭繼續開始移動，
這里推薦使用余數法，即無論如何求余都是在這片空間內進行操作，防止一次錯誤執行就直接整體崩潰，而且也相對而言更為簡潔，不推薦使用if陳述句，這樣顯得比較累贅，
入隊操作
注意進行加一移動位置操作的時候，不能直接q->rear++這樣的操作，這樣計算機判斷優先級會產生讓自己意想不到的后果，
此外這里還需要進行一次是否佇列已滿的判斷，當我們rear指標的下一個位置就是front的位置的時候，即改回圈佇列已滿，
如圖：
出隊操作
如果順序佇列的出隊操作，直接將front進行后移一位即可，
這里上面很多地方都提過了，有一個需要留意的地方，即佇列是否為空，當佇列為空的時候是無法進行出隊操作的，
其代碼可以表示為：
遍歷操作
遍歷操作需要借助一個臨時變數儲存位置front的位置資訊，利用i逐步向后移動，直到i到達了rear的位置即可宣告遍歷的結束，
關于佇列的總結
請牢記這句話：佇列是一個先進先出的資料結構，
今天佇列基礎就講到這里，下一期，我們再見！
另外如果你想更好的提升你的編程能力，好好學習C/C++編程知識的話！那么你很幸運~
C語言C++編程學習交流圈子，QQ群757874045【點擊進入】微信公眾號：C語言編程學習基地
分享（原始碼、專案實戰視頻、專案筆記，基礎入門教程）
歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！
編程學習書籍
編程學習視頻
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/108194.html
標籤：其他
上一篇：Python爬蟲的常見依賴庫大全