第三章棧和隊受限數(shù)據(jù)結(jié)構(gòu)----和刪除受限制的線性表都屬于和刪除受限制的線性表定義和術(shù)棧：限定在表尾作、刪除操作的線性表(a1,a2,,...，an）←元素(進棧 (棧底 (棧頂出棧(pop)進棧棧頂

進棧：一個元素到棧中出棧：從棧刪除一個元素棧頂：允許、刪除元素的一端(表尾)棧底(bottom)棧頂元素：處在棧頂位置的元素棧底：表中不允許、刪除元素的一端空棧：不含元素的棧棧的示意

棧的元素的進出“后進先出”,“LastInFirstOut”棧的別名:“后進先出”表、“LIFO”表、反 Initstack(ssPush(s,ee進棧s若s若不能解決溢出，重新分配空間失敗，則失敗Pop(s,es的頂元素，并送入eGettop(s,es的頂元素拷貝到e若sEmpty(ss輸出

輸入出棧進棧出棧進棧

調(diào)度站(棧AB ABA

CBC

(6)C出 CBBAAA(3)CABA ABA

AABA AABAA

B

ACA ACA(4)C進 (5)C出 ABCABABCAB

A,B,C

元素是A,而A不能先于B出棧,所以不能在輸出序列中,使A成為CA,B,C產(chǎn)生輸出C,A,B一般地，輸入序列(...,ai,...,aj,...,ak,... (1) (1) 輸A,B,C,D

A,B,C,D輸 (7)B,A,C,D(13)C,A,B,D(19) (8)B,A,D,C(14)C,A,D,B(20) (9)B,C,A,D(15)C,B,A,D(21)A,C,D,B(10)B,C,D,A(16)C,B,D,A(22)A,D,B,C(11)B,D,A,C(17)C,D,A,B(23)A,D,C,B(12)B,D,C,A(18)C,D,B,A(24) 共5+5+3+1=14棧的表示和操作實順序棧：用順序空間表示的棧。如何分配空序maxleng-

作。結(jié)束時top指向新棧頂top棧頂指

n-…10

棧棧底toptop>=0頂元素

top

序

序1 棧

10top→-top==maxleng-1若元出

序maxleng-…

… 指向下一空位置，完成進棧 作。結(jié)束時top正好指向新 頂元素所在位置上的一空位置top棧頂指

…0

棧棧 向去掉原棧頂元素后的新棧top>=1=s[top-

top

序

序1 棧

1top→若元素,將發(fā)生“溢出

順序棧的描**top是棧頂標(biāo)志，根據(jù)約定由top靜態(tài)分typedef{ElemTypeelem[maxleng]；//棧元素空間inttop； sqstacks； s.top---頂指針；s.elem[s.top-1]動態(tài)分#defineSTACK_INIT_SIZE#define typedef{ElemType*base； inttop； int //相當(dāng)于}SqStack； //SqStack為結(jié)構(gòu)類型SqStacks； s.top--頂指針；s.base[s.top-1]順序棧算初始化棧(動態(tài)分配voidInitStack(SqStack{S.base=(ElemTypeS.stacksize=}void{SqStackS1,S2;S2.base=(ElemTypeS2.stacksize=}進棧算intpush(SqStack&S,ElemType if {newbase=(ElemTypeif(!newbase){returnERROR;}} returnOK;}(3棧算intpop(SqStack{ifreturn x= return }}{ ElemTypee;if if{退棧成功，處理e的值s}else{退棧失敗，提示錯誤信息}}4.使用不帶表頭結(jié)點的單鏈structnode{ElemTypedata； structnode*next；//next為指針類型

data^^棧 棧

dataan-^an-^棧 棧優(yōu)點：進出棧時間為常數(shù)鏈?zhǔn)綏５倪M棧

棧pe^棧pe^p=(structnode*)malloc(sizeof(structnode));進棧算法structnode*push_link(structnode*top,Elemtype{structnodeintleng=sizeof(structnodep=(structnode*)malloc(leng)；//生成新結(jié)點 //topreturn }an-an-^ 棧新棧退棧算structnode*pop(structnode*top,Elemtype{structnodeif(top==NULL)returnNULL; (*e)=p- //取出原棧的頂元素送 return //返回新的棧頂指針}棧的應(yīng)用舉棧的基本用途----保存暫時不用的數(shù)或地址數(shù)制轉(zhuǎn)404N=1348,轉(zhuǎn)換為八進404 n1=1348/8=168//求商 依次退棧,得

4進棧20進50425042504(35進棧42進判定表達式中的刮號匹[...{...()...(例.{...[}...] (1)(2)(3)(4)

({((1)“(”進 (2)“{”進({({{({{{({((3)“{”進 (4)“{”退{({((5)“]”與“{”不匹表達式求①例：4+2*3–10/(7–5①③③ 11+-* >#+>><<<>>->><<<>>*>>>><>>/>>>><>>（<<<<<=>>>>>>>#<<<<<= 算法思想 從表達式“單詞 操作數(shù)/算當(dāng) ||s2的頂算符 時,重復(fù)若w為操作數(shù)，則w進s1,下一“單詞

prio(s2的頂算符(1)prio(w(2))w進s2；下一“單詞prio(s2的頂算符(1))=prio(w(2)w=“)”去括號，pop(s2)；下一“單詞prio(s2的頂算符(1)prio(w(2){c=bopa； }例求表達式的值：42*3–127–50#14#24#3#4#+5#+p(*)>p(-),退棧6#操作數(shù)退棧7#84#84a*b得69p(+)>p(-),退棧#4######-#-/#-/#-/#-/(#-/(p(-)>p()),退棧#-/#-/#-/a-b得c=2#-/p(()>p()),去括#-#p(/)>p(#),退棧########a/b得c=6##p(-)>p(#),退棧######a-b得c=44##p(#)=p(#),算法結(jié)隊列（排隊列及其操隊列----只允許在表的一端刪除元素,在另一端元空隊 不含元素的隊列隊 隊尾----隊列中只允許元素的一端。隊首元 處于隊首的元素 進隊----一個元素到隊列中。又稱：入隊 “先進先出”，“FirstInFirst“先進先出”表，“FIFO”表，排隊←a1,a2,......,←出←a1,a2,......,← 初始化,將q EnQueue(q,e)----將e隊列q的尾端 QetHead(q,e)----隊列q的首元素,送e 置q雙隊列（雙端隊列，deque----doubleendedqueue)(1)雙隊列----只許在表的兩端、刪除元素的線性表。a1,a2,.....,出 進a1,a2,.....,隊 隊輸出受限雙隊列----只許在表的兩端、在一端刪a1,a2,a1,a2,....., 輸入受限雙隊列----只允許在表的一端、在兩端刪a1,a2,a1,a2,....., 鏈?zhǔn)疥犃?用帶表頭結(jié)點的單鏈表表示隊Q

data∧表頭結(jié)∧(2空隊列Qdata表頭Qdata表頭結(jié)隊頭結(jié)其中： Q.front->dataQ.front->nexta1

∧∧隊尾結(jié)定義結(jié)點類typedefstructQnode{ElemTypedata； structQnode*next；//next為指針類型 其中 指向Qnode{

data生成空隊列算#defineLENGsizeof(Qnode) LinkQueueInitQueue() {LinkQueueQ； returnQ； }{LinkQueue }4.（空隊列時）新元素∧Q∧QdataP新結(jié)點X表頭結(jié)x

∧∧x表頭結(jié)隊頭(尾）表頭結(jié)（非空隊列時）新元素∧x∧x

datayy

表頭結(jié)X

隊頭(尾xx

表頭結(jié)隊頭結(jié)表頭結(jié)隊頭結(jié)∧∧y隊尾結(jié)新元素eLinkQueueEnQueue(LinkQueueQ,ElemType{Qnode*p； p=(Qnode*)malloc(LENG)；//生成新元素結(jié)點 Q.rear- //新結(jié) return //返回Q}{LinkQueueque; }新元素eintEnQueue(LinkQueue*Q,ElemType{Qnode*p； p=(Qnode*)malloc(LENG)； if(!p) //新結(jié)點生成失returnp- //裝入元素 return }LinkQueue }出 刪除隊頭結(jié)P

表頭結(jié)

隊頭結(jié)

P

表頭結(jié) 隊頭結(jié)

P表頭結(jié) 隊頭結(jié)

PXXPXX∧∧執(zhí)行：Q.front->next=p-∧∧∧∧PX ∧X∧X執(zhí)行∧∧LinkQueueDelQueue(LinkQueueQ,ElemType{Qnode*p； if(Q.front==Q.rear) {printf(“Emptyqueqe”return if return }隊列的順序表示

ArAA

空隊

空隊列 B,C,D

ABC A,B,C fDEFDEF

D，E,F此時空隊列 G進隊,“ 解決假溢出的方法一 移動元素DEFGDEF DEFG Q

DEF DEF

←G進隊,到GDEF r102

5←H,I4 3 E I G GHIDEF f設(shè)f指向隊頭元素；r指向隊尾元素后一空單元。Q[0..5]為循環(huán)隊列

空隊列f

AAB,C,DA

ABCD

ABCD

D D

←E

r

←FDE DEf

r

←G,HFDEFDEfG,H

FGHDEFGHDE

←IFGHGDE r解決方案1r+1==f，表明還剩若隊列為Q[0..maxleng-1]maxleng-1FGHDE滿隊FGHDE

←G,H若

ABCDE 當(dāng)r+1==f(f==0)&&(r==maxleng-即：(r+1)maxleng==f滿隊空隊列條件 當(dāng)(f==r)

f……………elem[MAXLENG-…………定義隊列的C#defineMAXLENG100Typedefstruct{ElemTypeelem[MAXLENG]; }SeQueueQ;隊列Q的結(jié)構(gòu)示意尾元素的后一個空位，,e為進隊元素。intEn_Queue(SeQueue&Q,Elemtypeif((Q.rear+1) //若Qreturn Q.rear=Q.