资源描述：
《数据结构第三章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列栈（Stack）队列（Queue）定义逻辑结构存储结构运算规则实现方式汉诺（Hanoi）塔:传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。xyz6463移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界末日到来!。３.１堆栈的定义3.1.1堆栈的逻辑结构堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另
2、一端称为堆栈的栈底（bottom）。特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！3.1.2堆栈的抽象数据类型ADTStack｛Dset：是一个只能从同一端插入或删除限定性的线性表（e0,e1,…,en-1）。Rset
3、：堆栈的一端（en-1）称为的栈顶（top），而另一端（e0）称为堆栈的栈底（bottom）。OPSet：｝OPSet：CreatStack()//构造空堆栈IsEmpty()//为空返回true，否则返回falseIsFull()//堆栈满返回true，否则返回falseGetTop()//返回栈顶元素Push(x)//向堆栈中压入元素Pop(x)//从堆栈中弹出元素Push()<=>insert()，即在线性表的末端插入一个元素。Pop()<=>delete(),删除最后一个元素。栈空时，若再执行pop操作就是一个错误，发生这种情况称
4、之为下溢（underflow）。栈已满，再执行压入堆栈运算，就是一个错误，称为上溢（overflow）。GetTop()返回栈顶数据元素，但不删除栈顶上的元素，相当于查找线性表的最后一个数据元素。如同线性表一样，堆栈也有顺序存贮和链式存贮两种存贮方式。在不同的存贮方式下，上述运算的执行过程是不相同的，下面就两种不同的存贮方式讨论堆栈运算的实现。3.２堆栈的顺序存储及操作3.2.1堆栈顺序存储堆栈顺序存储方式:是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保证堆栈数据元素逻辑上的有序性。堆栈占用的第一个存储单元的地址，就是堆栈的首
5、地址，也是堆栈中栈底元素（e0）存放的位置。123450ABCDEFtop=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空2.堆栈顺序存储结构定义typedefstruct{EType*element;//一维数组inttop;//指向堆栈栈顶元素intMaxSize;/
6、/可存储的最多数据元素}Stack；StackS，S1，S2；viodCreatStack(Stack&S,int&MaxStackSize){//构造一个最大容量为MaxStackSize的堆栈SS.MaxSize=MaxStackSize;S.element=newEType[S.MaxSize];S.top=-1;}堆栈栈顶指针设为-1（用户约定），即堆栈为空时，栈顶指针“指向”栈底空间的前面。3.2.2堆栈顺序存储结构下的操作2.判断堆栈是否为空或为满boolIsEmpty(Stack&S){//判断堆栈S是否为空if(S.top
7、==-1)returntrue;returnfalse;}boolIsFull(Stack&S){//判断堆栈S是否为满if(S.top>=S.MaxSize-1)returntrue;returnfalse;}4.返回栈顶元素的值StatusGetTop(Stack&S,EType&x){//返回堆栈S中栈顶元素if(IsEmpty(S))returnERROR;x=S.element[S.top];returnOK;}StatusPush(Stack&S,EType&x){//x进s栈，返回进栈后的状态值if(IsFull(S))re
8、turnERROR;S.top++;S.element[S.top]=x;returnOK;}5.进栈6.出栈StatusPop(Stack&S,EType&x){//将s栈顶的值取至x中，返
