彈出棧頂運(yùn)算符數(shù)學(xué)與信息技術(shù)學(xué)院課件

數(shù)據(jù)結(jié)構(gòu)

李萍

數(shù)據(jù)結(jié)構(gòu)李萍第三章棧和隊(duì)列主要學(xué)習(xí)內(nèi)容:掌握棧和隊(duì)列是兩種操作受限的線性表掌握棧和隊(duì)列的兩種存儲(chǔ)實(shí)現(xiàn)算法理解遞歸算法執(zhí)行過(guò)程中棧的變化過(guò)程

第三章棧和隊(duì)列主要學(xué)習(xí)內(nèi)容:3.1棧1.概念是限定僅在表尾進(jìn)行插入和刪除操作的線性表.允許插入和刪除的一端為棧頂（top),另一端稱為棧底（bottom).2.圖示一、定義an-1an-2…a1a0bottomtop退棧（彈出）進(jìn)棧（壓入）3.1棧1.概念一、定義an-1an-2…a1a0bott3.特性邏輯結(jié)構(gòu)：一對(duì)一存儲(chǔ)結(jié)構(gòu)：順序和鏈?zhǔn)酱鎯?chǔ)（順序棧和鏈棧）運(yùn)算規(guī)則：先進(jìn)后出基本操作：入棧、出棧、讀棧頂、判棧空、判棧滿等一、定義3.1棧3.特性一、定義3.1棧1.順序棧的靜態(tài)定義#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZE];inttop;}SqStack定義一個(gè)指向順序棧的變量：

SqStacksq;二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧1.順序棧的靜態(tài)定義二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧2.順序棧的基本操作棧空?？眨簍op=-10

棧滿：top=sq.MAXSIZE-1讀棧頂元素sq.data[top],top的值未變出棧sq.top--top的值改變?nèi)霔q.top++sq.data[top]=e二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧2.順序棧的基本操作二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧3.順序棧的動(dòng)態(tài)定義#defineMAXSIZE1024typedefstruct{datatype*base;datatype*top;intstacksize;}SqStack定義一個(gè)指向順序棧的變量：

SqStacksq;二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧3.順序棧的動(dòng)態(tài)定義二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧4.順序棧的基本操作棧空?？眨簊q.top=sq.base棧滿：sq.top–sq.base>=sq.stacksize讀棧頂元素*sq.top,top的值未變出棧sq.top--入棧sq.top++*sq.top=e二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧4.順序棧的基本操作二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧二、棧的表示和實(shí)現(xiàn)（鏈棧）Ntop空棧：top指向空無(wú)棧滿:因?yàn)榭梢苑峙浣Y(jié)點(diǎn)入棧：在棧頂進(jìn)行入棧，相當(dāng)于在鏈表頭插入結(jié)點(diǎn)出棧：在棧頂進(jìn)行出棧，相當(dāng)于在鏈表頭刪除結(jié)點(diǎn)3.1棧二、棧的表示和實(shí)現(xiàn)（鏈棧）N3.1棧習(xí)題考題：1、若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb習(xí)題考題：一選擇題1.對(duì)于棧操作數(shù)據(jù)的原則是（）。

A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序2.一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（）。A.不確定B.n-i+1C.iD.n-i3.若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（）。

A.i-j-1B.i-jC.j-i+1D.不確定的一選擇題1.對(duì)于棧操作數(shù)據(jù)的原則是（）。4.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）

A.543612B.453126C.346521D.2341565.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（）

A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪6.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是()。

A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-16.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為1．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為_(3)_。1．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)3.2棧的應(yīng)用1.數(shù)制轉(zhuǎn)換（38）10=（）2基本思想：余數(shù)先進(jìn)后出，符合棧的特點(diǎn)2.括號(hào)匹配基本思想：從左到右讀取括號(hào),不等于#就循環(huán)凡出現(xiàn)左括號(hào)，則進(jìn)棧凡出現(xiàn)右括號(hào)，首先檢查棧是否為空，若棧空，則表明該右括號(hào)多作，否則和棧頂元素比較；若相匹配，則左括號(hào)出棧，否則表明不匹配表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明表達(dá)式中匹配正確，否則左括號(hào)多余。3.2棧的應(yīng)用1.數(shù)制轉(zhuǎn)換3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想：需要兩個(gè)棧：對(duì)象棧s1和算符棧s2。當(dāng)自左至右掃描表達(dá)式的每一個(gè)字符時(shí):若當(dāng)前字符是運(yùn)算對(duì)象，入對(duì)象棧，若是運(yùn)算符時(shí)，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入算符棧，繼續(xù)向后處理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低則從對(duì)象棧出棧兩個(gè)運(yùn)算量，從算符棧出棧一個(gè)運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入對(duì)象棧，繼續(xù)處理當(dāng)前字符。3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想可以先轉(zhuǎn)化為后綴表達(dá)式，再進(jìn)行計(jì)算從左到右依次讀取表達(dá)式如果是操作數(shù)直接輸出到后綴表達(dá)式是左括號(hào)壓棧是右括號(hào)，彈出棧頂運(yùn)算符，若不是左括號(hào)，將彈出的棧頂運(yùn)算符輸出后綴字符中，重復(fù)此步，直到取到左括號(hào)，并將左右括號(hào)丟棄其它運(yùn)算符（+-*/等）與棧頂運(yùn)算符相比，如果高于棧頂運(yùn)算符，則壓棧；否則彈出棧頂元素，輸出至后綴表達(dá)式讀完表達(dá)式后，如果最后棧不空，將所有棧元素彈出至后綴表達(dá)式3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想計(jì)算后綴表達(dá)式讀后綴表達(dá)式，是操作數(shù)就壓棧是運(yùn)算符，則彈出棧頂?shù)膬蓚€(gè)操作數(shù)計(jì)算，將結(jié)果再壓入棧后綴表達(dá)式讀，棧內(nèi)即是表達(dá)式的值3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.3棧與遞歸的實(shí)現(xiàn)如圖3。73.3棧與遞歸的實(shí)現(xiàn)如圖3。7習(xí)題1.棧在（）中應(yīng)用。

A.遞歸調(diào)用B.子程序調(diào)用

C.表達(dá)式求值D.A，Ｂ，Ｃ2.表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。

A．a(chǎn)bcd*+-B.abc+*d-C.abc*+d-D.-+*abcd3.表達(dá)式3*2^(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（），其中^為乘冪。（要求能畫出棧的變化情況）

A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-習(xí)題1.棧在（）中應(yīng)用。習(xí)題4.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

A．隊(duì)列B．多維數(shù)組

C．棧D.線性表習(xí)題4.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種共享?xiàng)?.設(shè)有兩個(gè)棧S1,S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O..maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。共享?xiàng)?.4隊(duì)列一、定義隊(duì)列是只允許在一端刪除，另一端插入的線性表，允許刪除的一端叫隊(duì)頭（front),允許插入的一端叫隊(duì)尾（rear）.特點(diǎn)：先進(jìn)先出a0，a1，a2，…，an-1，進(jìn)隊(duì)出隊(duì)隊(duì)首隊(duì)尾3.4隊(duì)列一、定義a0，a1，a2，…，an-1，3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)1.語(yǔ)言描述#defineMAXSIZE1024/*隊(duì)列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*隊(duì)員的存儲(chǔ)空間*/intrear,front;/*隊(duì)頭隊(duì)尾指針*/}SqQueue;

定義一個(gè)指向隊(duì)的變量：

SqQueuesq;3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)置空隊(duì)sq.front=sq.rear=0入隊(duì)sq.data[sq.rear]=xsq.rear++;出隊(duì)sq.front--;

讀隊(duì)頭、隊(duì)尾sq.data[sq.front]sq.data[sq.rear-1]3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)隊(duì)中元素個(gè)數(shù)m=sq.rear-sq.front隊(duì)滿m==MAXSIZE隊(duì)空m==03.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)存在的問題：假溢出sq.rear=m-1時(shí)，再入隊(duì)時(shí)雖然前面有空間，但是尾指針已經(jīng)接近空間的上界而不能再入隊(duì)。frontrearBCD3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)frontrearBCD3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)假溢出解決方案：隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間。循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;入隊(duì)：sq.data[rear]=x;

sq.rear=(rear+1)%M;出隊(duì)：sq.front=(front+1)%M;3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)循環(huán)隊(duì)列存在的問題：隊(duì)空sq.front==sq.rear隊(duì)滿sq.front==sq.rear3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)循環(huán)隊(duì)列解決方案：另外設(shè)一個(gè)標(biāo)志存儲(chǔ)隊(duì)中元素個(gè)數(shù)num==0代表隊(duì)空，num==MAXSIZE代表隊(duì)滿少用一個(gè)元素空間：隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)1.語(yǔ)言描述typedefstruct{datatypedata[M];intfront;intrear;intcount;//記錄隊(duì)中元素點(diǎn)數(shù)}cirqueue;3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作入隊(duì)voidenqueue（cirqueue*q,datatypex）{if(q->count==M)//判隊(duì)滿if((q.rear+1)%M==q.front){printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;//插入元素xq->count++;//修改表長(zhǎng)}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作出隊(duì)datatypedequeue(cirqueue*q){if(q->count==0)//判隊(duì)空if((q.rear==q.front)){printf(“queuenull“);exit(0);}q->front=(q->front+1)%m;//刪除隊(duì)頭元素

q->count--;//修改表長(zhǎng)

return(q->data[q->font]);}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作讀隊(duì)頭元素datatypegetqueue(cirqueueq){return(q.data[q.front]);}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列五、鏈隊(duì)列1.定義限制在表頭刪除，表尾插入的單鏈表。由一個(gè)頭指針和一個(gè)尾指針確定鏈表的頭和尾frontrear

datalink3.4隊(duì)列五、鏈隊(duì)列frontreardatalin3.4隊(duì)列五、鏈隊(duì)列2.語(yǔ)言描述結(jié)點(diǎn)類型描述typedefstructnode{datatypedata;structnode*next;}queuenode;頭尾指針描述typedefstruct{queuenode*front;queuenode*rear;}linkqueue;3.4隊(duì)列五、鏈隊(duì)列頭尾指針描述3.4隊(duì)列五、鏈隊(duì)列3.圖示(a)非空隊(duì)rearfronta1an∧

…a2rearfronta1∧

rearfront

∧(b)空隊(duì)(c)鏈隊(duì)中只有一個(gè)元素結(jié)點(diǎn)

頭尾指針封裝在一起的鏈隊(duì)3.4隊(duì)列五、鏈隊(duì)列(a)非空隊(duì)rearfronta1an∧3.4隊(duì)列五、鏈隊(duì)列4.算法實(shí)現(xiàn)創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)：

LinkQueue*Init_LQueue(){queuenode*s;linkqueuep;s=(queuenode*)malloc(sizeof(queuenode));//申請(qǐng)結(jié)點(diǎn)

s->next=NULL;p.front=s;p.rear=s;return&p;3.4隊(duì)列五、鏈隊(duì)列3.4隊(duì)列五、鏈隊(duì)列4.算法實(shí)現(xiàn)入隊(duì)

voidIn_LQueue(linkqueue*q,datatypex){QNode*p;p=malloc(sizeof(QNnode));//申請(qǐng)新結(jié)點(diǎn)

p->data=x;p->next=q->rear->next;q->rear->next=p;//插入尾部

q->rear=p;//改變尾指針}3.4隊(duì)列五、鏈隊(duì)列3.4隊(duì)列五、鏈隊(duì)列4.算法實(shí)現(xiàn)出隊(duì)intOut_LQueue(linkqueue*q,datatype*x){queuennode*p;if(Empty_LQueue(q)){printf(＂隊(duì)空＂)；return0;}//隊(duì)空，出隊(duì)失敗

else{p=q->front->next;q->front->next=p->next;*x=p->data;//隊(duì)頭元素放x中

free(p);if(q->front->next==NULL)q->rear=q->front;//只有一個(gè)元素時(shí)，出隊(duì)后隊(duì)空，此時(shí)還要要修改隊(duì)尾指針參考

return1;}}3.4隊(duì)列五、鏈隊(duì)列習(xí)題考題：1.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a，b，c，d，e，f，g依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是b，d，c，f，e，a，g，則棧S的容量至少是

A.1

B.2

C.3

D.4習(xí)題考題：習(xí)題考題：2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順順序是（）A、bacdeB、dbaceC、dbcaeD、ecbad習(xí)題考題：習(xí)題1.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。

A.僅修改頭指針B.僅修改尾指針

C.頭、尾指針都要修改D.頭、尾指針可能都要修改2.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)()。

A．僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針

C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改習(xí)題1.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）習(xí)題3.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m17.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？()A.1和5B.2和4C.4和2D.5和118.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()。

A.1234B.4132C.4231D.4213習(xí)題3.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針分1.已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是_______。2．區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是______和______。3．設(shè)循環(huán)隊(duì)列用數(shù)組A[1..M]表示，隊(duì)首、隊(duì)尾指針分別是FRONT和TAIL，判定隊(duì)滿的條件為_______。習(xí)題1.已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序謝謝!謝謝!數(shù)據(jù)結(jié)構(gòu)

李萍

數(shù)據(jù)結(jié)構(gòu)李萍第三章棧和隊(duì)列主要學(xué)習(xí)內(nèi)容:掌握棧和隊(duì)列是兩種操作受限的線性表掌握棧和隊(duì)列的兩種存儲(chǔ)實(shí)現(xiàn)算法理解遞歸算法執(zhí)行過(guò)程中棧的變化過(guò)程

第三章棧和隊(duì)列主要學(xué)習(xí)內(nèi)容:3.1棧1.概念是限定僅在表尾進(jìn)行插入和刪除操作的線性表.允許插入和刪除的一端為棧頂（top),另一端稱為棧底（bottom).2.圖示一、定義an-1an-2…a1a0bottomtop退棧（彈出）進(jìn)棧（壓入）3.1棧1.概念一、定義an-1an-2…a1a0bott3.特性邏輯結(jié)構(gòu)：一對(duì)一存儲(chǔ)結(jié)構(gòu)：順序和鏈?zhǔn)酱鎯?chǔ)（順序棧和鏈棧）運(yùn)算規(guī)則：先進(jìn)后出基本操作：入棧、出棧、讀棧頂、判?？铡⑴袟M等一、定義3.1棧3.特性一、定義3.1棧1.順序棧的靜態(tài)定義#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZE];inttop;}SqStack定義一個(gè)指向順序棧的變量：

SqStacksq;二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧1.順序棧的靜態(tài)定義二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧2.順序棧的基本操作?？諚？眨簍op=-10

棧滿：top=sq.MAXSIZE-1讀棧頂元素sq.data[top],top的值未變出棧sq.top--top的值改變?nèi)霔q.top++sq.data[top]=e二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧2.順序棧的基本操作二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧3.順序棧的動(dòng)態(tài)定義#defineMAXSIZE1024typedefstruct{datatype*base;datatype*top;intstacksize;}SqStack定義一個(gè)指向順序棧的變量：

SqStacksq;二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧3.順序棧的動(dòng)態(tài)定義二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧4.順序棧的基本操作?？諚？眨簊q.top=sq.base棧滿：sq.top–sq.base>=sq.stacksize讀棧頂元素*sq.top,top的值未變出棧sq.top--入棧sq.top++*sq.top=e二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧4.順序棧的基本操作二、棧的表示和實(shí)現(xiàn)（順序棧）3.1棧二、棧的表示和實(shí)現(xiàn)（鏈棧）Ntop空棧：top指向空無(wú)棧滿:因?yàn)榭梢苑峙浣Y(jié)點(diǎn)入棧：在棧頂進(jìn)行入棧，相當(dāng)于在鏈表頭插入結(jié)點(diǎn)出棧：在棧頂進(jìn)行出棧，相當(dāng)于在鏈表頭刪除結(jié)點(diǎn)3.1棧二、棧的表示和實(shí)現(xiàn)（鏈棧）N3.1棧習(xí)題考題：1、若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb習(xí)題考題：一選擇題1.對(duì)于棧操作數(shù)據(jù)的原則是（）。

A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序2.一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（）。A.不確定B.n-i+1C.iD.n-i3.若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（）。

A.i-j-1B.i-jC.j-i+1D.不確定的一選擇題1.對(duì)于棧操作數(shù)據(jù)的原則是（）。4.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）

A.543612B.453126C.346521D.2341565.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（）

A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪6.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是()。

A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-16.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為1．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為_(3)_。1．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)3.2棧的應(yīng)用1.數(shù)制轉(zhuǎn)換（38）10=（）2基本思想：余數(shù)先進(jìn)后出，符合棧的特點(diǎn)2.括號(hào)匹配基本思想：從左到右讀取括號(hào),不等于#就循環(huán)凡出現(xiàn)左括號(hào)，則進(jìn)棧凡出現(xiàn)右括號(hào)，首先檢查棧是否為空，若?？?，則表明該右括號(hào)多作，否則和棧頂元素比較；若相匹配，則左括號(hào)出棧，否則表明不匹配表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？眨瑒t表明表達(dá)式中匹配正確，否則左括號(hào)多余。3.2棧的應(yīng)用1.數(shù)制轉(zhuǎn)換3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想：需要兩個(gè)棧：對(duì)象棧s1和算符棧s2。當(dāng)自左至右掃描表達(dá)式的每一個(gè)字符時(shí):若當(dāng)前字符是運(yùn)算對(duì)象，入對(duì)象棧，若是運(yùn)算符時(shí)，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入算符棧，繼續(xù)向后處理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低則從對(duì)象棧出棧兩個(gè)運(yùn)算量，從算符棧出棧一個(gè)運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入對(duì)象棧，繼續(xù)處理當(dāng)前字符。3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想可以先轉(zhuǎn)化為后綴表達(dá)式，再進(jìn)行計(jì)算從左到右依次讀取表達(dá)式如果是操作數(shù)直接輸出到后綴表達(dá)式是左括號(hào)壓棧是右括號(hào)，彈出棧頂運(yùn)算符，若不是左括號(hào)，將彈出的棧頂運(yùn)算符輸出后綴字符中，重復(fù)此步，直到取到左括號(hào)，并將左右括號(hào)丟棄其它運(yùn)算符（+-*/等）與棧頂運(yùn)算符相比，如果高于棧頂運(yùn)算符，則壓棧；否則彈出棧頂元素，輸出至后綴表達(dá)式讀完表達(dá)式后，如果最后棧不空，將所有棧元素彈出至后綴表達(dá)式3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.2棧的應(yīng)用3.表達(dá)式計(jì)算基本思想計(jì)算后綴表達(dá)式讀后綴表達(dá)式，是操作數(shù)就壓棧是運(yùn)算符，則彈出棧頂?shù)膬蓚€(gè)操作數(shù)計(jì)算，將結(jié)果再壓入棧后綴表達(dá)式讀，棧內(nèi)即是表達(dá)式的值3.2棧的應(yīng)用3.表達(dá)式計(jì)算3.3棧與遞歸的實(shí)現(xiàn)如圖3。73.3棧與遞歸的實(shí)現(xiàn)如圖3。7習(xí)題1.棧在（）中應(yīng)用。

A.遞歸調(diào)用B.子程序調(diào)用

C.表達(dá)式求值D.A，Ｂ，Ｃ2.表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。

A．a(chǎn)bcd*+-B.abc+*d-C.abc*+d-D.-+*abcd3.表達(dá)式3*2^(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（），其中^為乘冪。（要求能畫出棧的變化情況）

A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-習(xí)題1.棧在（）中應(yīng)用。習(xí)題4.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

A．隊(duì)列B．多維數(shù)組

C．棧D.線性表習(xí)題4.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種共享?xiàng)?.設(shè)有兩個(gè)棧S1,S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O..maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。共享?xiàng)?.4隊(duì)列一、定義隊(duì)列是只允許在一端刪除，另一端插入的線性表，允許刪除的一端叫隊(duì)頭（front),允許插入的一端叫隊(duì)尾（rear）.特點(diǎn)：先進(jìn)先出a0，a1，a2，…，an-1，進(jìn)隊(duì)出隊(duì)隊(duì)首隊(duì)尾3.4隊(duì)列一、定義a0，a1，a2，…，an-1，3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)1.語(yǔ)言描述#defineMAXSIZE1024/*隊(duì)列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*隊(duì)員的存儲(chǔ)空間*/intrear,front;/*隊(duì)頭隊(duì)尾指針*/}SqQueue;

定義一個(gè)指向隊(duì)的變量：

SqQueuesq;3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)置空隊(duì)sq.front=sq.rear=0入隊(duì)sq.data[sq.rear]=xsq.rear++;出隊(duì)sq.front--;

讀隊(duì)頭、隊(duì)尾sq.data[sq.front]sq.data[sq.rear-1]3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)隊(duì)中元素個(gè)數(shù)m=sq.rear-sq.front隊(duì)滿m==MAXSIZE隊(duì)空m==03.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)存在的問題：假溢出sq.rear=m-1時(shí)，再入隊(duì)時(shí)雖然前面有空間，但是尾指針已經(jīng)接近空間的上界而不能再入隊(duì)。frontrearBCD3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)frontrearBCD3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)假溢出解決方案：隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間。循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;入隊(duì)：sq.data[rear]=x;

sq.rear=(rear+1)%M;出隊(duì)：sq.front=(front+1)%M;3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)循環(huán)隊(duì)列存在的問題：隊(duì)空sq.front==sq.rear隊(duì)滿sq.front==sq.rear3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)2.操作實(shí)現(xiàn)循環(huán)隊(duì)列解決方案：另外設(shè)一個(gè)標(biāo)志存儲(chǔ)隊(duì)中元素個(gè)數(shù)num==0代表隊(duì)空，num==MAXSIZE代表隊(duì)滿少用一個(gè)元素空間：隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front3.4隊(duì)列三、隊(duì)列的順序?qū)崿F(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)1.語(yǔ)言描述typedefstruct{datatypedata[M];intfront;intrear;intcount;//記錄隊(duì)中元素點(diǎn)數(shù)}cirqueue;3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作入隊(duì)voidenqueue（cirqueue*q,datatypex）{if(q->count==M)//判隊(duì)滿if((q.rear+1)%M==q.front){printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;//插入元素xq->count++;//修改表長(zhǎng)}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作出隊(duì)datatypedequeue(cirqueue*q){if(q->count==0)//判隊(duì)空if((q.rear==q.front)){printf(“queuenull“);exit(0);}q->front=(q->front+1)%m;//刪除隊(duì)頭元素

q->count--;//修改表長(zhǎng)

return(q->data[q->font]);}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)2.基本操作讀隊(duì)頭元素datatypegetqueue(cirqueueq){return(q.data[q.front]);}3.4隊(duì)列四、循環(huán)隊(duì)列的實(shí)現(xiàn)3.4隊(duì)列五、鏈隊(duì)列1.定義限制在表頭刪除，表尾插入的單鏈表。由一個(gè)頭指針和一個(gè)尾指針確定鏈表的頭和尾frontrear

datalink3.4隊(duì)列五、鏈隊(duì)列frontreardatalin3.4隊(duì)列五、鏈隊(duì)列2.語(yǔ)言描述結(jié)點(diǎn)類型描述typedefstructnode{datatypedata;structnode*next;}queuenode;頭尾指針描述typedefstruct{queuenode*front;queuenode*rear;}linkqueue;3.4隊(duì)列五、鏈隊(duì)列頭尾指針描述3.4隊(duì)列五、鏈隊(duì)列3.圖示(a)非空隊(duì)rearfronta1an∧

…a2rearfronta1∧

rearfront

∧(b)空隊(duì)(c)鏈隊(duì)中只有一個(gè)元素結(jié)點(diǎn)

頭尾指針封裝在一起的鏈隊(duì)3.4隊(duì)列五、鏈隊(duì)列(a)非空隊(duì)rearfronta1an∧3.4隊(duì)列五、鏈隊(duì)列4.算法實(shí)現(xiàn)創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)：

LinkQueue*Init_LQueue(){queuenode*s;linkqueuep;s=(queuenode*)malloc(sizeof(queuenode));//申請(qǐng)結(jié)點(diǎn)

s->next=NULL;p.front=s;p.rear=s;return&p;3.4隊(duì)列五、鏈隊(duì)列3.4隊(duì)列五、鏈隊(duì)列4.算法實(shí)現(xiàn)入隊(duì)

voidIn_LQueue(linkqueue*q,datatypex){QNode*p;p=malloc(sizeof(QNnode));//申請(qǐng)新結(jié)點(diǎn)

p->data=x;p->next=q->rear->next;q->rear->next=p;//插入尾部

q->rear=p;