數(shù)據(jù)結構課件第三章1講

2023/9/22計算機科學與技術教研室1第三章棧和隊列第1講棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1棧

1、抽象數(shù)據(jù)類型棧的定義

2、棧的表示和實現(xiàn)3.1棧（stack）棧的定義和特點棧的定義棧的特點限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧先進后出（FILO）或后進先出（LIFO）2023/9/22計算機科學與技術教研室3/17ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)下面讓我們通過一個Flash來具體了解吧：2023/9/22計算機科學與技術教研室4/17棧的表示和實現(xiàn)順序棧實現(xiàn)：一維數(shù)組s[M]top=0123450棧空棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為0top123450進棧Atop出棧棧滿BCDEF設數(shù)組維數(shù)為Mtop=0,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？?023/9/22計算機科學與技術教研室5/17#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;Typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;棧的順序存儲表示：2023/9/22計算機科學與技術教研室6/17StatusInitStack(SqStack&S){//構造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack構造空棧初始化初始化算法2023/9/22計算機科學與技術教研室7/17StackGetTop(SqStackS,SElemType&e){//若棧不空，則用e返回S的棧頂元素，并返回OK，//否則返回ERROR；

if(S.top==S.base)returnERROR;e=*（S.top-1）;returnOK;}//GetTop取棧內(nèi)元素取棧頂元素取棧頂元素算法2023/9/22計算機科學與技術教研室8/17StatusPush(SqStack&S,SElemTypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));;if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//Push入棧（偽代碼）2023/9/22計算機科學與技術教研室9/17intpush(ints[],intx,inttop){if(top==M){printf("overflow");return(-M);}s[top]=x;return(++top);}入棧算法2023/9/22計算機科學與技術教研室10/170M-1棧1底棧1頂棧2底棧2頂在一個程序中同時使用兩個棧2023/9/22計算機科學與技術教研室11/17StackPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；//否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop出棧（偽代碼）2023/9/22計算機科學與技術教研室12/17intpop(ints[],inttop,int*q){if(top==0){printf("stackempty");return(0);}*q=s[--top];return(top);}出棧算法2023/9/22計算機科學與技術教研室13/17鏈棧棧頂^…...topdatalink棧底結點定義typedefstructnode{intdata;structnode*link;}JD;2023/9/22計算機科學與技術教研室14/17JD*lzjz(JD*top,intx){JD*p;p=(JD*)malloc(sizeof(JD));p->data=x;p->link=top;top=p;return(p);}鏈式入棧2023/9/22計算機科學與技術教研室15/17鏈式入棧算法圖示^…...棧底topxptop2023/9/22計算機科學與技術教研室16/17JD*lztz(JD*top,int*p){JD*q;if(top!=NULL){q=top;*p=top->