隊列的定義表示實現(xiàn)

1、隊列的定義表示實現(xiàn)第1頁，共30頁，2022年，5月20日，0點20分，星期四3.2 隊列只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。1. 定義一、概念：例如：隊列 Q= (a1 , a2 , a3 , ， an )在隊尾插入元素稱為入隊；在隊首刪除元素稱為出隊。隊頭元素隊尾元素允許插入的一端為隊尾，允許刪除的一端為隊頭。2第2頁，共30頁，2022年，5月20日，0點20分，星期四與線性表相同，仍為一對一關(guān)系。順序隊或鏈隊，以循環(huán)順序隊更常見。只能在隊首和隊尾運算，且訪問結(jié)點時依照先進先出（FIFO）的原則。關(guān)鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。3.

2、 存儲結(jié)構(gòu)：4. 運算規(guī)則：5. 實現(xiàn)方式 ：2. 邏輯結(jié)構(gòu)：3第3頁，共30頁，2022年，5月20日，0點20分，星期四二、隊列的抽象數(shù)據(jù)類型定義ADT Queue 數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定a1 端為隊列頭，an 端為隊列尾。 基本操作： ADT Stack4第4頁，共30頁，2022年，5月20日，0點20分，星期四（1）初始化隊列 InitQueue(&Q) （2）入隊 EnQueue(&Q,e) （3）出隊 DeQueue(&Q,&e)（4）獲取隊頭元素內(nèi)容 GetH

3、ead(Q,&e) （5）判斷隊列是否為空 QueueEmpty(Q) 基本操作: 建隊列、判斷隊列是否為空、入隊、出隊、讀隊頭元素值，等等。5第5頁，共30頁，2022年，5月20日，0點20分，星期四鏈隊列類型定義： typedef struct QueuePtr front ; /隊頭指針 QueuePtr rear ; /隊尾指針 LinkQueue;結(jié)點類型定義： typedef struct QNode QElemType data; /元素 struct QNode *next; /指向下一結(jié)點的指針 Qnode , * QueuePtr ;關(guān)于整個鏈隊的總體描述鏈隊中任一結(jié)點的

4、結(jié)構(gòu)三、隊列的表示和實現(xiàn)1.單鏈隊列/ -隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)-6第6頁，共30頁，2022年，5月20日，0點20分，星期四a1anQ.frontQ.rearQ.frontQ.rear空隊列為了操作方便，添加一個頭結(jié)點，令頭指針指向頭結(jié)點。Q. front=Q. rear7第7頁，共30頁，2022年，5月20日，0點20分，星期四 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個空隊列 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗

5、Q.front-next = NULL; return OK;/ -基本操作的算法描述-建隊操作構(gòu)造空隊列Q8第8頁，共30頁，2022年，5月20日，0點20分，星期四Q(隊尾)(隊首)fronta1a2a3rearp鏈隊會滿嗎？一般不會，因為刪除時有free動作。除非內(nèi)存不足！入隊（尾部插入）：rear-next=S; rear=S;出隊（頭部刪除）：p=front-next; front-next=p-next; free(p);Se鏈隊列的入隊和出隊操作9第9頁，共30頁，2022年，5月20日，0點20分，星期四 Status EnQueue (LinkQueue &Q, QElem

6、Type e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; 10第10頁，共30頁，2022年，5月20日，0點20分，星期四 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front =

7、 Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; /一定要考慮 free (p); return OK;11第11頁，共30頁，2022年，5月20日，0點20分，星期四隊列的順序存儲結(jié)構(gòu)如下圖所示：附設(shè)兩個指針front和rear分別指示隊列頭元素的位置和隊列尾元素的下一個位置約定：初始化建空隊列時，令front=rear=0；2. 順序隊列12第12頁，共30頁，2022年，5月20日，0點20分，星期四（2） 空隊列的特

8、征？ 約定：front=rear問題：（1）怎樣實現(xiàn)入隊和出隊操作？核心語句如下：入隊(尾部插入)： Qrear=e ; rear+ ; 出隊(頭部刪除)： e=Qfront ; front+; （3）隊列會滿嗎？ 極易裝滿！因為數(shù)組通常有長度限制，而其前端空間無法釋放。有假溢出現(xiàn)象。如圖：13第13頁，共30頁，2022年，5月20日，0點20分，星期四解決假溢出的途徑采用循環(huán)隊列在順序隊中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但實際上數(shù)組中還有空位置，這就叫“假溢出”。討論：什么叫“假溢出” ？如何解決？將存儲隊列元素的一維數(shù)組首尾相接，形成一個環(huán)狀。14第14頁，共30頁，20

9、22年，5月20日，0點20分，星期四a3a2a10123N-1rearfront循環(huán)隊列（臆造）順序隊列a3a2a1frontrear 0 1 2 3 . .N-115第15頁，共30頁，2022年，5月20日，0點20分，星期四新問題：在循環(huán)隊列中，隊空時 front=rear；隊滿時也會有 front=rear；判決條件將出現(xiàn)二義性！解決方案有二：使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；人為浪費一個單元，約定：隊列頭指針在隊列尾指針的 下一位置上作為隊列呈“滿”狀態(tài)的標(biāo)志。則隊滿特征可改為front=(rear+1)%N （N為最大隊列長度）； 實際中常選用方案2（人為浪費一個單

10、元）16第16頁，共30頁，2022年，5月20日，0點20分，星期四建隊核心語句：Q. base=(QElemType *)malloc(sizeof (QElemType ）* MAXQSIZE); /分配空間關(guān)于整個順序隊的總體描述#define MAXQSIZE 100 /最大隊列長度 typedef struct QElemType *base; /隊列的基址 int front; /隊頭指針 int rear; /隊尾指針 SqQueue/ -循環(huán)隊列隊列的順序存儲結(jié)構(gòu)-17第17頁，共30頁，2022年，5月20日，0點20分，星期四隊空條件 : front = rear (初始

11、化時：front = rear )隊滿條件： front = (rear+1) % N (N=MAXQSIZE)隊列長度：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear問3： 在具有N個單元的循環(huán)隊列中，隊滿時共有多少個元素？ N-1個6 問1：左圖中隊列MAXQSIZE N=？問2：左圖中隊列長度L=？518第18頁，共30頁，2022年，5月20日，0點20分，星期四例1. 一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置? J2 J3J1 J4 J5front=1rear=0解：由圖可知，隊頭和隊尾指針的初態(tài)

12、分別為front=1和rear=0。刪除4個元素后front=5；再插入4個元素后，rear=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=519第19頁，共30頁，2022年，5月20日，0點20分，星期四例2. Q010是一個循環(huán)隊列，初始狀態(tài)為front=rear=0,畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。d, e, b, g, h 入隊d, e 出隊i, j, k, l, m 入隊b 出隊n, o, p 入隊20第20頁，共30頁，2022年，5月20日，0點20分，星期四討論：循環(huán)隊列的基

13、本操作如何實現(xiàn)？以建隊、入隊和出隊三種基本操作為例1）初始化一個空隊列算法要求：生成一空隊列算法操作：為隊列分配基本容量空間 設(shè)置隊列為空隊列，其特征即： front=rear=0（也可為任意單元，如1，2， ）21第21頁，共30頁，2022年，5月20日，0點20分，星期四建隊的完整算法：Status InitQueue ( SqQueue &Q ) /初始化空循環(huán)隊列 Q Q . base=(QElemType *) malloc(MAXQSIZE*sizeof(QElemType） ); /分配空間 if (!Q.base) exit(OVERFLOW); Q.front =Q.rea

14、r=0; /置空隊列 return OK; /InitQueue;22第22頁，共30頁，2022年，5月20日，0點20分，星期四算法說明：向循環(huán)隊列的隊尾插入一個元素分 析：(1) 插入前應(yīng)當(dāng)先判斷隊列是否滿？ if ( Q . rear + 1 ) % MAXQSIZE )=Q.front) return ERROR;(2）插入動作 Q. base Q. rear = e; Q. rear = ( Q . rear + 1 ) % MAXQSIZE;2） 入隊操作隊列尺寸先存放元素，后移動隊尾指針23第23頁，共30頁，2022年，5月20日，0點20分，星期四Status EnQueu

15、e(SqQueue &Q, QElemType e)/向循環(huán)隊列 q 的隊尾加入一個元素 e if ( (Q.rear+1) % MAXQSIZE = = Q. front ) return ERROR ; /隊滿則上溢 Q. base Q. rear = e; /新元素e入隊 Q. rear = ( Q . rear + 1 ) % MAXQSIZE; /指針后移 return OK; / EnQueue;入隊操作完整算法24第24頁，共30頁，2022年，5月20日，0點20分，星期四3）出隊操作算法說明：刪除隊頭元素，返回其值 e 分 析： （1） 在刪除前應(yīng)當(dāng)判斷隊列是否空？ if (

16、Q. front = Q. rear ) return ERROR; （2）刪除動作分析： 前面約定指針front指向隊首元素的位置，故： e = Q. base Q. front ; Q. front = ( Q. front + 1 ) % MAXQSIZE; 隊列尺寸先取出元素，后移動隊頭指針25第25頁，共30頁，2022年，5月20日，0點20分，星期四Status DeQueue ( SqQueue &Q, QElemType &e) /若隊列不空，刪除循環(huán)隊列q的隊頭元素， /由 e 返回其值，并返回OK if ( Q. front = = Q. rear ) return ER

17、ROR;/隊列空 e = Q. base Q.front ; Q. front=(Q. front+1) %MAXQSIZE ; return OK; / DeQueue出隊操作完整算法26第26頁，共30頁，2022年，5月20日，0點20分，星期四例3：編寫一個算法，利用棧和隊列的基本運算將指定隊列中的內(nèi)容進行逆轉(zhuǎn)。分析：假設(shè)為循環(huán)隊列。建立一個臨時棧temps，將指定隊列Q中的所有元素出隊并入棧到temps中，這樣隊列Q為空，再將temps中的所有元素出棧并入隊到Q隊中，這樣Q隊列中的內(nèi)容發(fā)生了逆轉(zhuǎn)。算法如下：void reverse(SqQueue &Q) QElemType x; SqStack temps; InitStack(temps);27第27頁，共30頁，2022年，5月20日，0點20分，星期四 while( ! QueueEmpty (Q) ) /初始化temps棧 DeQueue (Q, x); Push (temps, x); While( ! StackEmpty (temps) ) Pop (temps, x); EnQueue (Q, x); 28第28頁，共30頁，2022年，5月20日，0點20分，星期四本章小結(jié)線性表、棧、隊的異同點：相同