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