? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?數(shù)據(jù)結(jié)構(gòu) 第7講 循環(huán)隊列

過了一段時間，小張再也受不了這種"起早貪黑"的有車生活。為了解決胡同停車問題绽昏，小張跑了無數(shù)次居委會悉稠，終于將擋在胡同口的建筑清除，這樣住在胡同盡頭的小張赊抖，就可以早早回家停在家門口统倒，每天第一個開車上班去了。

現(xiàn)在胡同打通了氛雪，但仍然很窄房匆，只能通過一輛車，但是可以從一端進(jìn)报亩，另一端出浴鸿，畫圖：

小汽車是線性排列，而且只能從一端進(jìn)弦追，另一端出岳链，這就是"隊列"，隊列也是一種線性表劲件，只不過它是操作受限的線性表掸哑，只能在兩端操作，先進(jìn)先出（First In First Out零远，F(xiàn)IFO）举户。

進(jìn)的一端稱為隊尾（rear），出的一端稱為隊頭（front）遍烦。隊列可以用順序存儲俭嘁，也可以用鏈?zhǔn)酱鎯Α?/p>

1. 順序隊列

隊列的順序存儲形式，可以用一個一維數(shù)組存儲數(shù)據(jù)元素服猪，用兩個整型變量記錄隊頭和隊尾元素的下標(biāo)供填。

順序存儲方式：

順序隊列的結(jié)構(gòu)體定義：

2. 完美圖解

接下來看看順序隊列的入隊和出隊情況：

假設(shè)現(xiàn)在順序隊列Q分配了6個空間，然后進(jìn)行入隊出隊操作罢猪，過程如圖所示：

(1)開始時為空隊近她，Q.front=Q.rear，如圖所示：

(2)元素a1進(jìn)隊膳帕，放入尾指針Q.rear（整型下標(biāo)）的位置粘捎，Q.rear后移一位薇缅，如圖所示：

(3)元素a2進(jìn)隊，放入尾指針Q.rear（整型下標(biāo)）的位置攒磨，Q.rear后移一位泳桦，如圖所示：

(4)元素a3，a4娩缰，a5分別按順序進(jìn)隊灸撰，尾指針Q.rear依次后移，如圖所示：

(5)元素a1出隊拼坎，頭指針Q.front（整型下標(biāo)）后移一位浮毯，如圖所示：

(6)?元素a2出隊，頭指針Q.front（整型下標(biāo)）后移一位泰鸡，如圖所示：

(7)元素a6進(jìn)隊债蓝，放入尾指針rear（整型下標(biāo)）的位置，rear后移一位盛龄，如圖所示：

(8)?元素a7進(jìn)隊饰迹，此時尾指針Q.rear已經(jīng)超過了數(shù)組的下標(biāo)，無法再存儲進(jìn)隊讯嫂，但是我們發(fā)現(xiàn)前面明明有2個空間，卻出現(xiàn)了隊滿的情況兆沙，這種情況稱為"假溢出"欧芽。

那么如何解決該問題呢？

能否利用前面的空間繼續(xù)存儲入隊呢葛圃？

試試看…～

上面第（7）步元素a6進(jìn)隊之后千扔，尾指針Q.rear要后移一個位置，此時已經(jīng)超過了數(shù)組的下標(biāo)库正，即Q.rear+1=Maxsize（最大空間數(shù)6）曲楚，那么如果前面有空閑，Q.rear可以轉(zhuǎn)向前面0的位置褥符，如圖所示：

然后元素a7進(jìn)隊龙誊，放入尾指針Q.rear（整型下標(biāo)）的位置，Q.rear后移一位喷楣，如圖所示：

元素a8進(jìn)隊趟大，放入尾指針Q.rear（整型下標(biāo)）的位置，Q.rear后移一位铣焊，如圖所示：

這時候雖然隊列空間存滿了逊朽，但是出現(xiàn)了一個大問題，隊滿時Q.front=Q.rear曲伊，這和隊空的條件一模一樣叽讳，無法區(qū)分隊空還是隊滿，如何解決呢？有兩種辦法：一是設(shè)置一個標(biāo)志岛蚤，標(biāo)記隊空和隊滿邑狸；另一種辦法是浪費一個空間，當(dāng)尾指針Q.rear的下一個位置Q.front是時灭美，就認(rèn)為是隊滿推溃。如圖所示：

3. 循環(huán)隊列

上述到達(dá)尾部又向前存儲的隊列稱為循環(huán)隊列，為了避免"假溢出"届腐，我們通常采用循環(huán)隊列铁坎。

循環(huán)隊列無論入隊還是出隊，隊尾犁苏、隊頭加1后都要取模運算硬萍，例如入隊后隊尾后移一位：Q.rear =(Q.rear+1)%Maxsize。

為什么要%Maxsize呢围详？

主要是為了處理臨界狀態(tài)朴乖，即Q.rear向后移動一個位置Q.rear+1后，很有可能超出了數(shù)組的下標(biāo)助赞，這時它的下一個位置其實是0买羞，如果將一維數(shù)組畫成環(huán)形圖，如圖所示：

上圖中最大空間Maxsize雹食，當(dāng)Q.rear=Maxsize-1時畜普，(Q.rear+1)%Maxsize=0，而且Q.front=0群叶，正好滿足隊滿的條件：(Q.rear+1) %Maxsize= Q.front吃挑，此時為隊滿。

因此無論是front還是rear向后移動一個位置時街立，都要加1與最大空間Maxsize取模運算舶衬，處理臨界問題。

總結(jié)：

隊空：Q.front=Q.rear; // Q.rear和Q.front指向同一個位置

隊滿： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front

入隊：

Q.base[Q.rear]=x; //將元素放入Q.rear所指空間赎离，

Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位

出隊：

e= Q.base[Q.front]; //用變量記錄Q.front所指元素逛犹，

Q.front=(Q.front+1) %Maxsize // Q. front向后移一位

循環(huán)隊列中到底存了多少個元素呢？

因為隊列是循環(huán)的梁剔，所以存在兩種情況：

（1）Q.rear>= Q.front圾浅，如下圖所示：

這種情況隊列中元素個數(shù)為：Q.rear-Q.front=4-1=3。

（2）Q.rear< Q.front憾朴，如下圖所示：

此時狸捕，Q.rear=4，Q.front=Maxsize-2众雷，Q.rear-Q.front=6-Maxsize灸拍。但是我們可以看到循環(huán)隊列中的元素實際上為6個做祝，那怎么辦呢？當(dāng)兩者之差為負(fù)數(shù)時鸡岗，可以將差值+Maxsize計算元素個數(shù)混槐，即：Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6，元素個數(shù)為6轩性。

那么在計算元素個數(shù)時声登，可以分兩種情況判斷：

Q.rear>= Q.front：元素個數(shù)為Q.rear-Q.front；

Q.rear<Q.front：元素個數(shù)為Q.rear-Q.front+ Maxsize揣苏；

也可以采用取模的方法把兩種情況統(tǒng)一為一個語句：

隊列中元素個數(shù)：(Q.rear-Q.front+Maxsize)% Maxsize

當(dāng)Q.rear-Q.front為負(fù)數(shù)時悯嗓，加上Maxsize再取余正好是元素個數(shù)，如(-2+6)%6=4卸察；當(dāng)Q.rear-Q.front為正數(shù)時脯厨，加上Maxsize超過了最大空間數(shù)，取余后正好是元素個數(shù)坑质，如(3+6)%6=3合武。

4. 隊列的基本操作

隊列的基本操作包括初始化、入隊涡扼、出隊稼跳、取隊頭元素、求隊列長度吃沪。

(1)初始化

bool?InitQueue(SqQueue?&Q)//注意使用引用參數(shù)汤善，否則出了函數(shù)，其改變無效??

{??

? ? ? ? Q.base=new?int[Maxsize];//分配空間??

? ? ? ?if(!Q.base)?return?false;??

? ? ? ? Q.front=Q.rear=0;//頭指針和尾指針置為零巷波，隊列為空??

? ? ? ? ?return?true;??

}??

(2)入隊

bool?EnQueue(SqQueue?&Q,int?e)//將元素e放入Q的隊尾 ?

{ ?

? ? ? ? ?if((Q.rear+1)%Maxsize==Q.front)?//尾指針后移一位等于頭指針萎津，表明隊滿 ?

? ? ? ? ? ? ? ? ?return?false; ?

? ? ? ?Q.base?[Q.rear]=e;//新元素插入隊尾 ?

? ? ? ?Q.rear=(Q.rear+1)%Maxsize;//隊尾指針后移一位 ?

? ? ? return?true; ?

}??

(3)出隊

bool?DeQueue(SqQueue?&Q,?int?&e)?//刪除Q的隊頭元素卸伞，用e返回其值 ?

{ ?

? ? if?(Q.front==Q.rear) ?

? ? ? ? ? return?false;?//隊空 ?

? ? e=Q.base[Q.front];//保存隊頭元素 ?

? ? Q.front=(Q.front+1)%Maxsize;//隊頭指針后移一位 ?

? ?return?true; ?

}??

(4)取隊頭元素

int?GetHead(SqQueue?Q)//返回Q的隊頭元素抹镊，不修改隊頭指針 ?

{ ?

? ? ? ? ? ?if?(Q.front!=Q.rear)?//隊列非空 ?

? ? ? ? ? ? ? ? ?return?Q.base[Q.front];??

? ? ? ? ? ? return?-1; ?

}??

(5)循環(huán)隊列的長度

int?QueueLength(SqQueue?Q) ?

{ ?

? ? ? return?(Q.rear-Q.front+Maxsize)%Maxsize; ?

} ?