资源描述：
《03栈new1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章栈和队列7/21/2021通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。7/21/20213.3栈的应用举例3.1栈的类型定义3.2栈类型的实现3.4队列的类型定义3.5队列类型的实现7/21/2021栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—
2、栈底，不含元素的空表称空栈。特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)3.1栈的类型定义7/21/2021ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的抽象数据类型定义7/21/2021InitStack(&S)DestroyStack(&S)ClearStack(&S)Stack
5、Empty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())7/21/20213.2栈类型的实现3.2.1顺序栈3.2.1链栈7/21/2021利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指向表尾的指针top，指示栈顶元素在顺序栈中的位置，称为栈顶指针。连续存储单元的基址用指针base指示，称为栈底指针。3.2.1顺序栈7/21/2021top=0123450栈S空栈顶指针top,指向实际栈顶前的空位置，初值为0top123450进栈
6、Atop出栈栈满BCDEF设数组大小为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空0M-1栈1底栈1顶栈2底栈2顶为减少溢出的概率，可以在同一段内存中同时使用两个栈.StackLength(S)basebasebase7/21/2021//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefs
7、truct{SElemType*base;SElemType*top;intstacksize;}SqStack;7/21/2021（1）初始化操作Initstack(sqstack&S)基本操作的实现：StatusInitstack(sqstack&S){s.base=(selemtype*)malloc(stack_init_size*sizeof(selemtype));if(!s.base)exit(overflow);s.top=s.base;s.stacksize=stack_init_size;returnok;}7/21/2021(
8、2)判栈空函数stackEmpty(sqstackS)statusstackempty(sqstacks){ifs.top==s.basereturn(true)elsereturn(false);}(3)返回桟的长度Stacklength(sqstacks)IntStacklength(sqstacks){return(s.top-s.base);}s.tops.baseCBAs.bases.top7/21/2021(4)取栈顶元素函数gettop(sqstacks,selemtype&e)Statusgettop(sqstacks,selemt
9、ype&e){if(s.top=s.base)returnerror;e=_____________;returnok;}CBAs.bases.top*(s.top–1)7/21/2021(5)进栈函数push(sqstack&s,selemtypee)Statuspush(sqstack&s,selemtypee){(1)if桟满追加空间；（2）e进桟；（3）top加1；}CBAs.bases.top7/21/2021StatusPush(SqStack*s,SElemTypee){if(s->top–s->base>=s->stacksize)
10、/*栈满，追加存储空间*/{l_temp=(SElemType*)realloc(s->base,(s->stacksiz
