【正文】 隊一元素，剩余元素向隊頭方向平移 —— 費時 (2)當不能入隊時，檢查隊列中是否有空，若有則平移 —— 耗時 有效辦法：使 0單元接在 MaxSize1單元后 (邏輯上 )， 形成環(huán)形結構 —— 循環(huán)隊列 循環(huán)隊列 : ? 在循環(huán)隊列中，其存儲空間是首尾循環(huán)利用的，當隊尾指針rear指向最后一個存儲位置時，下一個所求的位置自動為數組空間的開始位置（即下標為 0的位置） m1 0 1 2 3 …… 隊列的初始狀態(tài) front rear 循環(huán)隊列的運算 設 以 Queue(0:MaxSize1)為循環(huán)隊列的存儲空間 初始隊空時， front=rear=0 入隊指針操作： rear= (rear+1)% MaxSize 退隊指針操作： front= (front+1)% MaxSize 在隊列操作時，由于有兩個指針，而且這兩個指針都會移動，因此判斷其隊空和隊滿的方法與普通的線性表的判斷方法有較大的不同，特別是在循環(huán)隊列。 循環(huán)隊列的判斷隊空、隊滿的辦法為： 當隊尾指針追上隊頭指針時為隊滿 即： if ((rear+1)% MaxSize= =front) 則隊滿； 否則： front= =raer 則為隊空。 此法優(yōu)點：僅根據 front、 rear指針就可做判斷 ,算法較簡單。 不足：實際利用的存儲單元為 MaxSize1個 （浪費一個存儲單元） 二、隊列的數據類型定義 ⑴ 隊列和指針分開定義 ElemType queue[MaxSize]。 /* MaxSize為已定義的常量*/ int front, rear, len。 其中 MaxSize的值確定了 queue數組所能存儲隊列的最大長度。 ⑵ 隊列的記錄定義 隊列的順序存儲結構同樣可以被定義在一個記錄類型中，假定該記錄類型用 QueueSq表示，則定義為： struct QueueSq { ElemType queue[MaxSize]。 int front, rear, len。 }。 ⑶ 隊列數組采用動態(tài)分配的動態(tài)定義 若要對存儲隊列的數組空間采用動態(tài)分配，則 QueueSq結構類型可定義為： struct QueueSq { ElemType *queue。 /*指向存儲隊列的數組空間 */ int front, rear, len。 /*隊首指針、隊尾指針、隊列 長度變量 */ int MaxSize。 /*queue數組長度 */ }。 1. 初始化隊列 第一種情況是隱含分配用于存儲隊列的固定大小的動態(tài)存儲空間，假定動態(tài)存儲空間的大小為 10。 void InitQueue(struct QueueSq* Q) { /*置隊列空間初始最大長度為 10*/ QMaxSize=10。 /*動態(tài)存儲空間分配 */ Qqueue=malloc(10*sizeof(ElemType))。 /*置隊列為空 */ Qfront=Qrear=0。 } 第二種情況是分配由參數指定大小的動態(tài)存儲空間。實用中使用任一種初始化算法均可。 void InitQueue(struct QueueSq* Q, int ms) { /*檢查 ms是否有效，若無效則退出運行 */ if(ms=0) {printf(ms值非法 !\n)。 exit(1)。} /*置隊列空間大小為 ms*/ QMaxSize=ms。 /*動態(tài)存儲空間分配，若分配失敗則退出運行 */ Qqueue=malloc(ms*sizeof(ElemType))。 if(!Qqueue) { printf(內存空間用完 !\n)。 exit(1)。 } /*初始置隊列為空 */ Qfront=Qrear=0。 2. 向隊列插入元素 void EnQueue(struct QueueSq* Q, ElemType x) { /*當隊列滿時進行動態(tài)重分配 */ if((Qrear+1)%QMaxSize==Qfront) againMalloc(Q)。 /*求出隊尾的下一個位置 */ Qrear=(Qrear+1)%QMaxSize。 /*把 item的值賦給新的隊尾位置 */ Qqueue[Qrear]=x。 } againMalloc()算法的具體定義如下： void againMalloc(struct QueueSq* Q) { /*空間擴展為原來的 2倍，并由 p所指向，原內容被自動拷貝到 p所指向的存儲空間中 */ ElemType *p。 p=realloc(Qqueue, 2*QMaxSize*sizeof(ElemType))。 if(!p) { /*分配失敗退出運行 */ printf(存儲空間用完 !\n)。 exit(1)。 } /*使 queue指向新的隊列空間 */ Qqueue=p。 /*把原隊列的尾部內容向后移動 MaxSize個位置 */ if(Qrear!=QMaxSize1) { int i。 for(i=0。 i=Qrear。 i++) Qqueue[i+QMaxSize]=Qqueue[i]。 Qrear+=QMaxSize。 /*隊尾指針后移 MaxSize個位置 */ } /*把隊列空間大小修改為新的長度 */ QMaxSize=2*QMaxSize。 } 3. 從隊列中刪除元素并返回 ElemType OutQueue(struct QueueSq* Q) { /*若隊列為空則終止運行 */ if(Qfront==Qrear) { printf(隊列已空，無法刪除 !\n)。 exit(1)。 } /*使隊首指針指向下一個位置 */ Qfront=(Qfront+1)%QMaxSize。 /*返回隊首元素 */ return Qqueue[Qfront]。 } 隊列的鏈接存儲結構和操作實現 ?隊列的鏈接存儲結構也是通過由結點構成的單鏈表實現的，此時只允許在單鏈表的表頭進行刪除和在單鏈表的表尾進行插入，因此它需要使用兩個指針：隊首指針 front和隊尾指針 rear。 ? front指向隊首結點的存儲位置， rear指向隊尾結點的存儲位置。 ?用于存儲隊列的單鏈表簡稱 鏈接隊列 或 鏈隊 。 采用鏈接存儲結構的隊列中數據節(jié)點的定義： struct QueueLk { sNode* front。 //隊首指針 sNode* rear。 //隊尾指針 }。 其中 sNode結點類型重寫如下： struct sNode { ElemType data。 /*值域 */ struct sNode* next。 /*鏈接指針域 */ }。 ? 一個鏈接存儲的隊列如下圖所示。 ...frontreara1 a 2an在類型為 QueueLk的鏈隊 HQ上進行隊列的各種操作的算法如下： 1. 初始化鏈隊 void InitQueue(struct QueueLk* HQ) { /*把隊首和隊尾指針置為空 */ HQfront=HQrear=NULL。 } 2. 向鏈隊中插入一個元素 void EnQueue(struct QueueLk* HQ, ElemType x) { /*得到一個由 newp指針所指向的新結點 */ struct sNode* newp。 newp=malloc(sizeof(struct sNode))。 if(newp==NULL) { printf(內存動態(tài)空間用完，退出運行 !\n)。 exit(1)。 } /*把 x的值賦給新結點的值域，把新結點的指針域置空 */ newpdata=x。 newpnext=NULL。 /*若鏈隊為空，則新結點既是隊首結點又是隊尾結點 */ if(HQrear==NULL) HQfront=HQrear=newp。 /*若鏈隊非空，則依次修改隊尾結點的指針域和隊尾指針， 使之指向新的隊尾結點 */ else HQrear=HQrearnext=newp。 } 3. 從隊列中刪除一個元素 ElemType OutQueue(struct QueueLk* HQ) { struct sNode* p。 ElemType temp。 /*若鏈隊為空則中止運行 */ if(HQfront==NULL) { printf(隊列為空無法刪除 !\n)。 exit(1)。 } /*暫存隊首元素以便返回 */ temp=HQfrontdata。 /*暫存隊首指針以便回收隊首結點 */ p=HQfront。 /*使隊首指針指向下一個結點 */ HQfront=pnext。 /*若刪除后鏈隊變?yōu)榭?，則需同時使隊尾指針變?yōu)榭?*/ if(HQfront==NULL) HQrear=NULL。 /*回收原隊首結點，返回被刪除的隊首元素 */ free(p)。 return temp。 } 作業(yè) ? 第 3 題 ? 算法分析題 第 2 題 ? 題中 第 1 題