资源描述：
《冯毅《数据结构》ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实例栈队列下一章第三章栈和队列1、停车场特点后进先出，便道特点先进先出2、如何存储3、数据操作：进场，出场停车场管理RailwaySwitchingNetwork12341、其特点是先进先出2、如何存储3、数据操作：到达，离开，求队长等银行业务模拟栈和队列是两种特殊的线性表是操作受限的线性表，称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表线性表栈队列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栈和队列是两
2、种常用的数据结构a1a2a3………….an入队出队frontrear队列Q=(a1,a2,……,an)ana1a2……......出栈进栈栈s=(a1,a2,…,an)栈（stack）栈的逻辑结构栈的存储结构栈的应用栈的逻辑结构栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶(top)，表头—栈底(bottom)，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的运算：置空栈取栈顶元素判空栈进栈退栈ADTStack{数据对象：D＝
3、{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的抽象数据类型定义基本操作：InitStack(&S)操作结果：构造一个空栈SDestroyStack(&S)初始条件：栈S已存在操作结果：栈S被销毁StackEmpty(S)初始条件：栈S已存在操作结果：空栈，返回TRUE;否则FALSEStackLength(S)初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度ClearStack(&S
6、)初始条件：栈S已存在操作结果：将S清为空栈栈的抽象数据类型定义基本操作：GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse(S,visit())初始条件：栈S已存在且非空操作结果：依次对S的每个元素调用函数visit()栈的抽象数据类型定义双栈ana1a2……...栈顶...出栈进栈...栈顶出栈进栈超栈ana1a2……...栈顶
7、...出栈进栈...栈顶出栈双栈与超栈栈的存储结构顺序栈链栈实现：用一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450入栈Atop出栈栈满BCDEFtoptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空s[top++]=xx=s[--top]存在问题：1、栈容量难以扩充2、没有体现top与栈内在联系栈的顺序存储结构——顺序栈/*定义动态顺序栈*/typedefintSElemType;#defineSTACK_INIT_SIZE100//顺序栈存储空间
8、的初始分配量#defineSTACKINCREMENT10//顺序栈存储空间的分配增量typedefstruct{SElemType*base;//存储空间基址,栈底指针SElemType*top;//栈顶指针intstacksize;//当前分配的存储容量}SqStack;123450baseABCtop栈的顺序存储结构——顺序栈SqStackS;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)ex
9、it(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}顺序栈结构初始化：算法时间复杂度：O(1)栈容量stacksize=STACK_INIT_SIZE栈底指针top栈顶指针stacksize-110topbasebase栈的基本操作在顺序栈中的实现StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}取栈顶元素：123450baseABCDtop算法时
10、间复杂度：O(1)栈的基本操作在顺序栈中的实现StatusPop(SqStack&S,SElemType&e){if(S.
