隊列是一種什麼資料結構

佇列是一種線性資料結構。佇列只允許在表的前端進行刪除操作，而在表的後端進行插入操作，和堆疊一樣，佇列是一種操作受限的線性表；其進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

本文操作環境：windows10系統、thinkpad t480電腦。

佇列是一種線性資料結構。

佇列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

佇列的資料元素又稱為佇列元素。在佇列中插入一個佇列元素稱為入隊，從佇列中刪除一個佇列元素稱為出隊。因為佇列只允許在一端插入，在另一端刪除，所以只有最早進入佇列的元素才能先從佇列中刪除，故佇列又稱為先進先出（FIFO—first in first out）線性表。 

順序佇列

建立順序佇列結構必須為其靜態分配或動態申請一片連續的儲存空間，並設定兩個指標來管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置，如圖所示

每次在隊尾插入一個元素是，rear增1；每次在隊頭刪除一個元素時，front增1。隨著插入和刪除操作的進行，佇列元素的數量不斷變化，佇列所佔的儲存空間也在為佇列結構所指派的連續空間中移動。當front=rear時，隊列中沒有任何元素，稱為空隊列。當rear增加到指向分配的連續空間之外時，佇列無法再插入新元素，但這時往往還有大量可用空間未被佔用，這些空間是已經出隊的隊列元素曾經佔用過得儲存單元。

順序佇列中的溢出現象：

（1） "下溢"現象：當佇列為空時，做出隊運算產生的溢位現象。 「下溢」是正常現象，常用作程序控制轉移的條件。

（2）"真上溢"現象：當佇列滿時，做進棧運算產生空間溢位的現象。 「真上溢」是一種出錯狀態，應設法避免。

（3）"假上溢"現象：由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當佇列中實際的元素個數遠小於向量空間的規模時，也可能由於尾指標已超越向量空間的上界而不能做入隊操作。此現象稱為"假上溢"現象。

循環佇列

在實際使用佇列時，為了使佇列空間能重複使用，往往會對佇列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取餘運算rear%MaxSize和front%MaxSize來實現。這其實是把佇列空間想像成一個環形空間，環形空間中的儲存單元循環使用，用這種方法管理的佇列也稱為循環佇列。除了一些簡單應用之外，真正實用的隊列是循環隊列。 

在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全佔滿時，也有front=rear。為了區別這兩種情況，規定循環佇列最多只能有MaxSize-1個佇列元素，當循環佇列只剩下一個空儲存單元時，佇列就已經滿了。因此，隊列判空的條件時front=rear，而隊列判滿的條件時front=（rear 1）%MaxSize。隊空與隊滿的情況如圖：

推薦：《程式設計影片》

以上是隊列是一種什麼資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！