循環(huán)隊(duì)列隊(duì)空與隊(duì)滿兩個(gè)狀態(tài)的判斷算法分析

張春玲

摘 要 入隊(duì)和出隊(duì)是循環(huán)隊(duì)列的兩個(gè)主要操作，在入隊(duì)出隊(duì)操作時(shí)如何判斷隊(duì)空和隊(duì)滿是一項(xiàng)非常重要的工作，文章介紹了五種判斷隊(duì)空和隊(duì)滿的算法過程，從而保證入隊(duì)出隊(duì)操作的正確進(jìn)行。

關(guān)鍵詞 循環(huán)隊(duì)列；隊(duì)空隊(duì)滿；入隊(duì)出隊(duì)

中圖分類號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2014）08-0067-01

線性表是數(shù)據(jù)結(jié)構(gòu)中比較重要的一種邏輯結(jié)構(gòu)，插入刪除操作是線性表的基本操作，當(dāng)進(jìn)行這些操作時(shí)，不僅需要考慮插入、刪除的位置是否合法性，仍然需要考慮‘滿與‘空這兩種狀態(tài)，但是，由于棧和隊(duì)列都是受限制的線性表，它們已經(jīng)規(guī)定了進(jìn)行插入、刪除的位置，所以插入、刪除時(shí)不需要再考慮位置的合法性，只需要考慮‘滿與‘空。

1 隊(duì)列與棧的區(qū)別

數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列是只允許在一端進(jìn)行刪除（隊(duì)頭）另一端進(jìn)行插入（隊(duì)尾）的線性表；棧是只允許在一端進(jìn)行插入刪除（棧頂）的線性表。由于兩者都是線性表，則遵循線性表的存儲(chǔ)結(jié)構(gòu)表示—順序存儲(chǔ)以及鏈?zhǔn)酱鎯?chǔ)，這里主要討論靜態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)。如下：

#define MAXSIZE 100 //初始分配空間

typedef struct {

Elemtype data[MAXSIZE]；//一維數(shù)組

int Top； //棧頂指針，一直指向棧頂元素，初始值為-1

}sqStack；

typedef struct {

Elemtype data[MAXSIZE]；//一維數(shù)組

int front； //隊(duì)頭指針指向隊(duì)頭元素，初始值為0

int rear； //隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置，初始值為0

}sqQueue；

2 順序隊(duì)列與棧判斷滿和空的不同

線性表順序存儲(chǔ)的靜態(tài)分配特點(diǎn)是初始化時(shí)一次性分配好所需內(nèi)存空間（MAXSIZE），因此在插入刪除時(shí)需要判斷‘空和‘滿兩個(gè)狀態(tài)。由于棧的所有操作只在棧頂進(jìn)行，所以只通過棧頂值Top就可以反映出當(dāng)前存儲(chǔ)空間使用的情況，當(dāng)Top==-1時(shí)棧空，Top==MAXSIZE-1時(shí)棧滿。

順序隊(duì)列的操作分別在隊(duì)頭隊(duì)尾兩端進(jìn)行，在出隊(duì)入隊(duì)時(shí)，對(duì)頭front和隊(duì)尾rear值都是只增加（向MAXSIZE靠近）而不減小，如果僅通過rear==MAXSIZE來判斷順序隊(duì)列是否滿，此時(shí)可能存在rear已經(jīng)指向MAXSIZE同時(shí)front>0（因?yàn)槌鲫?duì)使front值增加）而不能做入隊(duì)操作的情況，導(dǎo)致元素出隊(duì)后的空閑存儲(chǔ)空間永遠(yuǎn)無法重新利用，盡管這時(shí)循環(huán)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)的小于最大存儲(chǔ)空間MAXSIZE，這就造成了順序隊(duì)列中的“假上溢”現(xiàn)象。以上進(jìn)一步看出棧與順序隊(duì)列在進(jìn)行插入刪除時(shí)空與滿的判斷條件不一樣。

順序隊(duì)列的“假上溢”現(xiàn)象：

為克服“假上溢”現(xiàn)象，可以將順序隊(duì)列想象為一個(gè)首尾相接的環(huán)狀空間，稱為循環(huán)隊(duì)列。在循環(huán)隊(duì)列中出隊(duì)入隊(duì)時(shí)，頭尾指針仍要向前移動(dòng)進(jìn)行加1操作，當(dāng)頭尾指針指向上界MAXSIZE時(shí)，頭尾指針加1操作的結(jié)果重新指向下界0（加1后對(duì)MAXSIZE做MOD取余數(shù)運(yùn)算）。循環(huán)隊(duì)列是解決了“假上溢”現(xiàn)象，但對(duì)循環(huán)隊(duì)列進(jìn)行插入刪除時(shí)如何判斷隊(duì)空與隊(duì)滿？

3 循環(huán)隊(duì)列隊(duì)空與隊(duì)滿的判斷

循環(huán)隊(duì)列入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故存在隊(duì)空和隊(duì)滿時(shí)都有front==rear的情況，因此無法通過front==rear來判斷隊(duì)空還是隊(duì)滿，下面就給出五種算法來解決循環(huán)隊(duì)列空和滿的問題。

算法一、增加兩個(gè)全局變量A，B，分別表示所有元素入隊(duì)的次數(shù)A和元素出隊(duì)的次數(shù)B。

初始化A=0，B=0；

出隊(duì)時(shí)，當(dāng)front==rear&&A==B（即入隊(duì)元素次數(shù)等于出隊(duì)元素次數(shù)）時(shí)隊(duì)空，不能出隊(duì)，然后B++；

入隊(duì)時(shí)，當(dāng)front==rear&&（A-B==MAXSIZE）（表示入隊(duì)元素?cái)?shù)多于出隊(duì)元素?cái)?shù)，但兩者差必須為MAXSIZE）時(shí)隊(duì)滿，不能入隊(duì)，然后A++。

算法二、增加一個(gè)計(jì)數(shù)變量Count，表示隊(duì)列中實(shí)際存在的數(shù)據(jù)元素的個(gè)數(shù)。

初始化Count=0；

出隊(duì)時(shí)，當(dāng)Count==0隊(duì)空，不能出隊(duì)，然后Count--；

入隊(duì)時(shí)，當(dāng)Count==MAXSIZE隊(duì)滿，不能入隊(duì)，然后Count++。

算法三、增加一個(gè)布爾變量Tag來區(qū)分。

初始化 Tag=0，并且入隊(duì)成功時(shí)置Tag=1、出隊(duì)成功時(shí)置Tag=0；

出隊(duì)是隊(duì)頭在追趕隊(duì)尾，如果追上了，即rear==front&&tag==0表示隊(duì)空，不能出隊(duì)，然后重新置Tag=0；

入隊(duì)是隊(duì)尾追趕隊(duì)頭（沿著空位置向隊(duì)頭方向移動(dòng)），如果追上了，即rear==front&&tag==1時(shí)表示隊(duì)滿，不能入隊(duì)，然后重新置Tag=1。

算法四、約定犧牲存儲(chǔ)空間中的一個(gè)存儲(chǔ)單元來區(qū)分。（教材中大多采用這種算法）。

出隊(duì)時(shí)，當(dāng)rear==front隊(duì)空，不能出隊(duì)；

入隊(duì)時(shí)，當(dāng)（rear+1）%MAXSIZE==front隊(duì)滿，不能入隊(duì)。

算法五、將靜態(tài)分配的循環(huán)隊(duì)列改為動(dòng)態(tài)分配的循環(huán)隊(duì)列。

以上可見，循環(huán)隊(duì)列不能使用動(dòng)態(tài)分配的一維數(shù)組實(shí)現(xiàn)，但是循環(huán)隊(duì)列也是順序隊(duì)列，遵循順序存儲(chǔ)結(jié)構(gòu)的分配方式，即可以靜態(tài)分配存儲(chǔ)空間，也可以根據(jù)隊(duì)列的長度動(dòng)態(tài)分配存儲(chǔ)空間。如下：順序隊(duì)列在動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：

#define QUESIZE 100 //初始分配量

#define QUEUEINCREMENT 10 //動(dòng)態(tài)分配增量

typedef struct{

ElemType *elem； //動(dòng)態(tài)分配存儲(chǔ)空間基址

int front；

int rear；

int quesize； //當(dāng)前分配的存儲(chǔ)容量（以sizeof（ElemType）為單位）

}sqQueue；

入隊(duì)時(shí)（rear+1）%quesize==front判斷是否隊(duì)滿，滿則動(dòng)態(tài)再分配QUEUEINCREMENT的空間，重新構(gòu)成新的循環(huán)隊(duì)列，新隊(duì)列頭尾指針要分不同情況來修改。因?yàn)樵?duì)列隊(duì)滿時(shí)，頭尾指針有不同的分布情況，所以先分析出不同分布后再分別根據(jù)新增加空間來修改頭尾指針。

出隊(duì)時(shí)rear==front隊(duì)空，不能出隊(duì)；

4 總結(jié)

基于以上五種算法循環(huán)隊(duì)列在實(shí)現(xiàn)入隊(duì)出隊(duì)操作時(shí)就比較容易了，不過一定要注意算法實(shí)現(xiàn)順序，入隊(duì)時(shí)先判斷是不是隊(duì)滿，出隊(duì)時(shí)先判斷是不是隊(duì)空，然后再進(jìn)行相應(yīng)的入隊(duì)出隊(duì)操作。

參考文獻(xiàn)

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2013.

[2]顧奇峰，動(dòng)態(tài)增長型循環(huán)隊(duì)列的實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2007（23）：262-264.

[3]高永平，循環(huán)隊(duì)列入隊(duì)算法的研究[J].計(jì)算機(jī)與現(xiàn)代化，2005（4）：9-13.endprint