数据结构第3章课件 中国石油大学(华东).ppt

《数据结构第3章课件 中国石油大学(华东).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列第三章栈与队列23.1.1栈的定义只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)3.1栈(Stack)退栈进栈a0an-1an-2top基于数组的存储表示实现的栈称为顺序栈，基于链表的存储表示实现的栈称为链式栈。3classSeqStack{//顺序栈类定义private:int*elements;//栈元素存放数组inttop;//栈顶指针intmaxSize;//栈最大容量栈的数组存储表示—顺序栈0123456789ma

2、xSize-1top(栈空)elements4voidoverflowProcess();//栈的溢出处理public:SeqStack(intsz=50);//构造函数~SeqStack(){delete[]elements;}//析构函数voidPush(int&x);//进栈intPop(int&x);//出栈intgetTop(int&x);//取栈顶内容intIsEmpty()const{returntop==-1;}intIsFull()const{returntop==maxSize-1;}intgetSize()const{returntop+1;}voidMake

3、Empty(){top=-1;}friendostream&operator<<(ostream&os,SeqStack&S)};①顺序栈的构造函数#include#includeSeqStack::SeqStack（intsz）{elements=newint[sz];assert(elements!=NULL);top=-1;maxSize=sz;}断言（assert）机制是C++提供的一种功能，若参数表中给定的条件满足，则继续执行后续的语句；否则出错处理终止程序的执行。6②顺序栈的溢出处理voidSeqStack::overflow

4、Process(){//私有函数：当栈满则执行扩充栈存储空间处理int*newArray=newint[2*maxSize];//创建更大的存储数组for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize+=maxSize;delete[]elements;elements=newArray;//改变elements指针};思路：①创建更大的存储数组②把原来的元素复制到新数组中③改变栈大小，删除原来的数组，栈指针指向新数组7③入栈操作voidSeqStack::Push(int&x){//若栈满,则溢出处理，将元素x插入该栈栈顶if

5、(IsFull())overflowProcess();//栈满elements[top++]=x;//栈顶指针先加1,再进栈};④出栈操作intSeqStack::Pop(int&x){//若栈不空，函数退出栈顶元素并将栈顶元素的值赋给x,//返回1，否则返回0if(IsEmpty())return0;x=elements[--top];//先取元素，栈顶指针退1return1;//退栈成功};[++top][top--]8⑤取栈顶元素intSeqStack::getTop(int&x){//若栈不空则x为该栈栈顶元素if(IsEmpty())return0;x=elements

6、[top];return1;};⑥输出栈中元素的重载操作<

7、/栈顶指针相遇栈空条件：t[0]=-1或t[1]=maxSize//退到栈底103.1.3栈的链接存储表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头top^11classLinkedStack{//链式栈类定义private:StackNode*top;//栈顶指针public:LinkedStack():top(NULL){}//构造函数~LinkedStack(){makeEmpty();}//析构函数voidPush(int&