第三章棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1棧（stack）棧的定義和特點定義：限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)數據結構—棧和隊列全文共48頁，當前為第1頁。棧的存儲結構順序棧實現：一維數組s[M]top=0123450棧空棧頂指針top,指向實際棧頂后的空位置，初值為0top123450進棧Atop出棧棧滿BCDEF設數組維數為Mtop=0,棧空，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空數據結構—棧和隊列全文共48頁，當前為第2頁。入棧算法0M-1棧1底棧1頂棧2底棧2頂出棧算法在一個程序中同時使用兩個棧typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;順序棧的定義數據結構—棧和隊列全文共48頁，當前為第3頁。鏈棧棧頂^…...topdatalink棧底結點定義入棧算法出棧算法typedefstructnode{intdata;structnode*link;}JD;^…...棧底toptopxptop^…...棧底topq數據結構—棧和隊列全文共48頁，當前為第4頁。棧的應用過程的嵌套調用r主程序srrrs子過程1rst子過程2rst子過程3數據結構—棧和隊列全文共48頁，當前為第5頁。例遞歸的執行情況分析遞歸過程及其實現遞歸：函數直接或間接的調用自身叫~實現：建立遞歸工作棧voidprint(intw){inti;if(w!=0){print(w-1);

for(i=1;i<=w;++i)printf(“%3d”,w);

printf("\n");}}Ch3_10.c運行結果：1，2，2，3，3，3

，數據結構—棧和隊列全文共48頁，當前為第6頁。遞歸調用執行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2,(2)2(1)3top(4)輸出:1,(3)1(2)2(1)3top(2)輸出：3,3,3,(1)3top返回(3)1(2)2(1)3top(4)0結束(1)數據結構—棧和隊列全文共48頁，當前為第7頁。TowerofHanoi問題問題描述：有A,B,C三個塔座，A上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號1,2,3……n。要求將n個圓盤從A移到C，疊放順序不變，移動過程中遵循下列原則：每次只能移一個圓盤圓盤可在三個塔座上任意移動任何時刻，每個塔座上不能將大盤壓到小盤上解決方法：n=1時，直接把圓盤從A移到Cn>1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉化成只有一個圓盤的Hanoi問題算法：執行情況：遞歸工作棧保存內容：形參n,x,y,z和返回地址返回地址用行編號表示nxyz返回地址數據結構—棧和隊列全文共48頁，當前為第8頁。main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6數據結構—棧和隊列全文共48頁，當前為第9頁。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6數據結構—棧和隊列全文共48頁，當前為第10頁。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0數據結構—棧和隊列全文共48頁，當前為第11頁。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0棧空3ABC02BAC8Hanoi.cD:\fengyi\bkc\power\power.c數據結構—棧和隊列全文共48頁，當前為第12頁。回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較若不等，非回文若直到棧空都相等，回文多進制輸出：字符串：“madamimadam”例把十進制數159轉換成八進制數(159)10=(237)81598198280237余7余3余2toptop7top73top732數據結構—棧和隊列全文共48頁，當前為第13頁。表達式求值

中綴表達式后綴表達式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中綴表達式：操作數棧和運算符棧例計算2+4-3*6操作數運算符24+操作數運算符6-操作數運算符6-36*操作數運算符6-18操作數運算符12數據結構—棧和隊列全文共48頁，當前為第14頁。后綴表達式求值步驟：1、讀入表達式一個字符2、若是操作數，壓入棧，轉43、若是運算符，從棧中彈出2個數，將運算結果再壓入棧4、若表達式輸入完畢，棧頂即表達式值；若表達式未輸入完，轉1top4top43top735top例計算4+3*5后綴表達式：435*+top415top19數據結構—棧和隊列全文共48頁，當前為第15頁。(1)(2)(4)(5)(6)(7)(3)地圖四染色問題R[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#

紫色

2#黃色3#

紅色4#

綠色數據結構—棧和隊列全文共48頁，當前為第16頁。3.2隊列隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)——允許插入的一端隊頭(front)——允許刪除的一端隊列特點：先進先出(FIFO)a1a2a3…….an入隊出隊frontrear隊列Q=(a1,a2,……,an)雙端隊列a1a2a3…….an端1端2入隊出隊入隊出隊數據結構—棧和隊列全文共48頁，當前為第17頁。鏈隊列結點定義typedefstructnode{intdata;structnode*link;}JD;頭結點^…...front隊頭隊尾rear設隊首、隊尾指針front和rear,front指向頭結點，rear指向隊尾數據結構—棧和隊列全文共48頁，當前為第18頁。frontrearx入隊^xfrontreary入隊x^yfrontrearx出隊x^yfrontrear空隊^frontreary出隊^數據結構—棧和隊列全文共48頁，當前為第19頁。入隊算法出隊算法數據結構—棧和隊列全文共48頁，當前為第20頁。隊列的順序存儲結構實現：用一維數組實現sq[M]front=-1rear=-1123450隊空123450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=-1空隊列條件：front==rear入隊列：sq[++rear]=x;出隊列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront數據結構—棧和隊列全文共48頁，當前為第21頁。存在問題設數組維數為M，則：當front=-1,rear=M-1時，再有元素入隊發生溢出——真溢出當front-1,rear=M-1時，再有元素入隊發生溢出——假溢出解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環隊列基本思想：把隊列設想成環形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實現：利用“模”運算入隊：rear=(rear+1)%M;sq[rear]=x;出隊：front=(front+1)%M;x=sq[front];隊滿、隊空判定條件數據結構—棧和隊列全文共48頁，當前為第22頁。012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態J4,J5,J6出隊J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設一個標志以區別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==front數據結構—棧和隊列全文共48頁，當前為第23頁。入隊算法：出隊算法：數據結構—棧和隊列全文共48頁，當前為第24頁。隊列應用舉例劃分子集問題問題描述：已知集合A={a1,a2,……an}，及集合上的關系R={(ai,aj)|ai,ajA,ij}，其中(ai,aj)表示ai與aj間存在沖突關系。要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均無沖突關系，同時要求分子集個數盡可能少例A={1,2,3,4,5,6,7,8,9}R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}

可行的子集劃分為：

A1={1,3,4,8}A2={2,7}A3={5}A4={6,9}數據結構—棧和隊列全文共48頁，當前為第25頁。算法思想：利用循環篩選。從第一個元素開始，凡與第一個元素無沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進組所用數據結構沖突關系矩陣r[i][j]=1,i,j有沖突r[i][j]=0,i,j無沖突循環隊列cq[n]數組result[n]存放每個元素分組號工作數組newr[n]數據結構—棧和隊列全文共48頁，當前為第26頁。工作過程初始狀態：A中元素放于cq中，result和newr數組清零，組號group=1第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應位置，這樣，凡與第一個元素有沖突的元素在newr中對應位置處均為“1”,下一個元素出隊若其在newr中對應位置為“1”，有沖突，重新插入cq隊尾，參加下一次分組若其在newr中對應位置為“0”,無沖突，可劃歸本組；再將r矩陣中該元素對應行中的“1”拷入newr中如此反復，直到9個元素依次出隊，由newr中為“0”的單元對應的元素構成第1組,將組號group值“1”寫入result對應單元中令group=2,newr清零，對cq中元素重復上述操作，直到cq中front==rear,即隊空，運算結束數據結構—棧和隊列全文共48頁，當前為第27頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=123456789012345678cqfr000000000012345678newr000000000012345678result初始R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第28頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=23456789012345678cqfr010000000012345678newr100000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第29頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

23456789012345678cqfr010000000012345678newr100000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第30頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2456789012345678cqfr010001

100012345678newr101000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第31頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

256789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第32頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

56789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第33頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第34頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第35頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

79012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第36頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

7

9012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第37頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=5

6

7

9012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第38頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=6

7

95012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第39頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

7

956012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第40頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

956012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第41頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

569012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第42頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

69012345678cqfr010101

101012345678newr1

2

1

1

302

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}數據結構—棧和隊列全文共48頁，當前為第43頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

96012345678cqfr010101

101012345678newr1

2

1

1

302

1001234567