[文學(xué)]第四章棧和隊(duì)列(編輯修改稿)
2025-11-10 13:56 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 mp。 Q)。 void ClearQueue (QueueType amp。 Q)。 end QUEUE 假定有一個(gè)隊(duì)列 q，其元素類型為整型 int，下面給出調(diào) 用上述操作的一些例子。 (1) InitQueue(q)。 //把隊(duì)列 q置為一個(gè)空隊(duì)列 (2) EnQueue(q,35)。 //元素 35進(jìn)隊(duì)，隊(duì)列為（ 35） (3) int x=12。 EnQueue(q,2*x+3)。 //元素 2*x+3的值 27進(jìn)隊(duì)，此時(shí)隊(duì)列為（ 35,27） (4) EnQueue(q,16)。 //元素 16進(jìn)隊(duì)，此時(shí)隊(duì)列為 (35,27,16) (5) coutPeekQueue(q)endl。 //輸出隊(duì)首元素 35,原隊(duì)列保持不變 (6) OutQueue(q)。 OutQueue(q)。 //依次刪除隊(duì)列元素 35和 27，此時(shí)隊(duì)列為 (16) (7)while(!EmptyQueue(q)) coutOutQueue(q)“ “。 //依次輸出隊(duì)列 q中的所有元素 練習(xí)：利用棧實(shí)現(xiàn)隊(duì)列的運(yùn)算 void EnQueue(s1,x) stack s1。 int x。 { if(s1top==n) cout“隊(duì)列已滿！” endl。 else push(s1,x)。 } void OutQueue(s1,s2,x) stack s1,s2。 int x。 { =1。 while(!EmptyStack(s1)) push(s2,pop(s1))。 x=pop(s2)。 while(!EmptyStack(s2)) push(s1,pop(s2))。 } bool EmptyQueue(s1) stack s1。 { if(EmptyStack(s1)) return ture。 else return false。 } 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) 使用數(shù)組和兩個(gè)整型變量分別存儲(chǔ)隊(duì)首和 隊(duì)尾元素的下標(biāo)位置 struct Queue { ElemType queue[MaxSize]。 int front, rear。 }。 隊(duì)列的進(jìn)隊(duì)和出隊(duì) ? front = rear =0 時(shí) ,初始化； ? 進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn) 1 rear = rear + 1， 再寫入， rear 指向尾元素 ? 出隊(duì)時(shí)隊(duì)頭指針先進(jìn) 1 front = front + 1， 再刪除， front 指向隊(duì)列頭元素 當(dāng) front＝＝ rear時(shí)，隊(duì)列是什么狀態(tài)呢？ 規(guī)定： 讓 front指向隊(duì)首元素的前一單元的位置。 當(dāng) front＝＝ rear時(shí)，隊(duì)列為空 注意：數(shù)組長(zhǎng)度為 N，隊(duì)列只能使用其中的 N1個(gè)。 假設(shè)數(shù)組長(zhǎng)度為 N，則 （ 1）當(dāng) front＝＝ 0， rear＝＝ N－ 1時(shí)， 隊(duì)滿，入隊(duì)則溢出（真溢出） （ 2）當(dāng) front?。?0， rear＝＝ N－ 1時(shí)， 入隊(duì)也會(huì)溢出（假溢出） 解決方案： （ 1）隊(duì)首固定：每次出隊(duì)后，剩余元素向前移動(dòng)，隊(duì)首元素永遠(yuǎn)在數(shù)組第一個(gè)位置上。 缺點(diǎn)：造成大量數(shù)據(jù)的移動(dòng)，浪費(fèi)時(shí)間 （ 2）循環(huán)隊(duì)列：利用模運(yùn)算 ? 存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。 ? 隊(duì)頭、隊(duì)尾指針加 1時(shí)從 maxSize 1直接進(jìn)到 0，可用語(yǔ)言的取模 (余數(shù) )運(yùn)算實(shí)現(xiàn)。 ? 隊(duì)頭指針進(jìn) 1: front = (front + 1) % MaxSize。 ? 隊(duì)尾指針進(jìn) 1: rear = (rear + 1) % MaxSize。 ? 隊(duì)列初始化： front = rear = 0。 ? 隊(duì)空條件： front == rear。 ? 隊(duì)滿條件： (rear + 1) % MaxSize == front ? 隊(duì)列元素個(gè)數(shù)： (rearfront+Maxsize)%Maxsize ? 插入和刪除的時(shí)間復(fù)雜度為 O（ 1）； 1 2 3 4 5 0 J3 J5 J4 一般情況 1 2 3 4 5 0 J3 J5 J4 J6 J7 J8 隊(duì)滿 1 2 3 4 5 0 隊(duì)空 練習(xí)： 1. 棧和隊(duì)列的共同點(diǎn)是 ______ A. 都實(shí)先進(jìn)后出 B. 都是先進(jìn)先出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn) C 2. 已知一個(gè)棧的進(jìn)棧序列是 1， 2， 3， … ， n，其輸出序列是 p1,p2,…,p n,若 p1=n,則 pi= ______ A. i B. ni C. ni+1 C ，通常需要使用____保存中間結(jié)果 A. 隊(duì)列 B. 棧 C.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1