【正文】 (6) ?ClearQueue(amp。Q): 置隊(duì)空操作，不論隊(duì)列是否為空，操作結(jié)果都是將 Q置為空隊(duì)列。 (7) ?QueueLength(Q): 求當(dāng)前隊(duì)列中元素的個(gè)數(shù)。 (8) ?DestroyQueue(amp。Q): 銷毀 Q隊(duì)列。 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 隊(duì)列的表示與實(shí)現(xiàn) 隊(duì)列有兩種存儲(chǔ)表示方法： 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) —— 順序隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) —— 鏈隊(duì)列 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 （ 1）隊(duì)列的順序表示與實(shí)現(xiàn) ——循環(huán)隊(duì)列 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和棧類似，常借助于一維數(shù)組來存儲(chǔ)隊(duì)列中的元素。為了指示隊(duì)首和隊(duì)尾的位置，尚需設(shè)置頭 (front)、尾 (rear)兩個(gè)指針，并 約定 ，在非空隊(duì)列中，頭指針始終指向隊(duì)列中頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置，如圖所示： 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 ―假溢出 ” 現(xiàn)象 ，如下圖所示 : 解決“假溢出”的方法有兩種： 1) 采用平移元素的方法 一旦發(fā)生“假溢出”就把整個(gè)隊(duì)列的元素平移到存儲(chǔ)區(qū)的首部，即：始終使 =0。 該方法的缺點(diǎn)：需大量移動(dòng)元素，效率低 2)將整個(gè)隊(duì)列作為循環(huán)隊(duì)列 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 隊(duì)空的條件： = 隊(duì)滿的條件： = 解決方法： ①設(shè)置標(biāo)志位 ②犧牲一個(gè)存儲(chǔ)空間，即 隊(duì)空的條件： = 隊(duì)滿的條件：(+1)%MAXQSIZE= 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 循環(huán)隊(duì)列的基本運(yùn)算 循環(huán)隊(duì)列類型定義 define MAXQSIZE 100 //最大隊(duì)列長(zhǎng)度 typedef struct { QElemType *base。 //初始化動(dòng)態(tài)分配空間 int front。 int rear。 } SqQueue。 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 1）初始化操作 int InitQueue(SqQueue amp。Q){ //構(gòu)造一個(gè)空隊(duì)列 = (QElemType *)malloc(MAXSIZE * sizeof(QElemType))。 if ( ! ) return 0。 = = 0。 return 1。 }//InitQueue 2）求隊(duì)列的長(zhǎng)度 int QueueLength(SqQueue Q){ //求隊(duì)列的長(zhǎng)度 return ( – + MAXQSIZE) % MAXQSIZE。 } 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 3）入隊(duì)列操作 int EnQueue(SqQueue amp。Q, QElemType e){ //插入元素 e為 Q的新的隊(duì)尾元素 if ((+1)%MAXQSIZE == ) return 0。 [] = e。 = (+1) % MAXQSIZE。 return 1。 } 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 4）出隊(duì)列操作 int DeQueue(SqQueue amp。Q, QElemType amp。e){ // 刪除 Q的隊(duì)頭元素 , 并用 e返回其值 if( == ) return 0。 e = []。 = (+1) % MAXQSIZE。 return 1。 } 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 （ 2）隊(duì)列的鏈?zhǔn)奖硎九c實(shí)現(xiàn) ——鏈隊(duì)列 ?鏈隊(duì)列：用鏈表表示的隊(duì)列； ?一個(gè)鏈隊(duì)列需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針惟一確定； ?每個(gè)鏈隊(duì)列對(duì)應(yīng)一個(gè)頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)； ?頭指針和尾指針均指向頭結(jié)點(diǎn)，則鏈隊(duì)列為空。 說明： 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 鏈隊(duì)列類型定義 typedef struct QNode { QElemType data。 struct QNode *next。 } QNode, *QueuePtr。 typedef struct{ QueuePtr front。 //隊(duì)頭指針 Queneptr rear。 //隊(duì)尾指針 } LinkQueue 鏈隊(duì)列的基本運(yùn)算 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 1）初始化操作 int InitQueue(LinkQueue amp。Q){ //構(gòu)造一個(gè)空隊(duì)列 ==(QueuePtr)malloc(sizeof(QNode))。 if ( ! ) return 0。 next = NULL。 return 1。 }//InitQueue 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 2）入隊(duì)列操作 int EnQueue(LinkQueue amp。Q, QElemType e){ //插入元素 e為 Q的新的對(duì)尾元素 p = (QueuePtr) malloc (sizeof(QNode))。 if (!p) return 0。 p data = e。 p next = NULL。 next = p。 = p。 return 1。 } 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 3）出隊(duì)列操作 int DeQueue(LinkQueue amp。Q, QElemType amp。e){ // 刪除 Q的隊(duì)頭元素 , 并用 e返回其值 if( == ) return 0。 p = next。 e = p data next= p next。 if( == p) = 。 free(p)。 return 1。 } 數(shù)據(jù)結(jié)構(gòu) 第 3章 棧和隊(duì)列 四、本章小結(jié) 棧 定義 表示與實(shí)現(xiàn)（順序棧和鏈棧） 應(yīng)用（表達(dá)式求值，遞歸調(diào)用等） 隊(duì)列 鏈隊(duì)列（定義，表示與實(shí)現(xiàn)） 循環(huán)隊(duì)列（定義，表示與實(shí)現(xiàn)） 定義