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