循環(huán)隊(duì)列隊(duì)空與隊(duì)滿兩個(gè)狀態(tài)的判斷算法分析
2014-07-24 15:53:26張春玲
新媒體研究 2014年8期
張春玲
摘 要 入隊(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
