搜索
第三章栈和队列本章主要内容：•栈和队列的抽象数据类型定义•栈和队列的表示和实现•栈和队列的应用学习目的及要求：•掌握并理解栈和队列是两种特殊的线性结构•掌握栈和队列的抽象数据类型的定义以及表示和实现•掌握栈和队列的典型应用3.1栈一、栈的定义二、抽象数据类型栈的定义三、栈的表示和实现四、栈的应用举例3.1.1栈的定义1．定义栈(Stack)——是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表。栈顶(top)——允许插入和删除的一端，又称表尾。栈底(bottom)——栈的另一端，又称表头。若给栈S=(a1,a2…ai,…an)，则a1为栈底元素，an为栈顶元素，如图所示。进栈(push)——在栈顶插入一个元素，又称入栈或压入。出栈(pop)——在栈顶删除一个元素，又称退栈或弹出。空栈——栈中没有元素(n=0)。3.1栈2．栈的特点后进先出(LastInFirstOut，简称LIFO)。又称栈为后进先出表(简称LIFO结构)。3.1栈对栈的操作除了在栈顶进行插入和删除外，还有栈的初始化、判空及取栈顶元素等。其抽象数据类型定义如下：ADTStack{数据对象：D={ai|ai∈ElemSet，i=1,2…n，n≥0}数据关系：R={ai-1，ai|ai-1，ai∈D，i=2,3,…,n}基本操作：InitStack(&s)操作结果：构造一个空栈s。DestroyStack(&s)操作结果：栈s被销毁。ClearStack(&s)操作结果：将s清为空栈。3.1.2抽象数据类型栈的定义3.1栈StackEmpty(s)操作结果：若s为空栈，则返回TRUE，否则FALSE。StackLength(s)操作结果：返回s的元素个数，即栈的长度。GetTop(s,&e)操作结果：用e返回s的栈顶元素。Push(&s,e)操作结果：插入元素e为新的栈顶元素。Pop(&s,&e)操作结果：删除s的栈顶元素，并用e返回其值。StackTrasverse(s,visit())操作结果：从栈底到栈顶依次对s的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。}ADTStack3.1栈两种存储表示方式：顺序存储和链式存储。1.栈的顺序存储及其基本操作的实现(1)栈的顺序存储是利用一块连续的存储单元依次存放栈中的数据元素，并附一个指针top指示当前栈顶。采用顺序存储方式存储的栈称为顺序栈。3.1.3栈的表示和实现3.1栈(2)基本操作的算法①用一维数组和一个栈顶指针A．定义一个栈设栈中数据类型为整型，用stack数组存放栈中数据元素，定义一个栈类型stacktype：typedefintelemtype;#defineMaxSize100;typedefstruct{elemtypestack[MaxSize];inttop;}stacktype;3.1.3.1用静态数组表示栈3.1栈Top指示最后一个元素B．初始化栈：建立一个空栈s，实际上是将栈顶指针指向-1。voidinitstack(stacktype*s){s-top=-1;}C．判断栈是否为空栈：若栈s为空则返回1，否则返回0。intstackempty(stacktypes){if(s.top==-1)return(1);elsereturn(0);}top空栈3.1.3.1用静态数组表示栈3.1栈D．进栈：将元素x插入到栈s中。若栈满则显示相应信息，否则指针top增1，将x送入栈顶指针所在位置。Voidpush(stacktype*s,elemtypex){if(s-top==MaxSize-1)printf(“stackoverflow\n”);else{s-top++;s-stack[s-top]=x;}}3.1.3.1用静态数组表示栈3.1栈E．出栈：从栈中删除栈顶元素。若栈空则显示相应信息，否则栈指针减1，即栈顶为下一个元素的位置。elemtypepop(stacktype*s){elemtypee;if(s-top==-1)printf(“stackunderflow\n”);else{e=s-stack[s-top];s-top--;}returne;}3.1.3.1用静态数组表示栈3.1栈toptopatopbtopcabtopc进栈出栈ctopebtop3.1.3.1用静态数组表示栈3.1栈F．取栈顶元素：若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。Elemtypegettop(stacktypes){if(s.top==-1)printf(“stackempty\n”);elsereturn(s.stack[s.top]);}G.打印栈：voiddisplay(stacktypes){inti;printf(“stackdata:”)for(i=s.top;i=0,i--)printf(“%d”,s.stack[i]);printf(“\n”);}3.1.3.1用静态数组表示栈3.1栈②用一个栈顶指针和一个栈底指针以及一个初始的存储空间#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{elemtype*base;elemtype*top;intstacksize;}sqstack;连续的存储空间栈顶指针指示栈顶元素下一个位置(用栈顶指针动态地反映栈中元素的变化情况)basetop空栈baseatoptopb3.1.3.2用动态数组表示栈3.1栈Top指示最后一个元素的下一个位置B.初始化栈：构造一个空栈s，即s-top==s-basevoidinitstack(sqstack*s){s-base=(selemtype*)(malloc(stack_inti_size*sizeof(selemtype));if(!s-base)printf(“fail!\n”);else{s-top=s-base;s-stacksize=stack_init_size;}}3.1.3.2用动态数组表示栈3.1栈C．判断栈是否为空栈：若栈s为空则返回1，否则返回0。Intstackempty(sqstack*s){if(s-top==s-base)return(1);elsereturn(0);}D.取栈顶元素：gettop(s)若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。selemtypegettop(sqstack*s){if(s-top==s-base)printf(“stackempty\n”);elsereturn(*(s-top-1));}3.1.3.2用动态数组表示栈3.1栈E.进栈：将元素x插入到栈s中。若栈满则追加存储空间，否则将x送入栈顶，指针top增1。Voidpush(sqstack*s,elemtypex){if(s-top-s-base=s-stacksize){s-base=(elemtype*)realloc(sbase,(s.stacksize+STACKINCREMENT)*sizeof(elemtype));s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=x;}//栈满的判断//重新定义栈空间//新栈顶//进栈3.1.3.2用动态数组表示栈3.1栈F.出栈：从栈中删除栈顶元素。若栈空则显示相应信息，否则栈指针减1，即栈顶为下一个元素的位置。elemtypepop(stacktype*s){elemtypee;if(s-top==s-base)printf(“stackunderflow\n”);else{s-top--;e=*s-top;}returne;}3.1.3.2用动态数组表示栈3.1栈2.栈的链式存储方式采用链式存储的栈称为链栈。3.1.3.3用单链表表示栈3.1栈栈底栈顶topa1^an-1andatanext…链栈的特点：(1)不存在栈满上溢的情况，是一种特殊的单链表。(2)链栈是动态存储结构，无需预先分配存储空间，因此节省存储空间。(3)入栈时，先申请一个结点的存储空间，然后修改栈顶指针。(4)出栈时，同样也是将栈顶的后继结点做为栈顶。3.1栈3.1.3.3用单链表表示栈用一维动态数组表示线性表1.指针的等价写法typedefstructa{intdata;structa*next;}node,*list;必须弄清的问题node*p;listp;等价用一维动态数组表示线性表2.直接修改与用函数修改的不同必须弄清的问题voidmain(){intx;x=0;}voidchange0(intr){r=0;}voidchange1(int*r){*r=0;}voidmain(){intx;change0(x);change1(&x);}√×在函数内部改变传递进来的参数，要想外部也改变，必须让传递进来的参数是指针。用一维动态数组表示线性表3.传递的参数本身是指针怎么处理？必须弄清的问题voidmain(){listp;p=null;}voidchange1(list*p){*p=null;}voidmain(){listx;change1(&x);}typedefstructa{intdata;structa*next;}node,*list;把指针参数当普通变量对待(1)链栈结点类型的定义：typedefstructnode{elemtypedata;structnode*next;}node;(2)初始化栈voidinitstack(node*top){top=NULL;}栈底a1^an-1an栈顶topdatanext…3.1.3.3用单链表表示栈3.1栈voidinitstack(node**top){*top=NULL;}×(3)入栈voidpush(node**top,elemtypee){node*p;p=(node*)malloc(sizeof(node));p-data=e;p-next=*top;*top=p;}(4)出栈elemtypepop(node**top){node*q;elemtypedata;if(*top!=NULL){q=*top;data=q-data;*top=*top-next;q=null;return(data);}}3.1.3.3用单链表表示栈3.1栈3.2栈的应用举例一、数制转换二、表达式求值三、括号匹配的检验四、迷宫求解五、递归的实现由十进制N向其它进制d的转换是计算机实现计算的基本问题，基于原理：N=(Ndivd)*d+Nmodd其中：div为整除运算，mod为取余运算。一个十进制数转换成其它进制数：N除d取余，先余为低，后余为高。如：(1348)10=(2504)813481688888212040521348mod8低高一、数制转换3.2栈的应用举例算法分析：由十进制转换为其他进制的数的规则，可知，求得的余数的顺序为由低位到高位，而输出则是由高位到低位。因此，这正好利用栈的特点，先将求得的余数依次入栈，输出时，再将栈中的数据出栈。一、数制转换3.2栈的应用举例算法实现：voidconversion(){initstack(s);scanf(“%d”,n);while(n){push(s,n%8);n=n/8;}while(!stackempty()){pop(s,e);printf(“%d”,e);}}//余数入栈一、数制转换3.2栈的应用举例//结果从高位到低位出栈二、括号匹配的检验3.2栈的应用举例如何判断表达式中的括号匹配涉及两个方面：一是括号成对出现；二是成对出现的位置。如：[（）（）]是正确的[（]）是错误的检验括号匹配的方法用“期待的急迫程度”概念来描述。先出现的期待程度低，后出现的期待程度高，期待程度高的先得到满足。这一规律恰好符合栈的特点。[([