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