资源描述：
《栈和队列（第1讲）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列第三章栈和队列3.1栈3.2栈的应用举例3.3*栈与递归3.4队列栈和队列是两种重要的线性结构栈和队列是操作受限的线性表出进排队买票羊肉串出如何理解？进栈队列3.1栈3.1.1栈的概念3.1.2栈的顺序存储和实现3.1.3栈的链式存储和实现学习要点1理解掌握栈的结构特征和操作特点；2掌握栈的顺序存储结构和链式存储结构，以及如何用C语言描述它们的类型定义；3掌握在两种存储结构下，栈的基本操作的算法；重点掌握顺序存储结构栈的基本操作的算法；4理解栈的后进先出的特点及在程序设计中的应用.基本内容1栈的概念，栈的基本操作； 2栈的两类存
2、储结构和它们的类型定义； 3在栈的存储结构下，栈的基本操作的算法； 4栈在程序设计中的应用。栈是限定仅能在表尾一端进行插入、删除操作的线性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除一、什么是栈3.1.1栈的概念5）由于进栈、出栈操作总是在栈顶一端进行，通常设置栈顶指针变量指示栈顶的位置。说明：1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素；2）在表尾插入元素的操作称进栈操作，删除元素的操作称为出栈操作;3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一
3、定在栈顶,第一个出栈的元素为栈顶元素；4）栈的元素具有后进先出的特点，所以栈又称为后进先出表（LIFO表）；出栈进栈a1a2an...表头表尾栈底栈顶栈的抽象数据类型的定义InitStack(&S)结果:构造一个空栈S。数据对象:D={ai
4、ai∈ElemSet，i=1,2,…,n}数据关系:R1={}；约定a1为栈底，an为栈顶。基本操作:ADTStack{}ADTStackDestroyStack(&S)结果:销毁栈S。条件:栈S已存在。…功能：若栈S为空，则返回True；否则，返回False。栈的基本操作1） 初始化操
5、作InitStack((&S)功能：构造一个空栈S。2）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈。3）置空栈操作ClearStack(&S)功能：将栈S置为空栈。4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回5）进栈操作Push(&S,e)功能：元素e进栈。6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回7）判空操作StackEmpty(S)栈的顺序存储结构也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素。顺序栈3.1.2栈的顺序存储和实现一、栈的顺序存储结构baseto
6、p栈底指针——base栈顶指针——topABC栈容量注意!指向栈底元素指向栈顶元素的上一个元素顺序栈的类型定义#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base；SElemType*top；intstacksize；}SqStack；SqStackS；S.baseS.topS.stacksize顺序栈的图示anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEnn-1i-1i-210空栈ABCS.b
7、aseS.topDE满栈S.baseS.top如何判定?S.top==S.baseABCS.baseS.top栈中有三个元素SqStackS如何判定?S.top-S.base==S.stacksize当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？功能：建一个空栈S。二、顺序栈基本操作的算法1、初始化操作InitStack((SqStack&S)参数：S是存放栈的结构变量。…nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZES.base=(SElemType*)malloc
8、(STACK_INIT_SIZE*sizeof(SElemType))；if(!S.base)exit(OVERFLOW)；S.top=S.base；S.stacksize=STACK_INIT_SIZE；returnOK；StatusInitStack(SqStack&S){}2、销毁栈操作DestroyStack(SqStack&S)功能：销毁一个已存在的栈。nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE销毁前S.top=NULLS.stacksizeS.base
9、=NULL0销毁后算法:StatusDestroyStack(SqStack&S){if(!S.base)returnERROR;//若栈未建立（尚未分配栈空间）f
