资源描述：
《《数据结构》(c语言版)第三章_栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列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栈和队列是两种常用的数据类型1第三章栈和队列3.1栈3.2栈的应用举例3.4队列3.3栈与递归的实现2学习提要：1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满
2、和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。重难点内容：顺序栈的相关操作、循环队列的判空判满33.1栈（stack）3.1.1栈的类型定义3.1.2栈的表示和实现4栈的定义：限定仅在表尾进行插入或删除操作的线性表。不含元素的空表称空栈。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)特点：后进先出（LIFO）3.1.1栈的类型定义表尾—栈顶表头—栈底5ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端
5、为栈顶，a1端为栈底。基本操作：}ADTStack栈的抽象数据类型定义：6InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())7一、顺序栈3.1.2栈的表示和实现//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;//栈底指针SElemT
6、ype*top;//栈顶指针intstacksize;}SqStack;8实现：一维数组s[M]top123450进栈Push(&S,e)A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450空栈topbasebasetoptop出栈Pop(&S,&e)123450ABCDEFtoptoptoptop栈空basetoptop栈底指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置9StatusInitSta
7、ck(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;}10StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize
8、+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}11StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}120M-1栈1底栈1顶栈2底栈2顶
9、在一个程序中同时使用两个栈13二、链栈栈的链式存储结构。栈顶指针就是链表的头指针。注意:链栈中指针的方向栈顶指针∧a1anan-114入栈操作push(&S,e)出栈操作pop(&S,&e)^…...栈底toptopxptop^…...栈底topqp->next=top;top=pq=top;top=top->next153.2栈的应用3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序问题3.2.4迷宫求解3.2.5表达式求值163.2.1数制转换十进制N和其他d进制数的转换原理:N=(Nd
