【正文】 1)假設以數(shù)組 sequ[m1]存放循環(huán)隊列的元素，設變量 rear和 quelen分別為指示隊尾元素位置和隊中元素個數(shù)，試寫出入隊和出隊算法。已知 S為指向鏈表中某結點的指針。 下一頁 上一頁 停止放映 [第 67頁 /68頁 ] 【 例 24】 利用循環(huán)隊列求 k階斐波那切數(shù)列某一式的值。而后將隊頭元素出隊，將第 k+1個元素入隊。 } } 下一頁 上一頁 停止放映 [第 66頁 /68頁 ] 求 k階斐波那切數(shù)列某一項 k階斐波那切數(shù)列 {ai}定義如下： 解決方法 : 建立一個容量為 k的循環(huán)隊列，將前 k個元素依次入隊。 else { p= next。e) { QNode *p。 } } 下一頁 上一頁 停止放映 [第 65頁 /68頁 ] （ 5） 取隊頭元素 若隊列不空 ， 則用 e返回隊頭元素； void GetHead(LinkQueue amp。 if(==p) =。 e=pdata。 if(==) cout隊列已空 。Q, ElemType amp。 下一頁 上一頁 停止放映 [第 64頁 /68頁 ] 鏈隊列的出隊操作 若隊列不空 ， 則刪除隊頭元素 ， 用 e返回其值 。 下一頁 上一頁 停止放映 [第 63頁 /68頁 ] 出隊操作要考慮兩種情況 當隊列長度大于 1時 ,只修改隊頭指針即可。 不為 1,修改頭指針 。若空 ,則顯示 隊列 ‘ 下溢 ’ 。 //在隊尾插入結點 s = s。 snext =NULL。 //建立新結點 s if（ s == NULL） cout“ 內(nèi)存無可用空間 ” 。 void EnQueue(LinkQueue amp。 step3 非空 ,將 T插入鏈中 ,修改 rear指針。 step2 判別 T是否為空 。 } return len。 while(p!=){ len++。Q) { QNode *p=。 //尾指針指向頭結點 } 下一頁 上一頁 停止放映 [第 59頁 /68頁 ] （ 2） 求隊列的長度 返回隊列的元素個數(shù) ， 即隊列的長度 。 //建立頭結點 next=NULL。 void InitQueue(LinkQueue amp。 // 隊尾指針 }。 struct LinkQueue { QNode *front。 }。 下一頁 上一頁 停止放映 [第 57頁 /68頁 ] 鏈隊列結點可定義： struct QNode { ElemType data。 隊頭指針 front就是單鏈表的頭指針，隊尾指針 rear則是指向單鏈表最后一個結點的指針。 e = [i]。e) { if(==) cout隊列已空 。 void GetHead(SqQueue amp。 e = []。e) { if(==) cout隊列已空 。 void DeQueue(SqQueue amp。 step2 隊頭指針后移一個位置。 } } 下一頁 上一頁 停止放映 [第 52頁 /68頁 ] （ 3）出隊操作 算法描述 : step1 判別隊列是否為空 。 else { = (+1)%。 void EnQueue(SqQueue amp。 step2 隊尾指針后移一個位置 ,將新結點元素值存入當前結點單元。 } 這里 sz為隊列最大長度 ，數(shù)組長度 length比 sz大一。 = = 0。 void InitQueue(SqQueue amp。 非空 ,取值為 .F.。 ? 由于隊頭指針所指單元總是空的， length比實際能存儲的元素多一。 SqQueue q。 // 隊頭指針 int rear。 // 存放元素的數(shù)組 int length。由于隊列的特殊性， 在順序存儲的隊列中，出隊和入隊操作都不移動元素而是移動指針。 else rear＝ rear + 1。 else front ＝ front + 1。 這樣構成循環(huán)隊列。 下一頁 上一頁 停止放映 [第 43頁 /68頁 ] 循環(huán)隊列 設定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1 。 else rear = rear + 1 。 front front rear D E F G H rear 示例 下一頁 上一頁 停止放映 [第 42頁 /68頁 ] 解決假溢出的方法 如果使當 rear = MAXSIZE+1 時，即超過隊列末端時，令 rear = 1；從而使隊列的首尾相連接。 下一頁 上一頁 停止放映 [第 40頁 /68頁 ] 舉例：順序隊列的入隊、出隊操作 （ A）空隊列 （ B） A、 B、 C、 D、 E入隊 （ C） A、 B、 C出隊 A B C D E front rear front rear D E front rear 入隊時， rear在變 出隊時， front在變 下一頁 上一頁 停止放映 [第 41頁 /68頁 ] 順序隊列入隊、出隊操作（續(xù)） D） F、 G、 H入隊 (E） D、 E、 F、 G、 H出隊，出現(xiàn)假 ? 溢出 ? 注：一方面隊列中是空的，另一方面又出現(xiàn)溢出。 front = front +1 ； x = queue [front ]； front rear a1 a2 … a n 下一頁 上一頁 停止放映 [第 39頁 /68頁 ] 問題： 讀第 1個元素時： front = front +1 x = queue[front]； front = front +1； 讀其它元素時： x = queue[front]； front = front +1； 顯然，對于第 1個元素和其它元素的讀操作，將出現(xiàn)不一致。 隊列具有先進先出（ FIFO）的特點。 進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭