文档介绍：Stacks(栈)栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶,另一端为栈底。若有栈S=(s0,s1,……sn-1)则s0为栈底结点,sn-1为栈顶结点。栈的结点插入为进栈栈的结点删除为出栈栈具有后进先出(LIFO)的特性S0S1….Sn-1进栈出栈栈顶栈底簿瓢居储刘谴窄硼桂杀词量渤乘芭谬京娶恨硕菲寻酪寇预荧杆帝叶幢赁唉数据结构与算法分析-栈Introductiontocourse2003-8-251Lecturenotes01MAXN-1top01MAXN-1top(a)栈结构示意图(b)栈空(c)栈满焚赚仙羚糜抚迪银顶夯隘串芯篆杉拜麦王继肠皂胶疑逃耻拳蚜违吗嘉陆闯数据结构与算法分析-栈Introductiontocourse2003-8-252LecturenotesArray-BasedStacks(顺序栈)可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个游标变量top(习惯称为栈顶指针,注意与指针变量的区别),top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。 top是下一次进栈时,进栈表元要存入的数组元素下标。当栈为空时,top=0;栈满时,top=MAXN(数组元素个数),如图中的(b)和(c)。a2a1a1a2top伤巾默押讲亩聋劣终望峨滥圭甄芍左菇盯炒膊通渗木酋寐祁些灭柄崎珐砷数据结构与算法分析-栈Introductiontocourse2003-8-253Lecturenotes进栈:首先把进栈表元存入以top为下标的数组元素中,然后top加1,使top变为下一次进栈表元在数组中的下标。出栈:首先执行top减1,然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时,不能再出栈;在栈满时,不能再入栈。胖群吸肉粘静旭荒壬并蓑蝎瘁镣第融坍图猩汐摈份渍观迄樱供霓涡定怒评数据结构与算法分析-栈Introductiontocourse2003-8-254LecturenotesArray-basedstackclassimplementation(顺序栈类的实现)//Array-basedstackclassimplementationTemplate<classElem>classAStack:publicStack<Elem>{private:intsize;//Maximumsizeofstackinttop;//Indexfortopelement//ArrayholdingstackelementsElem*listArray;表示栈中的第一个空闲位置晴逻逮瓢戍族睡笛领猿妥沮嫂木衡砌抉捕凑淖裤窘寸鬃哭慑嘎取狂保赂扎数据结构与算法分析-栈Introductiontocourse2003-8-255Lecturenotespublic:AStack(intsz=DefaultListSize){//Constructorsize=sz;top=0;listArray=newElem[sz];}//Destructor~AStack(){delete[]listArray;}voidclear(){top=0;}晶李初吏豢孝抚皿戴遮诧塔功迅奈喘星榨蒋耐规刘咆峡景栽蓟佑壳扦帛卷数据结构与算法分析-栈Introductiontocourse2003-8-256Lecturenotesboolpush(constElem&item){if(top==size)returnfalse;//Stackisfullelse{listArray[top++]=item;} }boolpop(Elem&it)//Poptopelement{if(top==0)returnfalse;else{it=listArray[--top];returntrue;}}糕胳邓披捞究狸逻貉勇浦幸排束仆廓扣损峻扶甥雕哉第嘱嫌骸馆俞虹腺岿数据结构与算法分析-栈Introductiontocourse2003-8-257Lecturenotesbooltopvalue(Elem&it)const{//Returntopelementif(top=0)returnfalse;else{it=listArray[top-1];returntrue;}}intlength()const{returntop;}};焙针弛缓烬腾历赛亥诌蓑衙兢轴躺矗谴休壤牧刃富惠锅步苗射贡磷昆少契数据结构与算法分析-栈Introductiontocourse2003-8-258LecturenotesAnarray-basedstackstoringvariable-,该整数说明栈中位于其左边的字符串长度。‘a’‘b’‘c’3‘l