数据结构与算法分析-栈.ppt

《数据结构与算法分析-栈.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Stacks(栈)栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另一端为栈底。若有栈S=(s0,s1,……sn-1)则s0为栈底结点，sn-1为栈顶结点。栈的结点插入为进栈栈的结点删除为出栈栈具有后进先出(LIFO)的特性S0S1….Sn-1进栈出栈栈顶栈底2003-8-251Lecturenotes01MAXN-1top01MAXN-1top(a)栈结构示意图(b)栈空(c)栈满2003-8-252LecturenotesArray-BasedStacks(顺序栈)可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要

2、一个游标变量top(习惯称为栈顶指针，注意与指针变量的区别)，top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。top是下一次进栈时，进栈表元要存入的数组元素下标。当栈为空时，top=0；栈满时，top=MAXN（数组元素个数），如图中的(b)和(c)。a2a1a1a2top2003-8-253Lecturenotes进栈:首先把进栈表元存入以top为下标的数组元素中，然后top加1，使top变为下一次进栈表元在数组中的下标。出栈:首先执行top减1，然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时，不能再出栈；在栈满时，不能再入栈。200

3、3-8-254LecturenotesArray-basedstackclassimplementation(顺序栈类的实现)//Array-basedstackclassimplementationTemplateclassAStack:publicStack{private:intsize;//Maximumsizeofstackinttop;//Indexfortopelement//ArrayholdingstackelementsElem*listArray;表示栈中的第一个空闲位置2003-8-255Lecturenotespu

4、blic:AStack(intsz=DefaultListSize){//Constructorsize=sz;top=0;listArray=newElem[sz];}//Destructor~AStack(){delete[]listArray;}voidclear(){top=0;}2003-8-256Lecturenotesboolpush(constElem&item){if(top==size)returnfalse;//Stackisfullelse{listArray[top++]=item;}}boolpop(Elem&it)//Poptopelement

5、{if(top==0)returnfalse;else{it=listArray[--top];returntrue;}}2003-8-257Lecturenotesbooltopvalue(Elem&it)const{//Returntopelementif(top=0)returnfalse;else{it=listArray[top-1];returntrue;}}intlength()const{returntop;}};2003-8-258LecturenotesAnarray-basedstackstoringvariable-lengthstrings.每个位

6、置存储一个字符或一个整数，该整数说明栈中位于其左边的字符串长度。‘a’‘b’‘c’3‘l’‘h’‘l’‘e’‘o’5012345678910top=102003-8-259LecturenotesLinkedStacks(链式栈)即用链表来实现栈。链表的第一个表元是栈顶结点，链表的末尾表元是栈底结点。链表的首表元指针就是栈顶指针top，top为NULL的空链表是空栈。x∧top栈底2003-8-2510Lecturenotes链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操

7、作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。2003-8-2511LecturenotesLinkedstackclassimplementation//Linklist-basedstackimplementationTemplateclassLstack:publicStack{Private:Link*top;//pointertofirstelementintSize;//countnumberofe