数据结构-栈和队列课件.ppt

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

1、第3章栈和队列掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程栈（Stack）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式3.1栈定义只能在表的一端（栈顶）进行插入和删除运算的线性表逻辑结构与线性表相同，仍为一对一关系存储结构用顺序栈或链栈存储均可，但以顺序栈更常见运算

2、规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则实现方式关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算栈与一般线性表的区别：仅在于运算规则不同一般线性表逻辑结构：一对一存储结构：顺序表、链表运算规则：随机、顺序存取栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出栈与一般线性表的区别“进”＝压入=PUSH（)“出”＝弹出=POP()a1a2……an顺序

3、栈Sai……表头表尾栈底base栈顶top低地址高地址写入：v[i]=ai读出：x=v[i]压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！低地址高地址v[i]a1a2aian……顺序表V[n]……an+1顺序栈与顺序表顺序栈的表示空栈base==top是栈空标志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的栈顶元素之上的下标地址栈满时的处理方法：1、报错,返回操作系统。2、分配更大的空间，作为栈的存储空间,将原

4、栈的内容移入新栈。#defineMAXSIZE100typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;顺序栈的表示构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错误顺序栈初始化basestacksizetops(2)设置栈底和栈顶指针S.top=S.base;(3)设置栈大小StatusInitStack(SqStack&S){S.base=newSElemType[MAXSIZE]；if(!S.base)returnOVERF

5、LOW;S.top=S.base;S.stackSize=MAXSIZE;returnOK;}顺序栈初始化判断顺序栈是否为空boolStackEmpty(SqStackS){if(S.top==S.base)returntrue;elsereturnfalse;}basetop3120求顺序栈的长度intStackLength(SqStackS){returnS.top–S.base;}basetopABStatusClearStack(SqStackS){if(S.base)S.top=S.base;returnOK;}清空顺

6、序栈basetop3120StatusDestroyStack(SqStack&S){if(S.base){deleteS.base;S.stacksize=0;S.base=S.top=NULL;}returnOK;}销毁顺序栈(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1顺序栈进栈StatusPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize)//栈满returnERROR;*S.top++=e;returnOK;}*S.top=e;S.top

7、++;ABCtopbase(1)判断是否栈空，若空则出错(2)获取栈顶元素e(3)栈顶指针减1顺序栈出栈StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)//栈空returnERROR;e＝*--S.top;returnOK;}--S.top;e=*S.top;ABCtopbase判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;/

8、/栈空e=*(S.top–1);returnOK;}e=*(S.top--);???ABCtopbase435612中到了12顺序不能实现；135426可以实现。1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？练习练习Ａ．i