資源描述：
《數(shù)據(jù)結構第07講-隊列-C.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第3章棧和隊列3.1棧3.2棧的應用舉例3.3棧與遞歸的實現(xiàn)3.4隊列3.4.1抽象數(shù)據(jù)類型隊列的定義3.4.2鏈隊列——隊列的鏈式表示和實現(xiàn)3.4.3循環(huán)隊列——隊列的順序表示和實現(xiàn)3.4.1抽象數(shù)據(jù)類型隊列的定義1.隊列的定義簡稱隊，是限定所有的插入只能在表的一端進行，而所有的刪除都在表的另一端進行的線性表。2.隊列的特點由于隊列的插入和刪除操作分別是在各自一端進行，每個元素必然按照進入的次序離隊，所以又把隊列稱為先進先出表(FirstInputFirstOutput，簡稱FIFO）。相關術語：表中允許插入的一端稱為隊尾(Rear)，允許刪除的一
2、端稱為隊頭(Front)向隊列中插入新元素稱為進隊或入隊，新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素離隊后，其后繼元素就成為新的隊首元素3.隊列的常見應用1）圖形的廣度優(yōu)先搜索法；2）優(yōu)先隊列；3）操作系統(tǒng)中的工作調(diào)度；4）用于“spooling”；先將輸出數(shù)據(jù)寫在磁盤上，再由打印機把先存入者先處理的順利將數(shù)據(jù)輸出。4.隊列的類型定義ADTQueue{數(shù)據(jù)對象：D＝{ai
3、ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關系：R＝{
4、ai-1,ai∈D,i=2,…,n}約定其中a1端為隊列頭，an端為
5、隊列尾。基本操作：}ADTQueue隊列的常用操作1）InitQueue(&Q)操作結果：構造空隊列Q2）DestroyQueue(&Q)條件：隊列Q已存在；結果：隊列Q被銷毀3）QueueLength(Q)初始條件：隊列Q已存在操作結果：返回Q的元素個數(shù)，即隊長4）GetHead(Q,&e)初始條件：Q為非空隊列操作結果：用e返回Q的隊頭元素5）EnQueue(&Q,e)初始條件：隊列Q已存在操作結果：插入元素e為Q的新的隊尾元素6）DeQueue(&Q,&e)初始條件：Q為非空隊列操作結果：刪除Q的隊頭元素，用e返回值7）ClearQueue(&
6、Q)條件：隊列Q已存在；結果：將Q清空第3章棧和隊列3.1棧3.2棧的應用舉例3.3棧與遞歸的實現(xiàn)3.4隊列3.4.1抽象數(shù)據(jù)類型隊列的定義3.4.2鏈隊列——隊列的鏈式表示和實現(xiàn)3.4.3循環(huán)隊列——隊列的順序表示和實現(xiàn)3.4.2鏈隊列——隊列的鏈式表示和實現(xiàn)隊列的物理存儲可以用順序存儲結構，也可用鏈式存儲結構。相應地，隊列的存儲方式也分為兩種，即順序隊列和鏈式隊列。1.鏈隊列的類型定義#defineMAXQSIZE100//最大隊列長度typedefstructQnode{QElemTypedata;stuctQnode*next;}QNode,
7、*QuenePtr;typedefstruct{QuenePtrfront;//隊頭指針QuenePtrrear;//隊尾指針}LinkQueue;2.隊列運算指針變化狀況a）空隊列Q．frontQ．rear∧a)x∧Q．frontQ．rearb)Q．frontQ．rearxy∧c)Q．frontQ．rearxy∧d)b）元素X入隊列c）Y入隊列d）X出隊列3.隊列在抽象類型中的幾種操作舉例例1：構造一個空隊列StatusInitQueue(LinkQueue&Q){//構造空隊列QQ.front=Q.rear=(QueuePtr)malloc(si
8、zeof(QNode));If(!Q.front)exit(OVERFLOW);//存儲分配失敗Q.front->next=NULL;returnOK;}//InitQueue;Q．frontQ．rear∧例2：銷毀空隊列StatusDestoryQueue(LinkQueue&Q){//銷毀隊列Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}//DestoryQueue;例3：入隊列StatusEnQueue(LinkQueue&Q,QElem
9、Typee){p=(QueuePrt)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲分配失敗p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}∧a1anQ.frontQ.rear∧eP例4：出隊列StatusDeQueue(LinkQueue&Q,QElemType&e){If(Q.front==Q.rear)returnERROR;p=Q.front->next;Q.front->next=p->next;e=p->data;if(Q.r
10、ear==p)Q.rear=Q.front;free(p);returnOK;}//DeQueue;Q．fr
