第三章+栈和队列Data+Structure+StackQueue.ppt

3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a0，a1，a2，…an)，则a0称为栈底元素，an为栈顶元素。栈中元素按a0，a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top 例、一叠书或一叠盘子。 顺序栈类的实现 template <class Elem> class AStack:public Stack<Elem>{ private: int size; int top; Elem *listArray; public: AStack(int sz=DefaultListSize) {size=sz; top=0; listArray=new Elem[size];} ~AStack() {delete [] listArray;} void clear() { top=0;} 顺序栈类的实现 bool push(const Elem& item){ if(top==size) return false; else{listArray[top++]=item; return true;} } bool pop(Elem &it){ if(top==0) return false; else {it=listArray[--top]; return true;} } bool topValue(Elem &it) const{ if(top==0) return false; else {it=listArray[top-1]; return true;} } 顺序栈类的实现 int length() const {return top;} }; 链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈类的实现 template <class Elem> class LStack:public Stack<Elem>{ private: Link<Elem>* top; int size; public: LStack(int sz=DefaultListSize) {top=NULL; sz=0;} ~LStack() {clear();} 链栈类的实现 void clear(){ while(top!=NULL){ Link<Elem>* temp=top; top->top->next; delete temp; }//while sz=0; }//clear bool push(const Elem& item){ top=new Link<Elem>(item ,top); size++; return true; } 链栈类的实现 bool pop(Elem& it){ if(size==0) return false; it=top->element; Link<Elem>* ltemp=top->next; delete top; top=ltemp; size--; return true; }//pop 链栈类的实现 bool topValue(Elem& it) const{ if(size==0) return false; it=top->element; return true; }//topValue int length()const {ret