Ch03 栈和队列01.ppt

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

1、第三章栈与队列数据结构电子教案1栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列第三章栈与队列2只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO,LastInFirstOut)栈(Stack)退栈进栈a0an-1an-2topbottom3templateclassStack{//栈的类定义public:Stack(){};//构造函数virtualvoidPush(constTx)=0;//进

2、栈virtualboolPop(T&x)=0;//出栈virtualboolgetTop(T&x)const=0;//取栈顶virtualboolIsEmpty()const=0;//判栈空virtualboolIsFull()const=0;//判栈满};栈的抽象数据类型4其中：elements:栈元素存放数组(指针类型)top：栈顶指针（整型）maxSize：栈的大小（整型）栈的线性存储表示—顺序栈0123456789maxSize-1top(栈空)elements5top空栈toptoptoptoptopa

3、进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c6topc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop7#include#include#include"stack.h"templateclassSeqStack:publicStack{//顺序栈类定义private:T*elements;//栈元素存放数组inttop;//栈顶指针intmaxSize;//栈最大容量voidoverflowProce

4、ss();//栈的溢出处理顺序栈的定义8public:SeqStack(intsz=50);//构造函数～SeqStack(){delete[]elements;}//析构函数voidPush(constT&x);//进栈boolPop(T&x);//出栈boolgetTop(T&x)const;//取栈顶内容boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==maxSize-1;}intgetSize()const{returntop+1

5、;}};9顺序栈的操作templatevoidSeqStack::overflowProcess(){//私有函数：当栈满则执行扩充栈存储空间处理T*newArray=newT[2*maxSize];//创建更大的存储数组for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize+=maxSize;delete[]elements;elements=newArray;//改变elements指针};10templatevoidS

6、eqStack::Push(constTx){//若栈不满,则将元素x插入栈顶,否则溢出处理if(IsFull()==true)overflowProcess();//栈满elements[++top]=x;//栈顶指针先加1,再进栈}templateboolSeqStack::Pop(T&x){//函数退出栈顶元素并返回栈顶元素的值if(IsEmpty()==true)returnfalse;x=elements[top--];//栈顶指针退1returntrue;//退栈成功}11

7、templateboolSeqstack::getTop(T&x)const{//若栈不空则函数返回该栈栈顶元素的地址if(IsEmpty()==true)returnfalse;x=elements[top];returntrue;}12双栈共享一个栈空间b[0]t[0]t[1]b[1]0maxSize-1V两个栈共享一个数组空间V[maxSize]设立栈顶指针数组t[2]和栈底指针数组b[2]t[i]和b[i]分别指示第i个栈的栈顶与栈底初始t[0]=b[0]=-1,t[1]=b[1]=

8、maxSize栈满条件：t[0]+1==t[1]//栈顶指针相遇栈空条件：t[0]=b[0]或t[1]=b[1]//退到栈底13boolPush(DualStack&DS,Tx,inti){if(DS.t[0]+1==DS.t[1])returnfalse;if(i==0)DS.t[0]++;elseDS.t[1]--;DS.V[DS.t[i]]=x;returntrue