【導讀】棧和隊列結構的特點。棧是允許在同一端進行插入。和刪除操作的特殊線性表。為棧底；棧底固定，棧中元素個數(shù)為零時稱為空。棧結構也稱為后進先出表。棧上溢?？臻g是有限的，若棧已滿，在進行入棧操作時，就要產生上溢。棧頂元素所在的位置。同順序表一樣，可利用一維數(shù)組來實現(xiàn)。有三個元素的進棧序列是1，2，3。寫出可能的出棧序列。Empty判定棧是否為空；elsecout<<"堆棧初始化長度錯誤";棧頂指針top上移(加1)；棧下溢信息，并停止執(zhí)行；否則，–step3棧頂指針top下移(減1)。多棧共享是充分利用?？臻g的一種策略。置動態(tài)移動，兩個棧之間的分界線是不定的。多的棧就難于表達了。這時，就需要采用鏈。t為申請的結點,為NULL表示失敗。示鏈滿;否則,執(zhí)行step2;

　　

【正文】 停止放映 [第 55頁 /68頁 ] 鏈隊列 —隊列鏈式存儲 鏈隊列實質上就是只能在頭部刪除元素、只能在尾部插入元素的單鏈表。 隊頭指針 front就是單鏈表的頭指針，隊尾指針 rear則是指向單鏈表最后一個結點的指針。 Q a1 an ∧ front rear 非空鏈隊列 Q ∧ front rear 空鏈隊列 下一頁 上一頁 停止放映 [第 56頁 /68頁 ] 鏈隊列為滿的條件 鏈滿的條件為 : T = NULL T為新創(chuàng)建的結點 ,當沒有存儲空間時 ,T為 NULL,表示鏈隊列已滿。 下一頁 上一頁 停止放映 [第 57頁 /68頁 ] 鏈隊列結點可定義： struct QNode { ElemType data。 struct QNode *next。 }。 另外 ， 鏈隊列有兩個指針 ， 可以分別定義 ， 也可采用下面定義 。 struct LinkQueue { QNode *front。 // 隊頭指針 QNode *rear。 // 隊尾指針 }。 data next 數(shù)據(jù)域 指針域 下一頁 上一頁 停止放映 [第 58頁 /68頁 ] （ 1） 鏈隊列初始化 建立一個含有頭結點的空的鏈隊列 。 void InitQueue(LinkQueue amp。Q) { = new QNode。 //建立頭結點 next=NULL。 = 。 //尾指針指向頭結點 } 下一頁 上一頁 停止放映 [第 59頁 /68頁 ] （ 2） 求隊列的長度 返回隊列的元素個數(shù) ， 即隊列的長度 。 int QueueLength(LinkQueue amp。Q) { QNode *p=。 int len=0。 while(p!=){ len++。 p= pnext。 } return len。 } 下一頁 上一頁 停止放映 [第 60頁 /68頁 ] （ 3）入隊列操作 算法描述 : step1 申請建立一個新結點 T。 step2 判別 T是否為空 。若空 ,表示 隊列已滿 。 step3 非空 ,將 T插入鏈中 ,修改 rear指針。 下一頁 上一頁 停止放映 [第 61頁 /68頁 ] 鏈隊列的入隊操作 插入元素 x為隊列新的隊尾元素。 void EnQueue(LinkQueue amp。Q, ElemType x) { QNode *s=new QNode。 //建立新結點 s if（ s == NULL） cout“ 內存無可用空間 ” 。 else { sdata = x。 snext =NULL。 next = s。 //在隊尾插入結點 s = s。 //修改隊尾指針 } } 下一頁 上一頁 停止放映 [第 62頁 /68頁 ] （ 4）出隊列操作 算法描述 : step1 判別隊列是否為空 。若空 ,則顯示 隊列 ‘ 下溢 ’ 。 step2 非空 ,則判別隊長度是否為 1。 不為 1,修改頭指針 。 為 1,則修改頭、尾指針； step3 釋放 P。 下一頁 上一頁 停止放映 [第 63頁 /68頁 ] 出隊操作要考慮兩種情況 當隊列長度大于 1時 ,只修改隊頭指針即可。 an ^ front rear Queue Queue front rear ^ an ^ P ... Queue Queue front rear rear front a1 an ^ a1 a2 a2 ^ ... an ^ 當隊列長度為 1時 ,除了修改隊頭指針外 ,還要修改隊尾指針。 下一頁 上一頁 停止放映 [第 64頁 /68頁 ] 鏈隊列的出隊操作 若隊列不空 ， 則刪除隊頭元素 ， 用 e返回其值 。 void DeQueue (LinkQueue amp。Q, ElemType amp。e) { QNode *p。 if(==) cout隊列已空 。 else { p= next。 e=pdata。 next=pnext。 if(==p) =。 delete p。 } } 下一頁 上一頁 停止放映 [第 65頁 /68頁 ] （ 5） 取隊頭元素 若隊列不空 ， 則用 e返回隊頭元素； void GetHead(LinkQueue amp。Q, ElemType amp。e) { QNode *p。 if(==) cout隊列已空 。 else { p= next。 e=pdata。 } } 下一頁 上一頁 停止放映 [第 66頁 /68頁 ] 求 k階斐波那切數(shù)列某一項 k階斐波那切數(shù)列 {ai}定義如下： 解決方法 : 建立一個容量為 k的循環(huán)隊列，將前 k個元素依次入隊。然后計算第 k+1個元素，它等于隊列中全部元素之和。而后將隊頭元素出隊，將第 k+1個元素入隊。重復上述過程，就可求得任意指定項元素的值。 下一頁 上一頁 停止放映 [第 67頁 /68頁 ] 【 例 24】 利用循環(huán)隊列求 k階斐波那切數(shù)列某一式的值。 i = 0 1 2 3 4 5 6 7 8 9 10 11 ai = 0 0 1 1 ai = 0 1 1 2 i = 4 ai = 1 1 2 4 i = 5 ai = 1 2 4 7 i = 6 ai = 2 4 7 13 i = 7 ai = 4 7 13 24 i = 8 ai = 7 13 24 44 i = 9 ai = 13 24 44 81 i = 10 ai = 24 44 81 149 i = 11 下一頁 上一頁 停止放映 [第 68頁 /68頁 ] 思考題 1)假設一單循環(huán)鏈表的長度大于 1，且表中即無頭結點也無頭指針。已知 S為指向鏈表中某結點的指針。試寫出刪除表中結點 S 的算法。 1)假設以數(shù)組 sequ[m1]存放循環(huán)隊列的元素，設變量 rear和 quelen分別為指示隊尾元素位置和隊中元素個數(shù)，試寫出入隊和出隊算法。