循環隊列隊空與隊滿兩個狀態的判斷算法分析

張春玲

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

關鍵詞 循環隊列；隊空隊滿；入隊出隊

中圖分類號：TP3 文獻標識碼：A 文章編號：1671-7597（2014）08-0067-01

線性表是數據結構中比較重要的一種邏輯結構，插入刪除操作是線性表的基本操作，當進行這些操作時，不僅需要考慮插入、刪除的位置是否合法性，仍然需要考慮‘滿與‘空這兩種狀態，但是，由于棧和隊列都是受限制的線性表，它們已經規定了進行插入、刪除的位置，所以插入、刪除時不需要再考慮位置的合法性，只需要考慮‘滿與‘空。

1 隊列與棧的區別

數據結構中，隊列是只允許在一端進行刪除（隊頭）另一端進行插入（隊尾）的線性表；棧是只允許在一端進行插入刪除（棧頂）的線性表。由于兩者都是線性表，則遵循線性表的存儲結構表示—順序存儲以及鏈式存儲，這里主要討論靜態分配的順序存儲結構。如下：

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

typedef struct {

Elemtype data[MAXSIZE]；//一維數組

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

}sqStack；

typedef struct {

Elemtype data[MAXSIZE]；//一維數組

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

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

}sqQueue；

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

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

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

順序隊列的“假上溢”現象：

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

3 循環隊列隊空與隊滿的判斷

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

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

初始化A=0，B=0；

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

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

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

初始化Count=0；

出隊時，當Count==0隊空，不能出隊，然后Count--；

入隊時，當Count==MAXSIZE隊滿，不能入隊，然后Count++。

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

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

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

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

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

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

入隊時，當（rear+1）%MAXSIZE==front隊滿，不能入隊。

算法五、將靜態分配的循環隊列改為動態分配的循環隊列。

以上可見，循環隊列不能使用動態分配的一維數組實現，但是循環隊列也是順序隊列，遵循順序存儲結構的分配方式，即可以靜態分配存儲空間，也可以根據隊列的長度動態分配存儲空間。如下：順序隊列在動態分配順序存儲結構：

#define QUESIZE 100 //初始分配量

#define QUEUEINCREMENT 10 //動態分配增量

typedef struct{

ElemType *elem； //動態分配存儲空間基址

int front；

int rear；

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

}sqQueue；

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

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

4 總結

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

參考文獻

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2013.

[2]顧奇峰，動態增長型循環隊列的實現[J].微計算機信息，2007（23）：262-264.

[3]高永平，循環隊列入隊算法的研究[J].計算機與現代化，2005（4）：9-13.endprint