算法資料循環(huán)隊列

1、3.2循環(huán)隊列目錄隊列的邏輯結(jié)構和基本計算隊列的存儲結(jié)構循環(huán)隊列的運算隊列的概念隊列是一種只允許在表的一端（稱為隊尾）進行插入，在另一端（稱為對頭）進行刪除的線性表。隊列的概念隊列是一種只允許在表的一端（稱為隊尾）進行插入，在另一端（稱為對頭）進行刪除的線性表。只能刪除隊頭的結(jié)點a1只能在隊尾插入結(jié)點x增加結(jié)點刪除結(jié)點隊列的概念隊列是一種只允許在表的一端（稱為隊尾）進行插入，在另一端（稱為對頭）進行刪除的線性表。 先排隊的先離開與我們生活中的排隊非常相似 晚排隊的晚離開 不允許插隊 不允許中途離隊隊列有5種基本運算因此，隊列也稱先進先出(FIFO)來使用和管理隊列。隊列的5種基本運算將隊列Q置

2、成空隊列置隊空SetNull(Q)獲取有效結(jié)點長度GetLength(Q)取頭結(jié)點GetHead(Q)入隊InsQueue(Q, x)出隊DelQueue(Q)54321隊列的5種基本運算N個結(jié)點數(shù)返回隊列中的結(jié)點數(shù)置隊空SetNull(Q)獲取有效結(jié)點長度GetLength(Q)若N為零，則為空隊列取頭結(jié)點GetHead(Q)入隊InsQueue(Q, x)出隊DelQueue(Q)54321隊列的5種基本運算讀取隊列Q中頭結(jié)點的值置隊空SetNull(Q)隊列中的結(jié)點保持不變獲取有效結(jié)點長度GetLength(Q)取頭結(jié)點GetHead(Q)入隊InsQueue(Q, x)出隊DelQue

3、ue(Q)54321隊列的5種基本運算x將結(jié)點x插入到隊列Q的隊尾置隊空SetNull(Q)獲取有效結(jié)點長度GetLength(Q)取頭結(jié)點GetHead(Q)入隊InsQueue(Q, x)出隊DelQueue(Q)54321隊列的5種基本運算刪除隊列頭結(jié)點置隊空SetNull(Q)獲取有效結(jié)點長度GetLength(Q)取頭結(jié)點GetHead(Q)入隊InsQueue(Q, x)出隊DelQueue(Q)54321目錄隊列的邏輯結(jié)構和基本計算隊列的存儲結(jié)構循環(huán)隊列的運算隊列的存儲結(jié)構常用隊列的存儲結(jié)構順序隊列循環(huán)隊列鏈接隊列本章重點講解順序隊列的存儲結(jié)構一維數(shù)組來 存放節(jié)點數(shù)據(jù)數(shù)組下標01

4、2amsizea1 a2 a3當隊列采用順序存儲結(jié)構時，可利用一維數(shù)組來存放結(jié)點數(shù)據(jù)。ann - 1nmsize - 1順序隊列的存儲結(jié)構必須有活動的 表頭和表尾的索引一維數(shù)組來 存放節(jié)點數(shù)據(jù)數(shù)組下標012amsize隊列的操作只能在表頭和表尾進行，且不移動隊列的結(jié)點。headn - 1n頭尾索引即頭尾結(jié)點對應的數(shù)組下標tailmsize - 1a1a2a3an順序隊列的結(jié)構描述一維數(shù)組來 存放節(jié)點數(shù)據(jù)數(shù)組下標012amsizen - 1nmsize - 1#definemsize128隊中可能he最a大d 結(jié)點數(shù)a1typedefstructa2a3unsigned chararraumsi

5、ze;隊中的結(jié)點存于一維數(shù)組中unsigned charhead;頭索引anunsgined chartail;尾索引tailQueue;順序隊列的存儲結(jié)構當要刪除一結(jié)點時一維數(shù)組來 存放節(jié)點數(shù)據(jù)數(shù)組下標012amsizehead出隊運算可描述為：head+;n - 1ntailmsize - 1再將頭索引加1， 使其指向下一結(jié)點a1a2a3an必須刪除索引head所指向的結(jié)點順序隊列的存儲結(jié)構當要插入一結(jié)點時amsize入隊運算可描述為：arraytail+;012headn - 1ntailmsize - 1再將頭索引加1， 使其指向下一結(jié)點必須將結(jié)點值插入到尾索引tail所指向的結(jié)點a1

6、a2a3anx順序隊列的存儲結(jié)構當隊列裝滿時amsize產(chǎn)生該現(xiàn)象的原因是：被刪除的結(jié)點（出隊結(jié)點） 的空間永遠不能再使用。012headn - 1nmsize - 1尾索引tail等于最大結(jié)點msize時，采用循環(huán)隊列當隊滿時，若再做入隊 tail操作會產(chǎn)生“上溢”a1a2a3an后果不可預測循環(huán)隊列將將順序隊列的數(shù)組設想為一個首尾相接的圓環(huán)，即接在arraymsize -1之后的是array0。amsizea1012head1這種意義的隊列稱為循環(huán)隊列。a2a2 a3a1head0anann - 1n - 1mtasiilze - 1n在入隊和出隊操作時須對頭尾索引進行特殊處理ntail

7、msize - 1循環(huán)隊列的入隊出隊操作amsize1a2a1headtail0ann - 1msize - 1tail利用模運算， 則可優(yōu)化為：tailnarraytail+ = x; tail % = msize;入隊后尾索引加1尾索引求模arraytail+ = x; if (tail =msize)tail = 0;入隊后尾索引加1若尾索引上溢則置尾索引為上界循環(huán)隊列的入隊出隊操作amsize1a2head0a1tailann - 1msize - 1nhead+;head % = msize;入隊后尾索引加1尾索引求模循環(huán)隊列的隊空與隊滿情況分析cdbaefgh如何確定隊空還是隊滿呢

8、?headtailhead tail循環(huán)隊列的類型定義count = 0head tailcount = msizecdbeheadaftailhg循環(huán)隊列的類型定義去掉尾索引#define typedefmsizestruct128增加結(jié)構描述countunsigned char unsigned char unsgined charQueue;arraumsize; head;tail;#definemsize128typedefstructunsigned chararraumsize; unsigned charhead; unsgined charcount;Queue;有效結(jié)點數(shù)c

9、ount = 0head tail去掉尾索引count = msizecdbeheadaf hgtail循環(huán)隊列的類型定義#definemsize128count初始值為0typedefstruct u入隊時，count加一head + countu 出un隊sig時ne，d ccohuanrt減arr一aumsize;u 滿un隊sig時ne，d cchoaurnth等ea于d;msizeunsgined charcount;u 空隊時，count等于0Queue;有效結(jié)點數(shù)#definemsize128typedefstructunsigned chararrau tail =msize;

10、unsigned charhead; unsgined chartail;Queue;增加結(jié)構描述countcount = 0head tailcount = msizecdbeheadaf tailhg目錄隊列的邏輯結(jié)構和基本計算隊列的存儲結(jié)構循環(huán)隊列的運算循環(huán)隊列的運算置隊空獲取有效結(jié)點長度取頭結(jié)點入隊出隊置隊空置隊空獲取有效結(jié)點長度習慣上也可順便取頭結(jié)點將頭索引置為0入隊只要將隊列的有效結(jié)點數(shù)置為0即可置隊空出隊void SetNull(lpQueue * lp)lp head= 0;lp count = 0;獲取有效結(jié)點長度置隊空獲取有效結(jié)點長度取頭結(jié)點入隊出隊unsigned cha

11、r GetLength(lpQueue * lp)return (lp count);獲取有效結(jié)點長度置隊空獲取有效結(jié)點長度取頭結(jié)點入隊出隊unsigned char GetHead(lpQueue * lp)return (lp arraylp head);獲取有效結(jié)點長度置隊空獲取有效結(jié)點長度取頭結(jié)點入隊出隊BOOL InsQueue(lpQueue * lp, unsigned char x)return TRUE; else return FALSE;if (lp count msize) lp array(lp head lp count)% msize = x;lp count+;獲取有效結(jié)點長度unsigned char DelQueue(lpQueue * lp