文档介绍：2003-8-25Lecturenotes101MAXN-1top01MAXN-1top(a)栈结构示意图(b)栈空(c)栈满2003-8-25Lecturenotes2Array-BasedStacks(顺序栈)可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个游标变量top(习惯称为栈顶指针),top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。 top是下一次进栈时,进栈表元要存入的数组元素下标。当栈为空时,top=0;栈满时,top=MAXN(数组元素个数),如图中的(b)和(c)。a2a1a1a2top2003-8-25Lecturenotes3进栈:首先把进栈表元存入以top为下标的数组元素中,然后top加1,使top变为下一次进栈表元在数组中的下标。出栈:首先执行top减1,然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时,不能再出栈;在栈满时,不能再入栈。2003-8-25Lecturenotes4Array-basedstackclassimplementation(顺序栈类的实现)//Array-basedstackclassimplementationTemplate<classElem>classAStack:publicStack<Elem>{private:intsize;//Maximumsizeofstackinttop;//Indexfortopelement//ArrayholdingstackelementsElem*listArray;表示栈中的第一个空闲位置2003-8-25Lecturenotes5public:AStack(intsz=DefaultListSize){//Constructorsize=sz;top=0;listArray=newElem[sz];}//Destructor~AStack(){delete[]listArray;}voidclear(){top=0;}2003-8-25Lecturenotes6boolpush(constElem&item){if(top==size)returnfalse;//Stackisfullelse{listArray[top++]=item;returntrue;} }boolpop(Elem&it)//Poptopelement{if(top==0)returnfalse;else{it=listArray[--top];returntrue;}}2003-8-25Lecturenotes7booltopvalue(Elem&it)const{//Returntopelementif(top==0)returnfalse;else{it=listArray[top-1];returntrue;}}intlength()const{returntop;}};2003-8-25Lecturenotes8Anarray-basedstackstoringvariable-,该整数说明栈中位于其左边的字符串长度。‘a’‘b’‘c’3‘l’‘h’‘l’‘e’‘o’50**********top=102003-8-25Lecturenotes9LinkedStacks(链式栈)即用链表来实现栈。链表的第一个表元是栈顶结点,链表的末尾表元是栈底结点。链表的首表元指针就是栈顶指针top,top为NULL的空链表是空栈。x∧top栈底2003-8-25Lecturenotes10链栈则没有上溢的限制,它就象是一条一头固定的链子,可以在活动的一头自由地增加链环(结点)而不会溢出,链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要在头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。