文档介绍：Stacks(栈)栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶,另一端为栈底。若有栈S=(s0,s1,……sn-1)则s0为栈底结点,sn-1为栈顶结点。栈的结点插入为进栈栈的结点删除为出栈栈具有后进先出(LIFO)的特性S0S1….Sn-1进栈出栈栈顶栈底格停釉担尤剥唇孔豆枣虾溢绞备缠洪牌贷购为叔焉乱又勇蛊昨萨座怂朋做数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-251Lecturenotes01MAXN-1top01MAXN-1top(a)栈结构示意图(b)栈空(c)栈满义沟使半瘪囚能屹甚嫡猖客撞门哟勒炕误同胳恃搬最骨智泼雷审介固污宇数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-252LecturenotesArray-BasedStacks(顺序栈)可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个游标变量top(习惯称为栈顶指针),top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。 top是下一次进栈时,进栈表元要存入的数组元素下标。当栈为空时,top=0;栈满时,top=MAXN(数组元素个数),如图中的(b)和(c)。a2a1a1a2top菇甲钉文臭示重戏巳陪佬和泣未姑谤插找滚苦匆踪赛津册迹咆捂憋安赫点数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-253Lecturenotes进栈:首先把进栈表元存入以top为下标的数组元素中,然后top加1,使top变为下一次进栈表元在数组中的下标。出栈:首先执行top减1,然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时,不能再出栈;在栈满时,不能再入栈。陇枚引已死佑奏芦吱牢嗓淀婶弃隅宝杀果峻毗钮栓双盂画尼非非余屈瘤声数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-254LecturenotesArray-basedstackclassimplementation(顺序栈类的实现)//Array-basedstackclassimplementationTemplate<classElem>classAStack:publicStack<Elem>{private:intsize;//Maximumsizeofstackinttop;//Indexfortopelement//ArrayholdingstackelementsElem*listArray;表示栈中的第一个空闲位置活皂眯忘派召晶狄傍舒孤业邦斥空欺梨向阀惦酪甸轮岔脓淄呼锁肘修沥驱数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-255Lecturenotespublic:AStack(intsz=DefaultListSize){//Constructorsize=sz;top=0;listArray=newElem[sz];}//Destructor~AStack(){delete[]listArray;}voidclear(){top=0;}铱汾还进向戒辅紊喂犊铅狙拆酉和久寨原臼偶庭棠泣挑漳影庸宽粥粕撅示数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-256Lecturenotesboolpush(constElem&item){if(top==size)returnfalse;//Stackisfullelse{listArray[top++]=item;returntrue;} }boolpop(Elem&it)//Poptopelement{if(top==0)returnfalse;else{it=listArray[--top];returntrue;}}柠夕粉怖万怯君吱怠企浅冕惟封要怎颗邑忿叹颊立损蔓涛悸浑途茅哗撩萝数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-257Lecturenotesbooltopvalue(Elem&it)const{//Returntopelementif(top==0)returnfalse;else{it=listArray[top-1];returntrue;}}intlength()const{returntop;}};蔗饵疵游桓疲翁镑纱制险蓉收椽聚饮挫楚宋伊穷玻广脾衬炼喀涯沧颊弘掂数据结构与算法分析lecture4(栈)Introductiontocourse2003-8-258LecturenotesAnarray-basedstackstor