栈表达式求值队列 优先队列.ppt

《栈表达式求值队列 优先队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章栈和队列栈表达式求值队列优先队列只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottomtemplateclassStack{public:Stack(intsz=10);//构造函数voidPush(Type&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈intIsEmpty()const;//判栈空否intIsFull()con

2、st;//判栈满否}栈的抽象数据类型#includetemplateclassStack{private:inttop;//栈顶指针Type*elements;//栈元素数组intmaxSize;//栈最大容量public:Stack(intsz=10);//构造函数~Stack(){delete[]elements;}voidPush(Type&item);//进栈栈的数组表示—顺序栈TypePop();//出栈TypeGetTop();//取栈顶voidMakeEmpty(){top=-1;}//置空栈intIsEmpty()

3、const{returntop==-1;}intIsFull()const{returntop==maxSize-1;}}templateStack::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=NULL);//断言}top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptoptemplate

4、e>voidStack::Push(Type&item){assert(!IsFull());//先决条件断言elements[++top]=item;//加入新元素}templateintstack::Pop(){if(IsEmpty())return0;//栈空不退栈top--;return1;//退出栈顶元素}templateTypestack::GetTop(){assert(!IsEmpty());//先决条件断言returnelements[top];//取出栈顶元素}双栈共享一个

5、栈空间b[0]t[0]t[1]b[1]0maxSize-1V栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作toptemplateclassStack;templateclassStackNode{friendclassStack;private:Typedata;//结点数据StackNode*link;//结点链指针public:StackNode(Typed=0,StackNode*l=NULL):data(d),link(l){}

6、};链式栈(LinkedStack)类的定义templateclassStack{private:StackNode*top;//栈顶指针public:Stack():top(NULL){}~Stack();voidPush(constType&item);//进栈intPop();//退栈Type*GetTop();//读取栈顶元素voidMakeEmpty();//实现与~Stack()同intIsEmpty(){returntop==NULL;}}templateStack::~Stack(){St

7、ackNode*p;while(top!=NULL)//逐结点回收{p=top;top=top->link;deletep;}}templatevoidStack::Push(constType&item){top=newStackNode(item,top);//新结点链入*top之前,并成为新栈顶}templateintStack::Pop(){if(IsEmpty())return0;StackNode*p=top;t