栈与队列的基本操作.ppt

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

1、7.3栈与队列的基本操作栈和队都是限制存取位置的线性表，既可以由顺序表实现，又可以由链表实现。7.3.1栈7.3.3队　列7.3.2栈的应用（选读）第六单元OBP—动态内存分配与数据结构7.3.1栈栈的基本概念：栈是一种线性表，其元素的插入和删除只能在其一端进行。这个端叫做栈顶(top)，对应的另一端叫栈底(bottom)。特点：（1）栈中没有任何元素时，称为空栈。（2）进栈原则—“后来居上”：最先进栈的压在栈底，依次类推，最后进的处于栈顶。（3）出栈原则—“后进先出”（LIFO：LastInFirstOut

2、）：最后进栈的最先出栈，而最先进栈的最后出栈。（4）栈的实现方式：顺序表，称顺序栈；链表，称链栈。7.3.1栈栈的基本操作：设给定栈s=(a0，a1，……，an-1)。进栈时，最先进栈的a0压在最下面，即栈底，an-1在最上面，即栈顶。而出栈时，顺序相反，最后进栈的an-1最先出栈，而最先进栈的a0最后出栈。参见下图的顺序栈：a0an-2……a1an-1bottom压栈toptoptoptoptop退栈顺序栈的操作只与top有关，而与bottom无关!初始top与bottom同指向栈数据区的下一单元，这样会便

3、于判断空栈。7.3.1栈#include//用于诊断classStack{inttop;//栈顶（下标）DataType*elements;//指向动态建立的栈intmaxSize;//栈最大容纳的元素个数public:Stack(constint&);//构造函数，top=-1~Stack(){delete[]elements;elements=NULL;}voidPush(constDataType&);//压栈，top++DataTypePop();//弹出，top--DataType

4、GetElem(int);//随机取数据，top不变voidMakeEmpty(){top=-1;}//清空栈boolIsEmpty()const{returntop==-1;}//判栈空boolIsFull()const{returntop==maxSize-1;}//判栈满voidPrintStack();//输出栈内所有数据};顺序栈类：const成员函数,只能读类的数据成员，而不能修改类成员数据!【例7.8】顺序栈类的定义Stack::Stack(constint&maxs=20){//默认的栈大小的

5、初始值20maxSize=maxs;top=-1;elements=newDataType[maxSize];//建立栈空间assert(elements!=NULL);//假定未悬空，否则分配失败，结束程序}voidStack::PrintStack(){for(inti=0;i<=top;i++)cout<

6、s[++top]=data;//栈顶下标先加1，元素再进栈}顺序栈类的定义DataTypeStack::Pop(){assert(!IsEmpty());//栈已空则不能退栈，退出程序returnelements[top--];//返回栈顶元素，同时栈顶下标-1}DataTypeStack:GetElem(inti){assert(i<=top&&i>=0);//超出栈有效数据区，则退出程序returnelements[i];//返回指定元素，top不变}7.3.1栈intmain(){inti,a[10]=

7、{0,1,2,3,4,5,6,7,8,9},b[10];Stackistack(10);for(i=0;i<10;i++)istack.Push(a[i]);//压栈if(istack.IsFull())cout<<"栈满"<

8、<