第3章---栈与队列

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

1、第三章栈与队列集美大学计算机学院王俊玲6/15/20211栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列第三章栈与队列6/15/20212只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottom6/15/20213//Stack.h在此定义templateclassStack{//栈的类定义public:Stack(){};//构造函数virtualvoidPush(Ex)=0;//进栈virtua

2、lboolPop(E&x)=0;//出栈virtualboolgetTop(E&x)=0;//取栈顶virtualboolIsEmpty()=0;//判栈空virtualboolIsFull()=0;//判栈满}；栈的抽象数据类型转类Stack的使用1使用2①virtual表明Push()是虚函数；“=0”表明类LinearList是抽象类，不提供Size()的实现(”纯”)；所以Push()为纯虚函数。②纯虚函数Push()在Stack的子类中必须定义自己的实现。6/15/20214#include#include#includ

3、e“stack.h”templateclassSeqStack:publicStack{//顺序栈类定义private:栈的数组存储表示—顺序栈0123456789maxSize-1top(栈空)elements转基类Stack的定义转assert.h说明转stack.h说明6/15/20215E*elements;//栈元素存放数组inttop;//栈顶指针intmaxSize;//栈最大容量voidoverflowProcess();//栈的溢出处理public:SeqStack(intsz=50);//构造函数～SeqStack(){delete

4、[]elements;}//析构函数voidPush(Ex);//进栈boolPop(E&x);//出栈boolgetTop(E&x);//取栈顶内容boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==maxSize-1;}转overflowProcess函数的实现转Push函数的实现转Pop函数的实现转getTop函数的实现转IsFull函数的使用转IsEmpty函数的使用1使用2sz默认值6/15/20216voidMakeEmpty(){top=-1;}//清空栈的内容的MakeEmpty函数的

5、声明和实现friendostream&operator<<(ostream&os,SeqStack&s)//输出栈中元素的重载操作};操作符“<<”重载的实现见教材P916/15/20217top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c6/15/20218topc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop6/15/20219顺序栈的操作templatevoidSeqStack::overflowProcess(){//私有函数：当栈满则执行扩充栈存储空间处理E*

6、newArray=newE[2*maxSize];//创建更大的存储数组(2倍)for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize+=maxSize;delete[]elements;elements=newArray;//改变elements指针};转overflowProcess函数的声明转overflowProcess函数的使用6/15/202110templatevoidSeqStack::Push(Ex){//若栈不满,则将元素x插入该栈栈顶,否则溢出处理if(IsFull()==tru

7、e)overflowProcess;//栈满elements[++top]=x;//栈顶指针先加1,再进栈};templateboolSeqStack::Pop(E&x){//函数退出栈顶元素并返回栈顶元素的值if(IsEmpty()==true)returnfalse;x=elements[top--];//栈顶指针退1returntrue;//退栈成功};转Push函数的声明转Pop函数的声明转函数IsFull的声明和实现转函数overflowProcess的声明转函数IsEmpty的声明