數(shù)據(jù)結(jié)構(gòu)-第4章-棧和隊列演示課件

1、第4章 棧和隊列 4.1 棧的結(jié)構(gòu)及其運算4.2 隊列的結(jié)構(gòu)及其運算4.3 鏈棧和鏈隊4.4 棧的應(yīng)用舉例4.5 小結(jié)習(xí)題44.1 棧的結(jié)構(gòu)及其運算圖4-1所示為棧的基本結(jié)構(gòu)。 圖4-1 棧的結(jié)構(gòu)棧的基本算法有進棧和出棧兩種。圖4-2給出了在進棧和出棧操作過程中棧頂指針和棧中元素之間的關(guān)系。圖中棧的最大容量是5，(a)圖中Top=0表示?？眨瑮Ｖ袩o其他元素；(b)圖中Top=1，表示棧中有一個元素A；(c)圖表示在(b)圖的基礎(chǔ)上進棧，棧指針加，Top= Top+1，Top=2，棧頂元素是B；(d)圖中Top=5，表示棧已滿，棧中有5個元素，棧頂元素是E；(e)圖表示在(d)圖的基礎(chǔ)上出棧，棧

2、指針減，Top=Top-1，Top=4，此時的棧頂元素換成D。注意，棧指針Top始終指向棧頂元素。圖4-2 棧頂指針和棧中元素的關(guān)系進行進棧和出棧操作時，首先要建立一個棧，設(shè)置棧指針的初態(tài)，測試棧滿和?？铡Ｏ旅娼o出用一維數(shù)組表示棧，進行初態(tài)設(shè)置和測試的方法。(1) 建立棧和設(shè)置初態(tài)。先進行數(shù)組說明，假設(shè)棧中結(jié)點的數(shù)據(jù)類型是字符型(char)。char stack MAXN；int top=0；/* 把棧置成空的初態(tài) */(2) 測試棧空。if (top=0) return (0) /* 棧空，返回0 */(3) 測試棧滿。if (top=MAXN) return(1) /* 棧滿，返回1 */

3、應(yīng)用以上的設(shè)置狀態(tài)和測試手段就可以很方便地建立進棧和出棧的算法。進棧算法進棧的基本操作過程是先將棧頂指針加，然后把新元素裝入棧中。進棧的整個操作過程可描述為：首先測試棧是否滿；若棧滿，則顯示棧已滿，不能裝入，否則新元素進棧。下面給出進棧的算法。 PUSHSTACK(stack , top, in)/* stack為棧，top是棧頂指針，in是進棧新元素 */ if (top=n) printf(棧滿)； else top+；stacktop=in； 出棧算法出棧的基本操作過程是將棧頂指針所指的元素退棧，然后棧指針減。出棧的整個過程可描述為：首先測試棧是否空，若棧為空，則顯示棧已空，不能退棧，否

4、則棧頂元素出棧。下面給出退棧的算法。POPSTACK(stack ，out，top)/* 從棧stack中取出元素給變量out，top是棧頂指針 */ if (top=0) printf(?？?； else out=stacktop； top-； 例有兩個棧分別為Stack1(n)和Stack2(m)，棧頂指針分別為Top1和Top2，設(shè)計一個算法，使得從Stack中逐個退棧，又依次裝入到Stack2中，直至退棧結(jié)束。分析在設(shè)計該算法時，Stack1退棧時要不斷地測試棧指針Top1是否為0，判斷Stack1棧是否空；同時也要不斷測試Stack2棧在進棧時Top2是否為m，判斷棧是否滿。然后再進

5、行出棧和進棧的操作，注意可能會出現(xiàn)當Stack1棧中的元素還未退棧完，而Stack2已滿的情況，此時應(yīng)停止該算法的執(zhí)行。圖4-3給出了該算法的框圖。圖4-3 退棧和進棧同時進行的框圖下面給出相應(yīng)的算法。POPPUSHSTACK (stack1 ，stack2 ，top1，top2)/* stack1為退棧，stack2為進棧，top1和top2為棧頂指針 */while(top1！=0)/* 判stack1棧是否空 */ if (top2=m) printf(stack2棧滿)；return; else top2+；/* 棧指針進棧操作 */stack2top2=stack1top1；top1

6、-；/* 棧指針退棧操作 */ 在程序設(shè)計中，棧最常見的應(yīng)用是子程序的調(diào)用。假設(shè)有一主程序，在執(zhí)行中要連續(xù)嵌套調(diào)用三個子程序，其嵌套調(diào)用的情況如圖4-4所示。 圖4-4 子程序嵌套調(diào)用4.2 隊列的結(jié)構(gòu)及其運算圖4-5(a)所示隊列中有a1，a2，ai，an共n個元素，進隊時這些元素由a1到an依次從隊尾進入，出隊時也只能由a1到an依次從隊首退出。 圖4-5 隊列的結(jié)構(gòu)同樣，隊列也存在隊滿不能進隊，隊空不能出隊的問題。圖4-6就說明了隊列中元素進隊和出隊分別與隊尾指針(實際上是進隊指針)和隊首指針(實際上是出隊指針)的關(guān)系。圖4-6表現(xiàn)總長度是5的隊，初態(tài)(a)圖所示為R=F=0，同時表示隊

7、空；(b)圖中依次有、B、C三個元素進隊，沒有出隊，因此隊首指針F=0，隊尾指針R=3；在(c)圖中兩個元素A和B已經(jīng)出隊，而沒有元素進隊，因此隊首指針F=2，隊尾指針R=3(注意：出隊的隊首指針總是指向當前隊首元素的前一個位置)；(d)圖表示在(c)圖的基礎(chǔ)上又有一個元素C出隊，這時R=F=3，顯然隊已經(jīng)空了；(e)圖表示隊中只有兩個元素D和E，但隊尾指針R=5，說明隊滿，已不能進隊。圖4-6 隊列指針的動態(tài)變化隊列的基本算法主要是進隊和出隊。設(shè)有隊列Queue(n)，F(xiàn)為隊首指針，R為隊尾指針。下面給出隊列設(shè)置初態(tài)和測試隊空、隊滿的方法。(1) 設(shè)置隊列指針初態(tài)。F=0，R=0(2) 測試

8、隊空。if (F=R) return(0)/* 隊空，返回0 */(3) 測試隊滿。if(R=n) return(1) /* 隊滿，返回1 */根據(jù)以上給出的隊列設(shè)置和測試的手段，就能夠較容易地建立進隊和出隊的算法。下面給出語言中有關(guān)隊列的類型說明：char Queue MAXN；int F=0，R=0；進隊算法根據(jù)隊列的結(jié)構(gòu)，若隊尾指針不在隊的最大長度上，則首先隊尾指針加，元素進隊，否則就是隊滿，無法進隊。ADDQUEUE(queue，r，f，in)/* 在queue隊列中進一個元素in，f和r分別是隊首和隊尾的標志 */ if(r=n) printf(隊滿); else r+; queue

9、r=in; 出隊算法出隊首先要判斷隊列中是否有元素，即R是否等于F，R=F可能出現(xiàn)在初態(tài)，也可能出現(xiàn)在出隊、進隊的動態(tài)變化中。DELQUEUE(queue，r, f, out)/* 在queue隊列中退出一個元素到out，f和r分別是隊首和隊尾的標志 */ if(f=r) printf(隊空); else out=queue+f;圖4-7表示了循環(huán)隊列的結(jié)構(gòu)和進隊、出隊指針的動態(tài)變化。在圖4-7(a)中，R=F時說明隊列為空；(b)圖說明隊滿時始終還存在一個空單元，即當出隊指針R+1=F時為隊滿；(c)圖是通常情況下避免假溢出的情況。圖4-7 循環(huán)隊列結(jié)構(gòu)和指針下面是在循環(huán)隊列中設(shè)置初態(tài)和判斷

10、隊滿、隊空的方法。(1) 設(shè)置初態(tài)。R=1，F(xiàn)=1(2) 進隊判斷是否隊滿。if (R=n) R=1else R=R+1if (R=F) return(1) /* 隊滿，返回1 */(3) 出隊判斷是否隊空。if (R=F) return(0) /* 隊空，返回0 */下面給出循環(huán)隊列的進隊算法。ADDCQUEUE(queue，r，f，in)/* queue為循環(huán)隊列，f和r分別是隊首和隊尾標志，in是進隊元素 */ if(r=n) r=1； else r+； if(r=f) printf(隊滿)； r-； else queuer=in；在循環(huán)隊列的進隊算法中，若判斷為隊滿，則為了使該算法能在

11、不改變原隊列的情況下(即原隊列仍為隊滿)能繼續(xù)判斷當前的隊已滿，進隊指針R要退1個單元，在后退時也仍要注意假溢出的問題，解決的方法是：if(R=1) R=n；else R=R-1；下面是循環(huán)隊列的出隊算法。DELCQUEUE(queue，r，f，out)/* 在循環(huán)隊列queue中退出一個元素到out，f和r分別是隊首和隊尾的標志 */ if(f=r) printf(隊空)； else if(f=n) f=1; else f+； out=queuef； 循環(huán)隊列的存儲區(qū)也可以表示為從0n-1，即Queue(n-1)，其結(jié)構(gòu)和指針表示與前面所討論的循環(huán)隊列相同。由于我們把隊列表示為Queue(n

12、-1)，因此可以方便地使用計算余數(shù)的數(shù)模運算來代替隊列假溢出而形成算法中的判斷語句，進隊指針改為R=(R+1)mod n出隊指針改為F=(F+1)mod n這樣在循環(huán)隊列中，進隊的算法為ADDQUEUE(queue，r，f，in)/* 在循環(huán)隊列queue中進一個元素in */ r=(r+1 )%n； if( r=f) printf(隊滿)； else queuer=in；在循環(huán)隊列中出隊的算法為DELQUEUE(queue，r，f，out)/* 在循環(huán)隊列queue中退出一個元素送out */ if(f=r) printf(隊空)； else f=(f+1)%n； out=queuef； 例

13、設(shè)有一個有序線性表A(n)和循環(huán)隊列Q(m)，設(shè)計一個算法，使得在線性表中比關(guān)鍵字KEY大的數(shù)據(jù)送到循環(huán)隊列中。設(shè)隊列Q中的邏輯地址為1m，F(xiàn)為隊首指針，R為隊尾指針。分析由于線性表A是有序的，因此只需確定在線性表A中比KEY大的值的序號i(地址)，然后從i開始直到n逐個地把線性表中的數(shù)據(jù)送入循環(huán)隊列。當然，下面的情況也應(yīng)考慮在內(nèi)：若線性表A所有的值均比KEY小，則不必把數(shù)據(jù)送入隊列；也有可能在進隊過程中，循環(huán)隊列的存儲空間不夠(隊滿)，產(chǎn)生溢出而出錯，最后還要修正線性表的表長。圖4-8給出了算法的流程框圖。算法描述如下：LIST_QUEUE(a，q，r，f，key)/* 在有序線性表a1:n

14、中把比關(guān)鍵字值key大的數(shù)值送到循環(huán)隊列q1:m中，其中r和f分別 是隊首指針和隊尾指針 */ for(i=1; ikey)break;/* 在線性表中找比key值大的值的位置 */if(i=n) k=n;/* 防止線性表的總長度n變化 */ while(idata; 在C語言中，鏈棧進棧的算法可描述如下：struct node int data； struct node *next；ADDS(struct node *htop，int in) struct node *p； p=(struct node *)malloc(sizeof(struct node)； p-data=in； p-n

15、ext=htop； htop=p；在進棧算法中，裝入結(jié)點使其成為棧頂元素的操作語句x-next=Htop具有兩種含義： (1) 當鏈棧為空時，按常規(guī)步驟為x-next=NULL。由于鏈棧為空時，Htop=NULL，因此x-next=Htop包含當?？諘r進棧的操作，即?？諘r，建立鏈棧入口且第一個結(jié)點的鏈指針為NULL。(2) 當鏈棧非空時，操作性質(zhì)與鏈表插入在鏈首的運算相同。退棧的算法與利用空間表取一個結(jié)點的算法是很接近的，所不同的是進行退棧操作時，鏈棧的第一個元素退出棧后，還必須取出該結(jié)點的數(shù)據(jù)。以下給出鏈棧退棧的算法。 DELS(htop，out)/* 從htop為入口的鏈棧中退出第一個結(jié)點

16、，數(shù)值域內(nèi)容送out */ if(htop=NULL) printf(?？?； else x=htop；/* 取鏈棧第一個結(jié)點地址x */out=x-data；/* 讀出棧頂元素數(shù)據(jù) */ htop=x-next；/* 建立新的鏈棧入口 */free(x)；/* 被刪除結(jié)點x送空間表 */ 4.3.2 鏈隊的存儲結(jié)構(gòu)及其運算我們曾經(jīng)討論了隊列的存儲結(jié)構(gòu)以及非循環(huán)隊列的假溢出問題，即便循環(huán)隊列設(shè)計得很巧妙，但若其長度達到隊列的總長度，就不能再進隊?，F(xiàn)在用鏈結(jié)構(gòu)的指針形式就能較好地解決隊列的假溢出和長度飽和問題。圖4-10給出了鏈隊的邏輯狀態(tài)和存儲結(jié)構(gòu)。其中，F(xiàn)ront和Rear是兩個指針型變量，

17、分別指示隊列中實際的隊首(退隊指針)和隊尾(進隊指針)的位置。 圖4-10 鏈隊的存儲結(jié)構(gòu)當隊空時，F(xiàn)ront=NULL；Rear=NULL；所謂隊滿，是指在可利用的空間表中，所有的結(jié)點被取完，即AV=NULL時，才表示隊滿。根據(jù)隊列的操作特點，進隊和退隊分別在表的兩端進行，具體表現(xiàn)為“先進先出”。從鏈隊的結(jié)構(gòu)可看出，進隊的基本操作步驟為(設(shè)進隊結(jié)點的地址為x)：Rear-next=x；x-next=NULL；Rear=x；其中第一個語句的含義是隊尾指針(進隊指針)指向的結(jié)點與插入結(jié)點鏈接；第二句表示當前的進隊結(jié)點形成新的隊尾，即尾端的新結(jié)點x的指針設(shè)置為空；第三句形成新的鏈尾指針。在考慮了取

18、新結(jié)點過程和隊空的邊界條件處理后，就得出了如下鏈隊進隊的算法。ADDQ(front，rear，in)/* 數(shù)據(jù)值in的結(jié)點進入鏈隊 */ x=malloc(size) x-data=in; x-next=NULL;/* 建立隊尾的標志 */ if (front=NULL) front=x； rear=x； /* 隊空進隊，建立進隊和退隊指針 */ else rear-next=x； rear=x； 在進隊的算法中，判斷隊列為空，其標志是Front=Rear=NULL，根據(jù)鏈隊的結(jié)構(gòu)，在鏈空時第一個結(jié)點進隊，必須同時建立進隊和退隊的指針，使得退隊指針Front和進隊指針Rear都指向進隊的第一個

19、結(jié)點。以下給出退隊的算法。DELQ(front，out)/* 從隊列q中，退出一個結(jié)點，把數(shù)據(jù)值送out */ if (front=NULL) printf(隊空)； else x=front； front=x-next； out= x-data； free(x)； if(front=NULL) rear=NULL；4.4 棧的應(yīng)用舉例 如何處理計算表達式是程序設(shè)計語言中的一個基本問題。對于一個含有表達式的賦值語句，必須將其翻譯成計算機能執(zhí)行的機器語言，首先應(yīng)正確地解釋表達式及其計算過程，例如，對于賦值語句x=4+8*2-3其正確的計算結(jié)果應(yīng)是17。但是，若計算機系統(tǒng)程序在把表達式的計算轉(zhuǎn)換成

20、機器能執(zhí)行的機器語言時，是從左到右，不作約束或規(guī)定地進行通常的掃描計算，則結(jié)果為x=4+8*2-3=12*2-3=24-3=21 顯然，按四則運算的法則，其計算的結(jié)果是錯誤的。因此，為了使編譯程序能正確地按計算順序進行，在編譯程序中表達式的運算次序是用運算符的優(yōu)先級來確定的。假設(shè)運算符的優(yōu)先級如下：運算符*/*+-；優(yōu)先級 32 211 0我們規(guī)定，優(yōu)先級高的運算符先計算；優(yōu)先級相同的運算符，遵循從左至右的順序運算，“；”表示表達式的結(jié)束符，優(yōu)先級最小為零。有了以上的規(guī)則，對表達式從左到右進行掃描計算時，其計算順序就能被惟一確定下來。例如，表達式A+B/C*D-E*F的運算順序如圖4-11所示

21、。圖4-11 表達式的運算順序編譯程序?qū)Ρ磉_式進行編譯時，需設(shè)置兩個棧，用于存放運算符的棧稱作運算符棧，簡稱OPS；另一個存放操作數(shù)的棧稱作操作數(shù)棧，簡稱OVS。當編譯程序自左向右對表達式進行掃描時，有如下處理規(guī)則。1操作數(shù)操作數(shù)一律進入操作數(shù)棧OVS。2運算符(1) 若運算符棧空，運算符進入運算符棧OPS。(2) 若運算符棧非空，則將該運算符的優(yōu)先級與運算符棧OPS中的棧頂元素的優(yōu)先級相比較。若該運算符的優(yōu)先級大，則該運算符進OPS棧；反之，則取出OPS棧頂?shù)倪\算符，并在操作數(shù)棧OVS中連續(xù)取出兩個棧頂元素(操作數(shù))，與取出的運算符相運算，并將結(jié)果再存入操作數(shù)棧OVS。(3) 進行第(2)步

22、操作后的運算符再與運算符棧的棧頂元素的優(yōu)先級比較。重復(fù)(2)步的操作，直至當前掃描到的運算符進OPS棧為止。3結(jié)束符“；”按運算的規(guī)則進行運算，OPS取一個運算符，OVS取出二操作數(shù)，重復(fù)進行直至運算符棧OPS空為止。對表達式A+B/C*D-E*F進行從左到右的掃描，當掃描到“+”、“/”、“*”時，由于運算符的優(yōu)先級后者比前者大，都逐個進棧。這時，操作數(shù)棧OVS和運算符棧OPS的狀態(tài)如圖4-12(a)所示。當掃描到“-”時，因“-”的優(yōu)先級比OPS棧頂元素運算符“*”的優(yōu)先級低，因此，OPS棧頂運算符“*”退棧；同時，從操作數(shù)棧OVS中連續(xù)退出兩個元素D和C，進行運算C*DT，T作為運算的中

23、間結(jié)果，成為下一步運算的操作數(shù)，繼續(xù)進操作數(shù)棧OVS。T進棧后，操作數(shù)棧OVS和運算符棧OPS的狀態(tài)如圖4-12(b)所示。 當前掃描的運算符“-”仍然比OPS棧頂元素運算符“/”的優(yōu)先級低，運算符棧OPS棧頂元素“/”繼續(xù)出棧，而且操作數(shù)棧OVS中也連續(xù)再退出兩個元素T和B，進行運算B/TT，T作為運算的中間結(jié)果，成為下一步運算的操作數(shù)，繼續(xù)進操作數(shù)棧OVS。T進棧后，OVS棧和OPS棧的狀態(tài)如圖4-12(c)所示。這時，當前掃描的運算符“-”還未進運算符棧OPS，而且“-”還要與OPS棧頂?shù)脑剡\算符“+”比較，由于優(yōu)先級相同，根據(jù)同優(yōu)先級運算自左到右的原則，“+”仍然從運算符棧OPS退棧

24、，在操作數(shù)棧OVS中再連續(xù)退出兩個元素T和A，進行運算A+TT，T作為運算的又一個中間結(jié)果，成為下一步的操作數(shù)而進棧OVS，T進棧后，這時運算符棧OPS為空，“-”才能進棧OPS。掃描繼續(xù)進行，形成E、F進棧OVS，“*”進棧OPS。這時棧OVS和OPS的狀態(tài)如圖4-12(d)所示。 圖4-12 表達式運算中棧的狀態(tài)變化4.5 小結(jié) 棧和隊列是兩種特殊的線性表，從邏輯結(jié)構(gòu)上分析，其數(shù)據(jù)元素仍然是順序存儲的，數(shù)據(jù)在存儲空間的存放地址也是連續(xù)的。棧的結(jié)構(gòu)特點是先進后出，數(shù)據(jù)元素只能在表的一端進行插入和刪除。棧指針Top始終指向棧頂元素在棧中的序號。棧的基本算法有進棧和出棧兩種，在算法實現(xiàn)中必須注意

25、棧滿(上溢)和棧空(下溢)的判斷。隊列是數(shù)據(jù)元素在表的一端插入，在表的另一端刪除的特殊線性表。隊列的結(jié)構(gòu)特點是先進先出。隊列有隊首指針(也稱作退隊指針)和隊尾指針(也稱作進隊指針)。隊列的基本算法也有進隊和出隊兩種，在算法中也要注意隊滿和隊空的判斷。為了解決隊列中的假溢出問題，循環(huán)隊列是一種有效的隊列結(jié)構(gòu)形式，隊列中存儲單元首尾相接的結(jié)構(gòu)特征能充分利用隊列中的存儲空間。注意，在循環(huán)隊列中，隊滿時始終存在一個空單元。在有序線性表的插入和刪除算法中，算法執(zhí)行在時間上的量級是線性階O(n)。棧和隊列的基本操作算法的時間執(zhí)行量級是常階數(shù)O(1)。鏈棧和鏈隊是單鏈表的一種特殊形式，它們具有鏈表的存儲結(jié)構(gòu)

26、的特征，也有棧和隊列操作上的各自特點。 鏈棧的進棧和退棧的運算都在首部進行，只需調(diào)整鏈棧的入口Htop的入口地址；鏈隊具有進隊指針Rear和退隊指針Front，進隊時調(diào)整進隊指針Rear的入口地址，退隊時調(diào)整Front的退隊指針。同時，應(yīng)該注意?？?、隊空時的判斷。習(xí)題4什么是棧和隊列-試比較兩者在結(jié)構(gòu)上有什么不同。設(shè)在如圖4-13所示的鐵路調(diào)度站中，右邊軌道上排列有編號為1、2、3的三節(jié)車廂，每節(jié)車廂可以被帶進站并可以在任意時候被拖走，例如，若將1、2、3依次帶進后且依次帶出，則在左邊軌道上產(chǎn)生新的排列3、2、1。試問：在左邊軌道上將可能出現(xiàn)多少種新的排列法-圖4-13 題圖4.3 設(shè)有棧Stack(n)，棧指針為Top；有一線性表A(m)，最大長度為k。試編寫一個算法，使得棧頂元素出棧，并將元素轉(zhuǎn)入到線性表中。設(shè)有兩個棧共享同一存儲空間V