第3章数据结构

《第3章数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列第三章栈与队列23.1.1栈的定义只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)3.1栈(Stack)退栈进栈a0an-1an-2topbottom3classStack{//栈的类定义public:Stack(){};//构造函数~Stack(){};virtualvoidPush(DataType&x);//进栈virtualboolPop(DataType&x

2、);//出栈virtualboolgetTop(DataType&x);//取栈顶virtualboolIsEmpty();//判栈空virtualboolIsFull();//判栈满}；栈的抽象数据类型栈的抽象数据类型有两种典型的存储表示，基于数组的存储表示实现的栈称为顺序栈，基于链表的存储表示实现的栈称为链式栈。4typedefintDataType;classSeqStack{//顺序栈类定义private:DataType*elements;//栈元素存放数组inttop;//栈顶指针intmaxSize;//栈最

3、大容量栈的数组存储表示—顺序栈0123456789maxSize-1top(栈空)elements5voidoverflowProcess();//栈的溢出处理public:SeqStack(intsz=50);//构造函数~SeqStack(){delete[]elements;}//析构函数voidPush(DataType&x);//进栈boolPop(DataType&x);//出栈boolgetTop(DataType&x);//取栈顶内容boolIsEmpty()const{returntop==-1;}boo

4、lIsFull()const{returntop==maxSize-1;}intgetSize()const{returntop+1;}voidMakeEmpty(){top=-1;}friendostream&operator<<(ostream&os,SeqStack&S)};6top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c7topc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop①顺序栈的构造函数#include

5、#includeSeqStack::SeqStack（intsz）{elements=newDataType[sz];assert(elements!=NULL);top=-1;maxSize=sz;}断言（assert）机制是C++提供的一种功能，若参数表中给定的条件满足，则继续执行后续的语句；否则出错处理终止程序的执行。9②顺序栈的溢出处理voidSeqStack::overflowProcess(){//私有函数：当栈满则执行扩充栈存储空间处理DataType*newArray=newData

6、Type[2*maxSize];//创建更大的存储数组for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize+=maxSize;delete[]elements;elements=newArray;//改变elements指针};思路：①创建更大的存储数组②把原来的元素复制到新数组中③改变栈大小，删除原来的数组，栈指针指向新数组10③入栈操作voidSeqStack::Push(DataType&x){//若栈满,则溢出处理，将元素x插入该栈栈顶if(IsFull()==

7、true)overflowProcess();//栈满elements[++top]=x;//栈顶指针先加1,再进栈};④出栈操作boolSeqStack::Pop(DataType&x){//若栈不空，函数退出栈顶元素并将栈顶元素的值赋给x,//返回true，否则返回falseif(IsEmpty()==true)returnfalse;x=elements[top--];//先取元素，栈顶指针退1returntrue;//退栈成功};11⑤取栈顶元素boolSeqStack::getTop(DataType&x){//

8、若栈不空则x为该栈栈顶元素if(IsEmpty()==true)returnfalse;x=elements[top];returntrue;};⑥输出栈中元素的重载操作<