1、數(shù)據(jù)結構,3.1 棧及其應用,第三章 棧和隊列,3.2 隊列及其應用,3.3 鏈棧與鏈隊列,3.2 隊列及其應用,隊列(queue)簡稱隊，是一種只允許在表的一端進行插入操作, 而在表的另一端進行刪除操作的線性表。,a1,a2,a3,a4,a5,3.2 隊列及其應用,隊列(queue)簡稱隊，是一種只允許在表的一端進行插入操作, 而在表的另一端進行刪除操作的線性表。,a1,a2,a3,a4,a5,設（a1,a2 , a3 , . , an ）為一隊列 允許插入的一端稱作隊尾，允許刪除的一端稱為隊頭；則a1為隊頭元素，an為隊尾元素；,說明,隊頭元素,隊尾元素,3.2 隊列及其應用,隊列(que

2、ue)簡稱隊，是一種只允許在表的一端進行插入操作, 而在表的另一端進行刪除操作的線性表。,a1,a2,a3,a4,a5,設（a1,a2 , a3 , . , an ）為一隊列 在表尾插入元素的操作，稱為入隊操作；在表頭刪除元素的操作，稱為出隊操作；,說明,入隊,出隊,a6,a1,3.2 隊列及其應用,隊列(queue)簡稱隊，是一種只允許在表的一端進行插入操作, 而在表的另一端進行刪除操作的線性表。,a1,a2,a3,a4,a5,設（a1,a2 , a3 , . , an ）為一隊列 隊列具有先進先出的特點，所以又稱為先進先出表（FIFO表）,說明,【火車車廂重排問題 】,問題描述：一列貨運列

3、車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1n，即貨運列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應的車廂，車廂的編號應與車站的編號相同，這樣，在每個車站只需卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列他們。 車廂的重排工作可以通過轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個入軌、一個出軌和k個緩沖軌，緩沖軌位于入軌和出軌之間。設計算法解決火車車廂重排問題。,1）初始化操作InitQueue( /存儲數(shù)據(jù)元素的數(shù)組 int rear; /尾指針，指向隊尾元素的下一個位置 int queuesize;/當前分配的存儲容量 SqQueue1;,1類型定義方

4、法一,注：隊頭元素總在0單元,SqQueue1,如何改進出隊的時間性能？,例：a1a2a3a4依次入隊,a1,a2,a3,a4,入隊操作時間性能為O(1),二. 隊列的順序存儲結構,Q.base,例：a1a2依次出隊,a1,a2,a3,a4,二. 隊列的順序存儲結構,Q.base,例：a1a2依次出隊,二. 隊列的順序存儲結構,例：a1a2依次出隊,a2,a3,a4,二. 隊列的順序存儲結構,Q.base,例：a1a2依次出隊,二. 隊列的順序存儲結構,出隊操作時間性能為O(n),二. 隊列的順序存儲結構,Status DeQueue(SqQueue1 / DeQueue,Q,0,1,10,1

5、1,移動元素,Q.base,Q.rear,Q.queuesize,二. 隊列的順序存儲結構,#define QUEUE_INIT_SIZE 100 / 存儲空間初始分配量 #define QUEUE_INCREAMENT 2 / 分配增量typedef struct QElemType *base; /存儲數(shù)據(jù)元素的數(shù)組 int front; /頭指針，若隊列不空，指向隊列頭元素 int rear; /尾指針，指向隊尾元素的下一個位置 int queuesize;/當前分配的存儲容量 SqQueue2;,2類型定義方法二,SqQueue2,例：a1a2a3a4依次入隊,a1,a2,a3,a4,

6、入隊操作時間性能仍為O(1),二. 隊列的順序存儲結構,Q.base,例：a1a2依次出隊,a1,a2,a3,a4,二. 隊列的順序存儲結構,Q.base,出隊操作時間性能提高為O(1),如有3個元素(5,6,7)的隊列Q,Q,0,1,10,11,0,1,10,11,出隊之前,出隊之后,2,3,4,5,6,7,Q,2,3,4,5,6,7,Status DeQueue(SqQueue2 / DeQueue,Q.base,Q.front,Q.queuesize,Q.rear,二. 隊列的順序存儲結構,（a)空隊列,隊頭指針隊尾指針和隊列中元素之間的關系圖示,(c)J1和J2相繼出隊,假溢出！,隊列

7、的移動有什么特點？,整個隊列向數(shù)組下標較大方向移動,解決假溢出的方法有多種： 一是通過不斷移動元素位置，每當有元素出隊列時，后面的元素前移一個位置，使隊頭元素始終占據(jù)第一個位置。 二是采用循環(huán)隊列。,假溢出！,假溢出：當元素被插入到數(shù)組中下標最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。,5 4 3 2 1 0,Q.front,J6,J5,J4,此時隊空，有Q.front=Q.rear,此時隊滿，也有Q.front=Q.rear,?,有兩種方法：1）另設一個標志位以區(qū)分隊空、隊滿。2）少用一個元素空間，即當隊列達到上圖所示狀態(tài)時， 就認為隊列已滿，這時的條件是Q.front=Q.rear+1;,如何判斷循環(huán)隊列 隊空、隊滿？,63頁,Status InitQueue (SqQueue / InitQueue,/為Q.base動態(tài)分配內(nèi)存空間,/分配不成功則退出,/頭尾指針置0,/返回成功,Status EnQueue (SqQueue / EnQueue,Q.front,4 0,5,J1,J2,J3,J4,J5,利用求模實現(xiàn)尾指針“環(huán)狀增1”,/判斷是否隊滿，滿則不允許入隊,/若隊不滿，則將e入隊尾,/修改隊尾指針,/返回成功,Q.