数据结构课件第三章1讲

2023/9/22计算机科学与技术教研室1第三章栈和队列第1讲栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈

1、抽象数据类型栈的定义

2、栈的表示和实现3.1栈（stack）栈的定义和特点栈的定义栈的特点限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈先进后出（FILO）或后进先出（LIFO）2023/9/22计算机科学与技术教研室3/17ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)下面让我们通过一个Flash来具体了解吧：2023/9/22计算机科学与技术教研室4/17栈的表示和实现顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空2023/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取栈内元素取栈顶元素取栈顶元素算法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->