數(shù)據(jù)結(jié)構(gòu)課件第三章4講

2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室1/10第三章棧和隊(duì)列第4講3.4

隊(duì)列

1、隊(duì)列的定義及特點(diǎn)

2、鏈隊(duì)列問題

3、隊(duì)列的順序表示和實(shí)現(xiàn)

4、循環(huán)隊(duì)列

2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室2/103.2隊(duì)列隊(duì)列的定義及特點(diǎn)隊(duì)列的定義隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列的特點(diǎn)先進(jìn)先出(FIFO)

2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室3/10a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)雙端隊(duì)列a1a2a3…….an端1端2入隊(duì)出隊(duì)出隊(duì)入隊(duì)2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室4/10鏈隊(duì)列結(jié)點(diǎn)定義typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;Typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室5/10frontrearx入隊(duì)^xfrontreary入隊(duì)x^yfrontrearx出隊(duì)x^yfrontrear空隊(duì)^frontreary出隊(duì)^2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室6/10鏈隊(duì)列入隊(duì)算法鏈隊(duì)列出隊(duì)算法入隊(duì)出隊(duì)2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室7/10隊(duì)列的順序表示和實(shí)現(xiàn)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sq[M]front=0rear=0123450隊(duì)空123450frontJ1,J2,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素位置初值front=rear=0空隊(duì)列條件：front==rear入隊(duì)列：sq[++rear]=x;出隊(duì)列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室8/10存在問題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=0,rear=M-1時，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front0,rear=M-1時，再有元素入隊(duì)發(fā)生溢出——假溢出解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動——浪費(fèi)時間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實(shí)現(xiàn)：利用“?！边\(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];隊(duì)滿、隊(duì)空判定條件2023/9/27計(jì)算機(jī)科學(xué)與技術(shù)教研室9/10012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個元素空間：隊(duì)空