Ch03 栈与队列3.ppt

《Ch03 栈与队列3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈与队列3.1栈3.2栈的应用：递归3.3队列1栈可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点先进后出(FILO)3.1栈(Stack)退栈进栈a1antopbottoman-1一、栈的定义2templateclassStack{//栈的类定义public:Stack(){};//构造函数virtualvoidPush(Tx)=0;//进栈virtualboolPop(T&x)=0;//出栈virtualboolg

2、etTop(T&x)=0;//取栈顶virtualboolIsEmpty()=0;//判栈空virtualboolIsFull()=0;//判栈满}；栈的抽象数据类型3#include#includeconstintstackIncreament=20;//栈溢出时扩展空间的增量templateclassSeqStack{//顺序栈类定义private:T*elements;//存放栈中元素的栈数组inttop;//栈顶指针intmaxSize;//栈最大

3、容量voidoverflowProcess();//栈的溢出处理二、顺序栈0123456789maxSize-1top(栈空)elements4public:SeqStack(intsz=50);//构造函数～SeqStack(){delete[]elements;}//析构函数voidPush(Tx);//进栈boolPop(T&x);//出栈boolgetTop(T&x);//取栈顶内容boolIsEmpty()const{return(top==-1)?true:false;}boolIsFull()cons

4、t{return(top==maxSize-1)?true:false;}intgetSize()const{returntop+1;}voidMakeEmpty(){top=-1;}};5template＜classT＞SeqStack＜T＞::SeqStack(intsz)//建立一个最大尺寸为sz的空栈，若分配不成功则错误处理。{top=-1;maxSize=sz;elements=newT[maxSize];//创建栈的数组空间assert(elements!＝NULL);//断言}6top空栈toptop

5、toptopa进栈b进栈aababcdee进栈abcdef进栈溢出7c退栈topabdd退栈ctopabcb退栈abtoptopaa退栈空栈toptopabdee退栈c8栈的其他成员函数的实现templatevoidSeqStack::overflowProcess()//私有函数：当栈满则执行扩充栈存储空间处理{T*newArray=newT[maxSize+stackIncreament];//创建更大的存储数组if(newArray==NULL){cerr<<“存储分配失败！”<

6、l;exit(1);}for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize=maxSize+stackIncreament;delete[]elements;elements=newArray;//改变elements指针};9templatevoidSeqStack::Push(constT&x){if()overflowProcess;//栈满elements[++top]=x;//栈顶指针先加1,再进栈};template

7、T>boolSeqStack::Pop(T&x){if(IsEmpty()==true)returnfalse;x=elements[top--];//取当前元素值，栈顶指针退1returntrue;//退栈成功};IsFull()==truetop==maxsize-110templateboolSeqstack::getTop(T&x){//若栈不空则函数返回该栈栈顶元素的地址if(IsEmpty()==true)returnfalse;x=elements[top];returnt

8、rue;};11双栈共享一个栈空间b[0]t[0]t[1]b[1]0maxSize-1V12三、栈的链接存储表示—链式栈链式栈的栈顶在链头；插入与删除仅在栈顶处执行；链式栈无栈满问题，空间可扩充；131.链式栈(LinkedStack)类的定义templatestructLinkNode{//链表结点类的定义Tdata;//数据域LinkNo