3栈与队列(本硕博与信工).ppt

《3栈与队列(本硕博与信工).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十一章堆栈与队列（一）引入栈和队列1234栈和队列是操作受限的线性表栈和队列是操作受限的线性表；通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型主要内容堆栈的概念及其运算栈的抽象类定义栈的定义及其实现堆栈的应用举例11.1堆栈的概念及其运算堆栈的定义堆栈的特点堆栈的示意图堆栈

2、的有关运算堆栈的定义堆栈是一种只允许在表的一端进行插入和删除运算的线性表；允许进行运算的一端称为栈顶，另一端则称为栈底；当表中没有元素时，称为空栈；堆栈的插入运算简称为入栈或进栈，删除运算简称为出栈或退栈。出栈进栈栈的示意图栈顶栈底ana2a1堆栈的特点出栈进栈栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素栈的示意图栈顶栈底ana2a1堆栈的有关运算进栈运算：在堆栈的顶端插入一个新元素，相当于在线性表最后的元素之后再插入一个新元素；出栈

3、运算：删除栈顶的元素，在实际应用中，经常要用到栈顶元素。所以，栈顶元素一般应先保存，再删除栈顶结点；清栈运算：用来将栈清空；测试栈空：测试当前栈是否为空，栈空时，不能进行出栈运算。下溢；测试栈满：测试当前栈是否为满，栈满时，不能进行入栈运算。上溢。11.2栈的抽象类定义template//定义一个抽象的模板堆栈类classabstack{public:boolIsEmpty()//判断堆栈是否为空{return(height==0)?true:false;}//进栈函数，将一元素压入

4、栈中virtualvoidPush(type&)=0;//出栈函数，从栈中取一元素virtualboolPop(type&)=0;//清栈函数，用于释放栈所占的内存空间virtualvoidClear()=0;protected:unsignedheight;};//栈高（1）抽象栈类中定义了栈高height，可简化操作，例如判断栈空、栈满。height在abstack类中为protected，它的派生类可以访问它。在抽象栈的数据成员中没有栈顶指针，因为顺序栈和链栈的栈顶指针具有不同的数据类型，顺序栈(整

5、型)、链栈(指针型)；（2）根据栈的常用操作，在abstack类中定义了4个函数，其中3个是纯虚函数，其实现与栈的存储结构有关，因此在派生类中给出其定义。IsEmpty();判定堆栈是否为空或栈高是否为0；Push(type&);将type类型的数据元素插入到栈顶；Pop(type&);将栈顶元素弹出并赋给type类型的元素；Clear();将堆栈清空。抽象栈类说明：11.3栈的定义及其实现顺序栈的定义顺序栈类的定义及典型成员函数的实现多栈共享空间问题顺序栈的定义设一维数组为STACK[maxsize];

6、再设一个整型变量top表示栈顶指针：当堆栈不空时，top的值就是栈顶元素的下标值；当堆栈为空时，有top=-1；top最大取值为maxsize-1。STACK[0]为第一个进入堆栈的元素，当没有删除运算时，STACK[i-1]为第i个进入堆栈的元素，STACK[top]为栈顶元素topABM-1…210SATCK顺序栈的示意图toptopABCDE空栈topAA进栈BCDE进栈topABEDC出栈称为：栈满顺序栈的定义堆栈是动态结构，存在溢出问题。当堆栈中已经有M个元素时，如果再做进栈运算就会产生溢出，称

7、之为上溢；对空栈进行删除运算也会产生溢出，称之为下溢。为了避免溢出，在对堆栈进行进栈运算和退栈运算之前都应该分别测试堆栈“是否已满”或者“是否已空”。顺序栈类的定义template//定义一个顺序栈类模板classSeqStack:pubilcabstack{public:SeqStack(inti);//构造函数，i用来设置栈的最大高度SeqStack(SeqStack&s)//拷贝构造函数，用于同{copy(s);}类型栈的赋值~SeqStack()//析构函数，调用

8、Clear()函数释放栈所{Clear();}占的内存空间voidPush(type&x);//进栈:将元素x压入栈中boolPop(type&x);//出栈:将栈顶元素值放入x中//清栈函数，用于释放栈所占的内存空间voidClear(){deleteelements;}SeqStack&Copy(SeqStack&s);//拷贝函数:同类型栈赋值//重载赋值运算符“＝”，用于同类型栈赋值SeqStack&operator=