張春玲

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

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

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

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

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

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

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

typedef struct {

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

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

}sqStack；

typedef struct {

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

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

int rear； //隊尾指針指向隊尾元素的下一個位置，初始值為0

}sqQueue；

2 順序隊列與棧判斷滿和空的不同

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

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

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

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

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

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

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

初始化A=0，B=0；

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

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

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

初始化Count=0；

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

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

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

初始化 Tag=0，并且入隊成功時置Tag=1、出隊成功時置Tag=0；

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

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

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

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

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

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

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

#define QUESIZE 100 //初始分配量

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

typedef struct{

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

int front；

int rear；

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

}sqQueue；

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

出隊時rear==front隊空，不能出隊；

4 總結(jié)

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

參考文獻(xiàn)

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

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

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