老師課件第3章棧和隊(duì)列

第三章棧和隊(duì)列主講：薛春艷棧的定義及實(shí)現(xiàn)1棧的應(yīng)用2隊(duì)列的定義及實(shí)現(xiàn)3隊(duì)列的應(yīng)用4主要內(nèi)容§3.1.1

棧的定義【定義】棧是限定在一端進(jìn)行插入和刪除操作的線性表。

棧頂：允許插入和刪除的一端叫做棧頂。棧底：不允許插入和刪除的一端叫做棧底。入棧（進(jìn)棧）：向棧中插入數(shù)據(jù)元素的操作。出棧（退棧）：從棧中刪除數(shù)據(jù)元素的操作。空棧：當(dāng)棧中沒有數(shù)據(jù)元素時(shí)稱為空棧。a1a2a3an-1an…入棧出棧棧頂元素棧底元素

a1a2a3…an-1an入棧出棧棧頂元素棧底元素棧的結(jié)構(gòu)特點(diǎn)每次進(jìn)棧的元素都被放在原棧頂元素之上而成為新的棧頂元素。每次出棧的總是當(dāng)前棧中“最新”的元素，即最后進(jìn)棧的元素——當(dāng)前的棧頂元素。

若要將一個(gè)非棧頂元素轉(zhuǎn)化為棧頂元素，需要將這個(gè)元素上面的數(shù)據(jù)元素全部刪掉。元素若以a1，a2，…，an的順序進(jìn)棧，則退棧的次序?yàn)閍n，an-1，…，a1?！娟P(guān)系】棧中數(shù)據(jù)元素之間是線性關(guān)系?！緮?shù)據(jù)元素】可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對象。

【基本操作】1.InitStack（S）

2.ClearStack（S）

3.IsEmpty（S）4.IsFull（S）

5.Push（S，x）6.Pop（S，x）

7.GetTop（S，x）

8.DestroyStack(&S)9.StackLength(S)棧的抽象數(shù)據(jù)類型定義①順序棧中數(shù)據(jù)元素用數(shù)組存放。②順序棧的棧底位置是固定不變的，設(shè)置在順序表的表頭。③順序棧的棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（棧頂元素在數(shù)組中的下標(biāo)）來指示當(dāng)前棧頂位置。④棧的最大長度為MAXSIZE，即top==MAXSIZE-1，說明棧已滿，不能再進(jìn)行入棧操作了。ABCtop

ABC

…elem[0]elem[1]elem[top]elem[MAXSIZE-1]棧底棧頂元素top空棧

topabcdef進(jìn)棧溢出topb進(jìn)棧abtopabcdee進(jìn)棧topabdee退棧ctopa進(jìn)棧a用來存放棧頂元素的下標(biāo)，top為-1表示空棧.top空棧topabdd退棧cc退棧topabcb退棧abtopaa退棧top§3.1.2棧的順序存儲結(jié)構(gòu)typedefintElemType; //數(shù)據(jù)元素的類型為整型constintMAXSIZE=100; //數(shù)組的容量classSqStack{private:ElemTypeelem[MAXSIZE];inttop;public:~SqStack(){}; //析構(gòu)函數(shù)

SqStack(){top=-1;}//構(gòu)造函數(shù),初始化一個(gè)空棧

voidSetEmpty(){top=-1;} //置已有的棧為空棧

voidpush(ElemTypee); //進(jìn)棧

ElemTypepop(); //出棧

voidPrintOut(); //輸出棧中數(shù)據(jù)元素

ElemTypeGettop(); //取棧頂元素?cái)?shù)據(jù)

};voidSqStack::push(ElemTypee){if(top==MAXSIZE-1) cout<<"\n棧滿溢出"<<endl;else{top++;elem[top]=e;}}【操作結(jié)果】在S頂部插入數(shù)據(jù)元素x。入棧操作topAtopABtopElemTypeSqStack::pop(){ElemTypex;if(top==-1){cout<<"\n棧為空,不能進(jìn)行出棧操作"<<endl;return0; }else{x=elem[top]; top--;returnx;}}出棧操作ABCDtopABCtopABtopElemTypeSqStack::Gettop(){if(top==-1){cout<<“空棧！”；

return-1;}else

returnelem[top];}【操作結(jié)果】取棧頂數(shù)據(jù)元素的值賦給x。取棧頂數(shù)據(jù)元素操作ABCDtopx=elem[top]voidSqStack::PrintOut(){cout<<"\nPrintOutData:\n";if(top==-1)cout<<"\n已是空棧！";

//if(IsEmpty())cout<<"\n已是空棧！"else{for(intk=top;k>=0;k--) cout<<setw(6)<<elem[k]; cout<<endl;}}輸出棧內(nèi)元素鏈棧：采用鏈表作為存儲結(jié)構(gòu)實(shí)現(xiàn)的棧叫做鏈棧。一般采用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧。由于棧的插入和刪除操作僅限制在表頭位置進(jìn)行，所以鏈表的表頭指針可以作為棧頂指針來使用?！?.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)ana2a1∧an-1……top空棧:top->next=NULLtop∧top：棧頂指針，始終指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)棧頂元素棧底元素鏈棧的類定義typedefintElemType;structLsnode{ElemTypedata;Lsnode*next;};classLsStack{private:Lsnode*top; //棧頂指針

public:LsStack(); //構(gòu)造函數(shù),建立空棧

~LsStack(){} //析構(gòu)函數(shù)

voidSetEmpty(); //將現(xiàn)有的棧置空

voidDisplay(); //顯示棧數(shù)據(jù)內(nèi)容

voidPush(ElemTypex); //進(jìn)棧

ElemTypePop(); //出棧};LsStack::LsStack()

{top=newLsnode; top->next=NULL;}構(gòu)造函數(shù)操作voidLsStack::SetEmpty()//將已有的鏈棧清空{(diào)Lsnode*p=top->next,*q;while(p!=NULL){top->next=p->next; deletep; //刪除一個(gè)結(jié)點(diǎn)

p=top->next;}}清空操作LsStack::~LsStack()//將已有的鏈棧清空{(diào)SetEmpty();deletetop;top=NULL;}析構(gòu)函數(shù)操作top∧初始化的空棧申請新結(jié)點(diǎn)p->data=x;p->next=NULL;ptopx∧x∧pai-1a1∧a2……topxp鏈棧的入棧操作第一個(gè)結(jié)點(diǎn)入棧top->next=p;第i個(gè)結(jié)點(diǎn)入棧p->next=top->next;top->next=p;voidLsStack::Push(ElemTypex) //進(jìn)棧Push{Lsnode*p;p=newLsnode;//申請一個(gè)結(jié)點(diǎn)

p->data=x;p->next=top->next;top->next=p;}入棧操作鏈棧的出棧操作棧頂結(jié)點(diǎn)出棧top->next=p->next;x=p->data;deletep;anan-1toppa1∧……出棧結(jié)點(diǎn)的存儲空間被釋放ElemTypeLsStack::Pop() {Lsnode*p;ElemTypex;if(top!=NULL) {p=top->next;top->next=top->next->next;x=p->data; deletep;returnx; }else{cout<<"\nStackNull!\n";return0;}}出棧操作§3.1.4棧的應(yīng)用

表達(dá)式求值：表達(dá)式由操作數(shù)、運(yùn)算符、界限符組成。操作數(shù)（operand）：常數(shù)或變量運(yùn)算符（operator）:

算術(shù)運(yùn)算符：+、-、*、/等等。關(guān)系運(yùn)算符：≠、＝、≤、≥、＜、＞邏輯運(yùn)算符：AND、OR、NOT界限符（delimiter）:

左右括號，表達(dá)式結(jié)束符#等。

θ1θ2 + - * / ( ) #

+ > > < < < > >- > > < < < > >* > > > > < > >/ > > > > < > >( < < < < < = ) > > > > > >#< < < < < = 算符優(yōu)先關(guān)系表1、先乘除、后加減2、同級運(yùn)算符先左后右3、先括號內(nèi)，后括號外4、表達(dá)式的開始結(jié)束5、其他情況運(yùn)算過程中，任意兩個(gè)相繼出現(xiàn)的算符θ1、θ2之間的優(yōu)先關(guān)系如下：第一步：規(guī)定運(yùn)算符的優(yōu)先級關(guān)系，即生成算符優(yōu)先級關(guān)系表；第二步：設(shè)置兩個(gè)棧：OPTR運(yùn)算符棧（‘

#’入棧）、OPND操作數(shù)棧；第三步：從左到右依次讀出表達(dá)式中的各個(gè)符號（運(yùn)算符或操作數(shù)），每讀出一個(gè)符號按以下原則進(jìn)行處理：表達(dá)式求值——算法思想若讀出的是操作數(shù)，則將該操作數(shù)壓入操作數(shù)棧，并依次讀入下一個(gè)符號。若讀出的是運(yùn)算符，則作進(jìn)一步判斷：①若讀出的當(dāng)前運(yùn)算符的優(yōu)先級大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級，則將讀出的運(yùn)算符壓入運(yùn)算符棧，并依次讀入表達(dá)式中下一個(gè)符號。②若讀出運(yùn)算符的優(yōu)先級低于運(yùn)算符棧頂運(yùn)算符的優(yōu)先級，則從操作數(shù)棧連續(xù)退戰(zhàn)兩次，依次得到兩個(gè)操作數(shù)b、a（表達(dá)式中的運(yùn)算符都是雙目運(yùn)算符，所以需要兩個(gè)操作數(shù)），并從運(yùn)算符棧退出一個(gè)運(yùn)算符送入θ，然后對a、b進(jìn)行θ運(yùn)算，并將運(yùn)算結(jié)果作為中間結(jié)果壓入操作數(shù)棧。③若棧頂運(yùn)算符的優(yōu)先級與剛讀入的運(yùn)算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運(yùn)算符（左括號）退棧即可。④若讀出的是表達(dá)式界限符‘

#’，且運(yùn)算符棧棧頂元素也是‘

#’，則說明表達(dá)式起始符“#”與表達(dá)式結(jié)束符“#”相遇，整個(gè)表達(dá)式求值完畢。最后的計(jì)算結(jié)果在操作數(shù)棧的棧頂位置。topn操作數(shù)運(yùn)算符#topt3×(7–2)#操作數(shù)3運(yùn)算符#topntopt3×(7–2)#Push(OPND,’3’)操作數(shù)3運(yùn)算符#×topntopt×(7–2)#Push(OPTR,’×’)操作數(shù)3運(yùn)算符#×(topntopt（7–2）#Push(OPTR,’(’)操作數(shù)37運(yùn)算符#×(topntopt7–2)#Push(OPND,’7’)操作數(shù)37運(yùn)算符#×(－topntopt–2)#Push(OPTR,’－’)操作數(shù)372運(yùn)算符#×(－topntopt2)#Push(OPND,’2’)操作數(shù)35運(yùn)算符#×(topntopt）#Operate(‘7’,’-‘,’2’)操作數(shù)35運(yùn)算符#×topntopt#Pop(OPTR)操作數(shù)15運(yùn)算符#topntopt#Operate(‘3’,‘×’,‘5’)操作數(shù)15運(yùn)算符#topntoptreturn(GetTop(OPND))一個(gè)遞歸函數(shù)的運(yùn)行過程類似于多個(gè)函數(shù)的嵌套調(diào)用，差別僅在于"調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)"。為了保證"每一層的遞歸調(diào)用"都是對"本層"的數(shù)據(jù)進(jìn)行操作，在執(zhí)行遞歸函數(shù)的過程中需要一個(gè)"遞歸工作棧"。它的作用是:1、將遞歸調(diào)用時(shí)的實(shí)際參數(shù)和函數(shù)返回地址傳遞給下一層執(zhí)行的遞歸函數(shù)；2、保存本層的參數(shù)和局部變量，以便從下一層返回時(shí)重新使用它們。棧與遞歸的實(shí)現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自己的過程叫做遞歸。voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;i++)printf(“%3d”,w);printf(“\n”);}}遞歸的執(zhí)行情況分析遞歸調(diào)用執(zhí)行情況如下：W=3Print(2);for(i=1;i<=w;i++)printf(“%3d”,w);printf(“\n”);W=2Print(1);for(i=1;i<=w;i++)printf(“%3d”,w);printf(“\n”);W=1Print(0);for(i=1;i<=w;i++)printf(“%3d”,w);printf(“\n”);W=0(3)w=1(2)w=2(1)w=3top122333§3.2.1隊(duì)列的定義【定義】隊(duì)列：只能在表的一端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作的線性表。

隊(duì)尾(rear)：允許插入的一端叫做隊(duì)尾。隊(duì)頭(front)：允許刪除的一端叫做隊(duì)頭。入隊(duì)：向隊(duì)列中插入數(shù)據(jù)元素的操作。出隊(duì)：從隊(duì)列中刪除數(shù)據(jù)元素的操作?？贞?duì)列：隊(duì)列中沒有數(shù)據(jù)元素時(shí)稱為空隊(duì)列。a1a2a3…an-1an入隊(duì)列出隊(duì)列隊(duì)尾元素隊(duì)頭元素每次入隊(duì)列的元素都被放在原隊(duì)尾元素之后而成為新的隊(duì)尾元素。每次出隊(duì)列的總是當(dāng)前隊(duì)列中“最舊”的元素，即最先入隊(duì)列的元素—當(dāng)前的隊(duì)頭元素。

隊(duì)列中的數(shù)據(jù)元素元素若以a1，a2，…，an的次序依次進(jìn)隊(duì)列，則只能依相同次序退出隊(duì)列。即a1是第一個(gè)出隊(duì)列的元素，只有在a1，a2，…，an-1

都離開隊(duì)列之后，an才能出隊(duì)列。frontrear空隊(duì)列frontrearA入隊(duì)AfrontrearB入隊(duì)ABfrontrearC,D入隊(duì)ABCDfrontrearA出隊(duì)BCDfrontrearB出隊(duì)CDfrontrearE,F,G入隊(duì)CDEFGCDEFGfrontrearH入隊(duì),溢出隊(duì)列的入隊(duì)和出隊(duì)§3.2.3隊(duì)列的順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的數(shù)據(jù)元素。附設(shè)兩個(gè)變量front指示隊(duì)列頭元素的位置（隊(duì)頭元素在數(shù)組中的下標(biāo)），rear指示隊(duì)列尾元素的下一個(gè)位置（隊(duì)尾元素下一個(gè)位置在數(shù)組中的下標(biāo)）。初始化空隊(duì)列：front=rear=0；數(shù)據(jù)元素入隊(duì)時(shí)rear加一；隊(duì)頭元素出隊(duì)時(shí)front加一。隊(duì)列滿的判別條件：rear==MAXSIZE。typedefintElemType;structSeQueuestr{ElemTypeelem[MAXSIZE];//一維數(shù)組

intfront,rear;//頭、尾指針};順序隊(duì)列的入隊(duì)和出隊(duì)(c)A出隊(duì)列后的狀態(tài)CB012345frontrear(a)空隊(duì)列012345frontrear(b)A、B、C入隊(duì)列后的狀態(tài)CBA012345frontrearEDC(d)D、E、F入隊(duì)列后的狀態(tài)012345Ffrontrear順序隊(duì)列滿的判別條件：rear==MAXSIZE真正隊(duì)滿的條件：rear-front==MAXSIZE【假溢出】順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲空間但不能進(jìn)行入隊(duì)列操作的溢出?！窘鉀Q辦法】1、采用循環(huán)隊(duì)列；

2、按最大可能的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)；

3、修改出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列中剩余數(shù)據(jù)元素向隊(duì)頭方向移動一個(gè)位置；

4、修改入隊(duì)算法，增加判斷條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向隊(duì)頭移動，然后再完成入隊(duì)操作。順序隊(duì)列的“假溢出”【循環(huán)隊(duì)列】

把順序隊(duì)列所使用的存儲空間臆造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列?！?.2.4循環(huán)隊(duì)列EDC0123MAXSIZE-1rearfront循環(huán)隊(duì)列…54順序隊(duì)列rearCDEMAXSIAZE-1.

543210front…循環(huán)隊(duì)列的結(jié)構(gòu)特點(diǎn)循環(huán)隊(duì)列和非循環(huán)順序隊(duì)列的存儲表示是完全一樣的。循環(huán)隊(duì)列的實(shí)質(zhì)就是順序隊(duì)列。循環(huán)隊(duì)列是將表示順序隊(duì)列的數(shù)組看成一個(gè)環(huán)狀的空間。即規(guī)定隊(duì)列中最后一個(gè)單元的直接后繼為隊(duì)列中的第一個(gè)單元。循環(huán)隊(duì)列不是在物理結(jié)構(gòu)上實(shí)現(xiàn)的真正的循環(huán)，只是使隊(duì)列在邏輯上實(shí)現(xiàn)循環(huán)。循環(huán)隊(duì)列與普通的順序隊(duì)列指針變化：順序隊(duì)列：入隊(duì)rear=rear+1;

出隊(duì)front=front+1;

循環(huán)隊(duì)列：

入隊(duì)rear=(rear+1)%MAXSIZE;

出隊(duì)front=(front+1)%MAXSIZE;隊(duì)滿：rear==front7012rearfront3465a17012a0a2front3465a6a5a4a3reara7

隊(duì)空：rear==front入隊(duì)：rear=(rear+1)%MAXSIZE出隊(duì)：front==(front+1)%MAXSIZEfronta97012a83465reara767012a2front345a6a5a4a3reara7【順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷】①使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長度）；判隊(duì)滿：count>0&&rear==front

判隊(duì)空：count==0②加設(shè)標(biāo)志位，出隊(duì)時(shí)置０,入隊(duì)時(shí)置１,則可識別當(dāng)前front==rear屬于何種情況判隊(duì)滿：tag==1&&rear==front

判隊(duì)空：tag==0&&rear==front

③少用一個(gè)存儲單元判隊(duì)滿：front==(rear+1)%MAXSIZE

判隊(duì)空：rear==front7012rearfront3465a17012reara0a2front3465a6a5a4a3A-G出隊(duì)H-N入隊(duì)01234567frontrear01234567frontJKrearIHLMN01234567frontrear空隊(duì)列A-G入隊(duì)45012367frontArearBCDEFG循環(huán)隊(duì)列的頭尾變化front、rear的移動方向都是順時(shí)針方向。front、rear的取值區(qū)間都是[0，MAXSIZE-1]。用來區(qū)別隊(duì)滿和隊(duì)空的少用的那個(gè)元素空間位置不是固定的，它是隨著front的位置變化而變化的。它總在front的前一個(gè)位置。rear永遠(yuǎn)追不上front（差一個(gè)位置：隊(duì)滿）；front能夠追上rear（隊(duì)空）。循環(huán)隊(duì)列的類定義classSeQueue{private:ElemTypeelem[MAXSIZE];intfront,rear;public:SeQueue(){front=0;rear=0;}//初始化空隊(duì)列

~SeQueue(){};intEmpty();voidDisplay(); //輸出隊(duì)列

voidAddQ(ElemTypex); //進(jìn)隊(duì)

ElemTypeDelQ(); //出隊(duì)

};intSeQueue::AddQ(ElemTypex){if((rear+1)%MAXSIZE==front) return(0);elem[rear]=x;

rear=(rear+1)%MAXSIZE;

return(1);}循環(huán)隊(duì)列的入隊(duì)操作intSeQueue::DelQ(){if（Q->front==Q->rear）

{cout<<"\nQueueisEmpty!"<<endl; return(-1);}else{front=(front+1)%MAXSIZE;

return(elem[front-1]);}}循環(huán)隊(duì)列的出隊(duì)操作§3.2.2隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefintElemType;structquenode{ElemTypedata; //數(shù)據(jù)域

quenode*next; //指針域};classLsQueue{private:quenode*front,*rear; //頭、尾指針

public:LsQueue();~LsQueue();intIsEmpty();voidDisplay();voidAddQ(ElemTypex);ElemTypeDelQ();};a1an∧a2……frontrear非空的鏈隊(duì)列空的鏈隊(duì)列判空條件：

front==rear;隊(duì)頭指針front：始終指向頭結(jié)點(diǎn)。隊(duì)尾指針rear：指向當(dāng)前鏈隊(duì)列中的最后一個(gè)數(shù)據(jù)元素。frontrear∧LsQueue::LsQueue()//構(gòu)造函數(shù)，初始化空隊(duì)

{quenode*p;p=newquenode;p->next=NULL;front=rear=p;}鏈隊(duì)列的構(gòu)造函數(shù)Q.frontQ.rear∧intLsQueue::IsEmpty()//判鏈隊(duì)列是否為空

{if(front==rear)return1;elsereturn0;}鏈隊(duì)列的判空操作鏈隊(duì)列的入隊(duì)操作a1an……Q.frontQ.rear申請新結(jié)點(diǎn)temp->data=x;temp->next=NULL;x∧

s第n+1個(gè)結(jié)點(diǎn)入隊(duì)列:rear->next=s;rear=s;∧x∧svoidLsQueue::AddQ(ElemTypex){{quenode*s;s=newquenode;s->data=x;s->next=NULL;rear->next=s;rear=s;}鏈隊(duì)列的入隊(duì)操作鏈隊(duì)列的出隊(duì)列操作a1an……Q.frontQ.rear∧a2panQ.frontQ.rear∧p=front->next;front->next=p->next;deletep;

p=front->next; front->next=p->next;if(p->next==NULL)rear=front;deletep;pElemTypeLsQueue::DelQ() {ElemTypex;quenode*p;if(front==rear){cout<<"\n隊(duì)列為空。"<<endl;x=-1;}else{p=front->next; front->next=p->next;