《堆栈和队列》ppt课件

《《堆栈和队列》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章限定性线性表——堆栈和队列3.1堆栈3.2堆栈应用3.4*优先级队列栈和队列是两种重要的抽象数据类型，是一类操作受限制的特殊线性表，其特殊性在于限制插入和删除等运算的位置。3.3队列13.1堆栈3.1.1堆栈的基本概念堆栈的定义：限定只能在固定一端进行插入和删除操作的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈又称为后进先出的线性表，即LIFO。2根据栈定义，每次进栈的元素都

2、被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：进栈、出栈图例进栈出栈ana2a1进栈出栈栈顶栈底3例3-1利用一个堆栈，如果输入系列由A、B、C组成，试给出全部可能的输出系列和不可能的输出系列。输出系列有：ABC、ACB、BAC、BCA、CBA不可能的输出系列为：CAB43.1.2栈的抽象数据类型定义数据元素集合：描述为{a0,a1,…,an-1}，ai的数据类型为DataType。关系：栈中数据元素之间是线性关系。基

3、本操作：(1)Initiate(S)初始化堆栈S(2)Push(S,x)入栈(3)Pop(S,d)出栈(4)GetTop(S)取栈顶数据元素(5)NotEmpty(S)堆栈S非空否53.1.3栈的表示和实现——顺序堆栈类栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。61.顺序堆栈的存储结构顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在

4、顺序栈中的位置。通常以top=0表示空栈。其结构如图所示：a0a1a2a3a4stack栈底栈顶MaxStackSize-1012345=top其中，a0,a1,a2,a3,a4表示顺序堆栈中已存储的数据元素，stack表示存放数据元素的数组，MaxStackSize-1表示最大存储单元个数，top表示当前栈顶存储下标。7classSeqStack{private:DataTypedata[MaxStackSize];//顺序堆栈数组inttop;//栈顶位置指示器public:SeqStack(void){top=0;}//

5、构造函数~SeqStack(void){}//析构函数voidPush(constDataTypeitem);//入栈DataTypePop(void);//出栈DataTypeGetTop(void)const;//取栈顶数据元素intNotEmpty(void)const//堆栈非空否{return(top!=0);}};2.顺序堆栈类的定义和实现8voidSeqStack::Push(constDataTypeitem)//入栈//把元素item入栈;堆栈满时出错退出{if(top==MaxStackSize){cout

6、<<"堆栈已满!"<

7、cout<<"堆栈空!"<#includeconstintMaxStackSize=100;//定义问题要求的元素数目的最大值typedefintDataType;//定义具体问题元素的数据类型#include"seqstack.h"3.顺序堆栈类的测试voidmain(void){SeqStackmyStack;//构造函数无参数时，定义的对象后不带括号Dat

8、aTypetest[]={1,3,5,7,9};intn=5;for(inti=0;i