【正文】 隊尾指示器 rear加 1等于隊頭指示器 front為隊列滿的條件。即順序循環(huán)隊列的隊列滿條件為 (rear+1)%MaxQueueSize==front。 順序循環(huán)隊列的隊列空條件仍然為 rear==front。 86 順序循環(huán)隊列的定義和實現(xiàn) ： 根據(jù)上面對順序循環(huán)隊列的分析，我們有順序循環(huán)隊列類的定義和實現(xiàn)如下： ＃ include ＃ include const int MaxQueueSize=100。 struct SequentQueue { elemtype queue[MaxQueueSize]。 //將隊列中元素定為數(shù)組型，元素類型為 elemtype int front。 //隊頭 int rear。 //隊尾 }。 87 ： 1)初始化隊列 IniQueue(amp。q) 將隊列 q設(shè)置成一個空隊列。 2)入隊列 EnQueue(amp。q,x) 將元素 x插入到隊尾中，也稱“進隊” ，“插入”。 3)出隊列 Delqeue (amp。q) 將隊列 q的隊頭元素刪除，也稱“退隊”、“刪除”。 4)取隊頭元素 GetHead (q) 得到隊列 q的隊頭元素之值。 5)判隊空 Empty(q) 判斷隊列 q是否為空，若為空返回 1，否則返回 0。 88 隊列的抽象數(shù)據(jù)類型可描述為： ADT QUEUE IS DATA：含有 n個元素 a1,a2,a3,…an ，按 FIFO規(guī)則存放，每個元素的類型為 elemtype Operation： void IniQueue(amp。q) //將隊列 q設(shè)置成一個空隊列。 void EnQueue (amp。q,x) //將元素 x插入到隊尾中，也稱“進隊” ，“插入”。 void DelQueue (amp。q) //將隊列 q的隊頭元素刪除，也稱“退隊”、“刪除”。 Elemtype GetHead (q) //得到隊列 q的隊頭元素之值。 int Empty (q) //判斷隊列 q是否為空，若為空返回 1，否則返回 0。 End queue 89 ： IniQueue (amp。q) void IniQueue(SequentQueue amp。q) { = =MaxQueueSize1 。 } 90 EnQueue(amp。q,x) void EnQueue (SequentQueue amp。q, elemtype x) { if((+1)%MaxQueueSize = = ) { cerr隊列已滿 !endl。 exit(1)。 } else { []=x。 =(+1)%MaxQueueSize。 } } 91 (3) 出隊列 void DelQueue(SequentQueue amp。q ) { if (= =) { cerr隊列已空 !endl。 exit(1)。 } else =(+1)%MaxQueueSize。 } elemtype DelQueue(SequentQueue amp。q ) { elemtype temp。 if (= =) { cerr隊列已空 !endl。 exit(1)。 } else { temp=[]。 =(+1)%MaxQueueSize。 return temp。 } } 92 (4) 取隊頭元素（注意得到的應(yīng)為頭指針后面一個位置值） elemtype GetHead(SequentQueue q ) { if (= =) {cerr隊列空 !endl。 exit(1)。 } else return [(+1)%MaxQueueSize]。 } (5) 判隊列空否 int Empty(SequentQueue q ) { if (= =) return 1。 else return 0。 } 93 上述文件名為 。一個 6個元素的順序循環(huán)隊列的入隊列過程見圖 3―10 。其中圖 3―10 （ a 3―10 （ b）3―10 （ c）為循環(huán)情況的入隊列過程。 94 圖 3―10 順序循環(huán)隊列的入隊列過程 012354r e a rf r o n t( a )012354f r o n tr e a r( b )DE012354r e a r( c )DEFf r o n tDD D E E D F 95 一個 6個元素的順序循環(huán)隊列的出隊列過程見圖 3―11 。其中圖 3―11 （ a）為初始狀態(tài)，3―11 （ b圖 3―11 （ c）為循環(huán)情況的出隊列過程。 96 圖 3― 11 順序循環(huán)隊列的出隊列過程 012354f r o n t( a )012354f r o n tr e a r( b )GF012354r e a r( c )Gf r o n tFE Gr e a rF G F G E E F G 97 循環(huán)隊列：逆時針運行示意圖 Queue 0 1 2 MaxQueueSize1 MaxQueueSize2 front 隊首指針 rear 隊尾指針 規(guī)定： 隊空： front==rear 隊滿： front==(rear+1)%MaxQueueSize 隊尾元素： elements[rear] 隊首元素： elements [ (front+1) % MaxQueueSize ] @ @ @ @ 98 循環(huán)隊列：滿隊列示意圖 Queue 0 1 2 MaxQueueSize1 MaxQueueSize2 front 隊首指針 rear 隊尾指針 front==(rear+1) % MaxQueueSize 本圖滿足上述隊滿條件。 由圖可知：隊滿時隊首指針所指的單元不能利用，此時再入列會使隊列變成空隊列 ( front==rear ) 隊尾元素 elements[rear] 隊首元素 @ @ @ @ @ @ @ @ @ @ @ @ 99 順序循環(huán)隊列的應(yīng)用 由于順序循環(huán)隊列和順序隊列結(jié)構(gòu)近似，但順序循環(huán)隊列的功能大大優(yōu)于順序隊列的功能，所以順序隊列幾乎不被采用。 順序循環(huán)隊列的應(yīng)用很廣泛。例如，操作系統(tǒng)中的各種數(shù)據(jù)緩沖區(qū)的先進先出管理，應(yīng)用系統(tǒng)中的各種事件排隊管理，等等。這里我們討論一個用順序循環(huán)隊列和順序堆棧實現(xiàn)判斷一個字符序列是否是回文的例子。 100 例 3―2 編程序判斷一個字符序列是否是回文 (回文是指一個字符序列以中間字符為基準兩邊字符完全相同 )。 程序從鍵盤輸入一個字符序列存入字符串 str中，字符串長度小于等于 80，輸入字符序列以回車換行符為結(jié)束標記，字符串 str中不包括回車換行符。把字符串中字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的元素和退棧的元素是否相等，若全部相等則該字符序列是回文，否則就不是回文。程序如下： 101 ＃ include typedef char elemtype。 //定義具體應(yīng)用的數(shù)據(jù)類型 elemtype ＃ include“ ＃ include“ void main(void) { sequentStack myStack。 sequentQueue myQueue。 char str[80]。 cout輸入字符序列，回車換行符結(jié)束： endl。 102 (str,80)。 // int h=strlen(str)。 // for(int i=0。ih。i++) { EnQueue( amp。myQueue,str[i])。 Push(amp。myStack,str[i])。 } while(!Empty(myQueue)) { if(DelQueue(myQueue)!=Pop(amp。myStack)) { cout不是回文 !endl。 103 return。 } } cout是回文 !endl。 } 第一次程序運行狀態(tài)為： 輸入字符序列，回車換行符結(jié)束： ABCDEDCBA 字符序列是回文 ! 104 第二次程序運行狀態(tài)為： 輸入字符序列，回車換行符結(jié)束： ABCDEDC 字符序列不是回文 ! 判斷一個字符序列是否是回文還有更簡單的方法。這里的程序主要是為了舉例說明順序隊列類和順序堆棧的使用方法。 105 優(yōu)先級隊列和順序優(yōu)先級隊列 優(yōu)先級隊列（ PriorityQueue）是帶有優(yōu)先級的隊列。隊列是數(shù)據(jù)元素的先進先出表，即最先進入隊列的元素將最先被刪除。但在有些軟件系統(tǒng)中有時也要求把進入隊列中的元素分優(yōu)先級，出隊列（即刪除）時，首先選擇優(yōu)先級最高的元素出隊列，對優(yōu)先級相同的元素則按先進先出的原則出隊列。簡單的優(yōu)先級隊列也可不考慮優(yōu)先級相同的元素的先進先出問題。 106 順序優(yōu)先級隊列定義和實現(xiàn) ： 通常優(yōu)先級隊列的優(yōu)先級為一數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級越高。一個不考慮優(yōu)先級相同元素的先進先出問題的順序優(yōu)先級隊列類的定義和實現(xiàn)如下： ＃ include ＃ include const int MaxpQueueSize=100。 struct SeqPQueue { elemtype data[MaxpQueueSize]。 //抽象類型 elemtype int size。 // } 107 ： 1).void IniPQueue(SeqPQueue amp。q) //初始化隊列 2） void PQInsert(SeqPQueue amp。q,elemtype item)。 //把元素 item 3) elemtype PQDelet