【正文】 r rear p front rear x出 隊 ^ x y If( ==p) = 福州大學至誠學院 鏈隊列的操作實現(xiàn) —InitQueue //構造一個空的隊列 Q Status InitQueue(LinkQueue amp。Q) { =(QueuePtr)malloc(sizeof(QNode) )。 = 。 if(!) return(OVERFLOW)。 next = NULL。 return OK。 } // InitQueue 福州大學至誠學院 鏈隊列的操作實現(xiàn) – DestroyQueue //銷毀隊列 Q Status DestroyQueue(LinkQueue amp。Q) { while( ){ = next。 free()。 = 。 } return OK。 } 福州大學至誠學院 鏈隊列的操作實現(xiàn) – EnQueue //插入元素 e為新的隊尾元素 Status EnQueue(LinkQueue amp。Q, QelemType e) { p = ( QueuePtr )malloc(sizeof(QNode))。 if(!p) return(OVERFLOW)。 pdata = e。 p next = NULL。 next = p。 = p。 return OK。 } 福州大學至誠學院 鏈隊列的操作實現(xiàn) —DeQueue //刪除隊列 Q 的隊頭元素并用 e返回其值 Status DeQueue(LinkQueue amp。Q, QelemType amp。e) { if( == ) retrun ERROR。 p = next。 e = pdata。 next = pnext。 if( == p) = 。 free(p)。 return OK。 } 福州大學至誠學院 循環(huán)隊列－隊列的順序表示和實現(xiàn) define MAXQSIZE 100 //最大隊列長度 typedef struct { QElemType *base。 // 動態(tài)分配存儲空間 int front。 // 頭指針，若隊列不空，指向隊列頭元素 int rear。 // 尾指針 ,若隊列不空指向 隊列尾元素的下一個位置 } SqQueue。 福州大學至誠學院 1 2 3 4 5 0 空隊列 rear=0 front=0 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入隊 J4 J5 J6 front rear rear 1 2 3 4 5 0 front J1,J1,J3入隊 rear 1 2 3 4 5 0 J1,J2,J3出隊 J1 J2 J3 front front front front ?存在問題： ?當 front=0,rear=M時再有元素入隊發(fā)生溢出 ——真溢出 ?當 front≠0,rear=M 時再有元素入隊發(fā)生溢出 ——假溢出 rear 福州大學至誠學院 ? 解決方案 ?隊首固定，每次出隊剩余元素向下移動 ——浪費時間 ?循環(huán)隊列 ? 基本思想：把隊列 設想成環(huán)形 ，讓 sq[0]接在 sq[M1]之后，若 rear+1==M,則令 rear=0。 ? 實現(xiàn)：利用 “ 模 ” 運算 ? 入隊 : base[rear]=x。 rear=(rear+1)%M。 ? 出隊： x=base[front]。 front=(front+1)%M。 ? 隊滿、隊空判定條件 福州大學至誠學院 0 1 2 3 4 5 rear front J5 J6 J7 0 1 2 3 4 5 rear front J4 J9 J8 隊空： front==rear 隊滿： front==rear J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) J4 福州大學至誠學院 解決方案 ? 設一個布爾變量以區(qū)別隊列的空和滿 ? 使用一個計數器記錄隊列中元素的總數 ? 少用一個元素空間，約定當循環(huán)數組中元素個數達到maxsize1時隊列為滿，即以隊列頭指針指向隊列尾指針的下一位置（指環(huán)的下一位置 )上作為隊列呈 ” 滿 “ 的標志 隊空： front==rear 隊滿： (rear+1)%M==front 福州大學至誠學院 循環(huán)隊列空或滿的判斷 0 1 2 3 4 5 J3 J4 J5 (a)一般隊列 0 1 2 3 4 5 (c)空隊列 J6 J3 J4 J5 0 1 2 3 4 5 J7 (b)滿隊列 福州大學至誠學院 循環(huán)隊列實現(xiàn) define MAXSIZE 100 typedef struct { QElemType *base。 // 存儲空間基地址 int front。 // 隊頭指針 int rear。 // 隊尾指針 } SqQueue。 福州大學至誠學院 循環(huán)隊列實現(xiàn) – InitQueue //初始化空隊列 Status InitQueue(SqQueue amp。Q) { =(QElemType*)malloc(sizeof(QElemType)*MAXSIZE )。 if(!) return(OVERFLOW)。 = = 0。 return OK。 } 福州大學至誠學院 循環(huán)隊列實現(xiàn) – EnQueue //入隊列 Status EnQueue(SqQueue amp。Q, QelemType e) { if((+1)% MAXSIZE == ) return(ERROR)。 [] = e。 = (+1) % MAXSIZE。 return OK。 } 福州大學至誠學院 循環(huán)隊列實現(xiàn) – DeQueue //出隊列 Status DeQueue(SqQueue amp。Q, QelemType amp。e) { if( == ) retrun ERROR。 e = []。 = (+1) % MAXSIZE。 return OK。 } 福州大學至誠學院 寫出以下程序段的輸出結果（隊列中的元素類型 QElemType 為 char）。 void main( ){ Queue Q。 InitQueue(Q)。 Char x=?e‘, y=?c‘。 EnQueue(Q, ?h‘)。 EnQueue(Q, ?r‘)。 EnQueue(Q, y)。 DeQueue(Q, x)。 EnQueue(Q, x)。 DeQueue(Q, x)。 EnQueue(Q, ?a‘)。 While ( !QueueEmpty(Q) ){ DeQueue(Q, y)。 Printf(y)。 } Printf(x)。 }