软件技术基础 第10章ppt课件.ppt

《软件技术基础 第10章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章栈和队列西安电子科技大学刘锋第一节栈第一节栈一、栈的概念栈是被限定仅在表的一端进行插入和删除操作的线性表，插入即入栈，删除即出栈。第一节栈一、栈的概念A入栈A第一节栈一、栈的概念B入栈AB第一节栈一、栈的概念C入栈ACB第一节栈一、栈的概念ACB栈底元素栈顶元素第一节栈一、栈的概念C出栈ABACB第一节栈一、栈的概念B出栈AACB第一节栈一、栈的概念A出栈ACB第一节栈一、栈的概念栈的操作原则是FILO或LIFO第一节栈二、栈的基本运算完成栈的初始化，即构建空栈。1、置空栈Setnull(S)第一节栈二、栈的基本运

2、算将元素x插入栈S中。2、进栈Push(S,x)第一节栈二、栈的基本运算删除栈顶元素，栈指针减1。3、出栈Pop(S)第一节栈二、栈的基本运算取出栈S的栈顶元素，栈指针不变。4、取栈顶元素Gettop(S)第一节栈二、栈的基本运算如果栈S为空，返回1，否则返回0。5、判断栈空StackEmpty(S)第一节栈三、栈的存储结构使用栈的原则进行操作的顺序表。1顺序栈第一节栈三、栈的存储结构1顺序栈typedefstruct{Elemtypedata[maxsize];inttop;/*栈顶指针*/}Stack;第一节栈三、栈

3、的存储结构1顺序栈ACBtop=2第一节栈三、栈的存储结构1顺序栈/*置空栈*/把栈顶指针初始化为-1第一节栈三、栈的存储结构1顺序栈/*置空栈*/voidSetnull(S){S.top=-1;}第一节栈三、栈的存储结构1顺序栈/*进栈*/将元素X插入到栈S中第一节栈三、栈的存储结构1顺序栈/*进栈*/intPush(StackS,Elemtypex){if(S.top>=maxsize-1)return0;else{S.top++;S.data[S.top]=x;}}第一节栈三、栈的存储结构1顺序栈/*进栈*/int

4、Push(StackS,Elemtypex){if(S.top>=maxsize-1)return0;else{S.top++;S.data[S.top]=x;}}第一节栈三、栈的存储结构1顺序栈/*出栈*/ElemtypePop(StackS){Elemtypex;if(S.top==-1)return0;else{x=S.data[S.top];S.top--;returnx;}}第一节栈三、栈的存储结构1顺序栈/*出栈*/ElemtypePop(StackS){Elemtypex;if(S.top==-1)retu

5、rn0;else{x=S.data[S.top];S.top--;returnx;}}第一节栈三、栈的存储结构1顺序栈/*取栈顶元素*/ElemtypeGettop(StackS){Elemtypex;if(S.top==-1)return0;else{x=S.data[S.top];returnx;}}第一节栈三、栈的存储结构1顺序栈/*取栈顶元素*/ElemtypeGettop(StackS){Elemtypex;if(S.top==-1)return0;else{x=S.data[S.top];returnx;}}

6、第一节栈三、栈的存储结构1顺序栈/*判断栈空*/intStackEmpty(StackS){if(S.top>=0)return0;elsereturn1;}第一节栈三、栈的存储结构2链栈只允许在表头进行插入和删除运算的单链表，单链表的表头指针即栈顶指针。第一节栈三、栈的存储结构2链栈cba^topx入栈第一节栈三、栈的存储结构2链栈xcba^topcba^topx入栈第一节栈三、栈的存储结构2链栈cba^topc出栈第一节栈三、栈的存储结构2链栈ba^topcba^topc出栈第一节栈三、栈的存储结构2链栈typede

7、fstructnode{Elemtypedata;structnode*next;}Snode;structSnode*top;第一节栈三、栈的存储结构/*置空栈*/voidSetnull(Snode*s){s=null;}2链栈第一节栈三、栈的存储结构/*进栈*/voidPush(Snode*s,Elemtypex){Snode*p;p->data=x;p->next=null;if(s==null)s=p;else{p->next=s;s=p;}}2链栈第一节栈三、栈的存储结构/*进栈*/voidPush(Snode

8、*s,Elemtypex){Snode*p;p->data=x;p->next=null;if(s==null)s=p;else{p->next=s;s=p;}}2链栈第一节栈三、栈的存储结构/*出栈*/ElemtypePop(Snode*s){Elemtypex;Snode*p=s;if(s==null)print