隊列簡介隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。 隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素成為出隊。因為隊列只允許在一段插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO—first in first out）線性表。順序隊列建立順序隊列結構必須為其靜態分配或動態申請一片連續的存儲空間，并設置兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置每次在隊尾插入一個元素是，rear增1；每次哎隊頭刪除一個元素時，front增1。隨著插入和刪除操作的進行，隊列元素的個數不斷變化，隊列所占的存儲空間也在為隊列結構所分配的連續空間中移動。當front=rear時，隊列中沒有任何元素，稱為空隊列。當rear增加到指向分配的連續空間之外時，隊列無法再插入新元素，但這時往往還有大量可用空間未被占用，這些空間是已經出隊的隊列元素曾經占用過得存儲單元。 順序隊列中的溢出現象：“下溢”現象：當隊列為空時，做出隊運算產生的溢出現象?！跋乱纭笔钦，F象，常用作程序控制轉移的條件。“真上溢”現象：當隊列滿時，做進棧運算產生空間溢出的現象?！罢嫔弦纭笔且环N出錯狀態，應設法避免。“假上溢”現象：由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為”假上溢”現象。循環隊列在實際使用隊列時，為了使隊列空間能重復使用，往往對隊列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把隊列空間想象成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。處了一些簡單應用之外，真正實用的隊列時循環隊列。[2] 在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環隊列最多只能有MaxSize-1個隊列元素，當循環隊列中只剩下一個空存儲單元時，隊列就已經滿了。因此，隊列判空的條件時front=rear，而隊列判滿的條件時front=（rear+1）%MaxSize。隊空和隊滿的情況如圖： 這里寫圖片描述隊列的數組實現隊列可以用數組Q[1…m]來存儲，數組的上界m即是隊列所容許的最大容量。在隊列的運算中需設兩個指針：head，隊頭指針，指向實際隊頭元素；tail，隊尾指針，指向實際隊尾元素的下一個位置。一般情況下，兩個指針的初值設為0，這時隊列為空，沒有元素。數組定義Q[1…10]。Q(i) i=3,4,5,6,7,8。頭指針head=2，尾指針tail=8。隊列中擁有的元素個數為:L=tail-head?，F要讓排頭的元素出隊，則需將頭指針加1。即head=head+1這時頭指針向上移動一個位置，指向Q(3)，表示Q(3)已出隊。如果想讓一個新元素入隊，則需尾指針向上移動一個位置。即tail=tail+1這時Q(9)入隊。當隊尾已經處理在最上面時，即tail=10，如果還要執行入隊操作，則要發生”上溢”，但實際上隊列中還有三個空位置，所以這種溢出稱為”假溢出”。 克服假溢出的方法有兩種。一種是將隊列中的所有元素均向低地址區移動，顯然這種方法是很浪費時間的；另一種方法是將數組存儲區看成是一個首尾相接的環形區域。當存放到n地址后，下一個地址就”翻轉”為1。在結構上采用這種技巧來存儲的隊列稱為循環隊列。 隊列和棧一樣只允許在斷點處插入和刪除元素。 循環隊的入隊算法如下：tail=tail+1；若tail=n+1，則tail=1；若head=tail，即尾指針與頭指針重合了，表示元素已裝滿隊列，則作上溢出錯處理；否則，Q(tail)=X，結束（X為新入出元素）。隊列和棧一樣，有著非常廣泛的應用。 注意：有時候隊列中還會設置表頭結點，就是在隊頭的前面還有一個結點，這個結點的數據域為空，但是指針域指向隊頭元素。另外，上面的計算還可以利用下面給出的公式cq.rear=(cq.front+1)/max;當有表頭結點時，公式變為cq.rear=(cq.front+1)/（max+1）。