资源描述：
《数据结构与算法-东北林业大学 第三章栈和队列演示文稿1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。3.1栈ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。用铁路调度站
2、表示栈栈的示意图栈的示意图例、一叠书或一叠盘子。anan-1a2a1栈顶栈底栈的抽象数据类型的定义ADTStack{数据对象：D={ai
3、ai∈ElemSet,I=1,2,…,n,n>=0}数据关系：R1={
4、ai-1,ai∈D,I=2,3,…n}基本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTraverse(S,visit())
5、}ADTStack3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)to
6、p=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈的存储结构·进栈算法#definestacksize100typedefstruct{Elemtypedata[stacksize];inttop;}seqstack;intpush(seqstack*s,Elemtypex){if(s->top==stacksize){printf(“overflow”);return(0);}else{s->data[s->top]=x;++
7、s->top;/*实际栈顶指针加1*/return(1);}}a2a3a4987654321a10top出栈算法：intpop(seqstack*s，elemtype*py){if(s->top==0){printf(“stackempty”);return(0);}else{--s->top;*py=s->data[s->top];/*返回出栈元素*/return(1);}}a2a3a4987654321a10topvoidinitstack(seqstack*S){S–>top=null;}判栈空intstackemp
8、ty(seqstackS){returnS.top==NULL;}栈初始化入栈算法0M-1栈1底栈1顶栈2底栈2顶出栈算法在一个程序中同时使用两个栈链式栈链式栈示意图3.1.3链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，其插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructnode{elemtypedata;structnode*next;}Lnode,*Linkstack;栈顶^…...t
9、opdatanext栈底入栈算法出栈算法^…...栈底toptopxptop^…...栈底topq链栈进栈算法intlpush(Linkstacks,inte){p=(Lnode*)malloc(sizeof(Lnode));p->data=e;p->next=s;s=p;return(1);}∧baseS进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧PbaseS进栈算法intlp
10、ush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧PbaseSe进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));
