资源描述：
《数据结构3栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列内容提要本课主题：栈的表示与实现，栈的应用，队列的表示与实现，队列的应用教学目的：栈的数据类型定义、栈的顺序存储表示与实现，掌握栈的应用方法，理解栈的重要作用，掌握队列的类型定义，掌握链队列的表示与实现方法教学重点：顺序栈的表示与实现，栈与递归，顺序队列的表示与实现教学难点：栈的定义，栈与递归，栈的应用，顺序队列的表示与实现3.1栈栈的由来函数调用、中断的计算机实现(P56)3.1.1栈的概念★一、栈的定义栈:限定仅在表尾进行插入或删除操作的线性表。形象的例子：仓库物流，车辆进出只有一对铁轨、一个出口的火车站，建房。典型应用：函数调用、递归调用的实现、递
2、归问题的非递归法求解、括号匹配、表达式求值、语句编译、迷宫问题求解3.1.1栈的概念栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈的特点栈的特点：后进先出(lastinfirstout,LIFO)提问：向某栈输入了三个元素，已知元素输入的先后顺序是A、B、C，那么该栈的输出序列可能有哪些？？反过来，如果输出序列是A、B、C呢？CBA,ABC,ACB,BAC,BCA，无CAB3.1.2栈的抽象数据类型定义ADTStack{数据对象:D={ai
3、ai∈ElemSet,i=1,2,...,n,n>=0}数据关系:R={
4、ai∈D,i=2,...
5、,n}基本操作:InitStack(&S)//构造一个空栈SDestroyStack(&S)//栈S存在，则栈S被销毁ClearStack(&S)//栈S存在，则清为空栈StackEmpty(S)//栈S存在，栈空则返回TRUE，否则返回FALSEStackLength(S)//栈S存在，则返回S的元素个数，即栈的长度GetTop(S,&e)//栈S存在且非空，则返回S的栈顶元素Push(&S,e)//插入元素e为新的栈顶元素，俗称推入操作或压入操作Pop(&S,&e)//删除栈顶元素并用e返回其值，俗称弹出操作StackTraverse(S,visit())//遍历
6、栈S}ADTStack★3.1.3顺序栈：栈的顺序存储及其实现1.顺序栈：利用一组地址连续的存储单元依次存放从栈底到栈顶的所有数据元素，同时附设栈底指针和栈顶指针指示栈底元素和栈顶元素的位置。顺序栈的类C语言实现2.顺序栈的类C语言实现#defineSTACK_INIT_SIZE100//注意P46页多出分号#defineSTACKINCREMENT10structSqStack{ElemType*base;//栈底指针，指向栈底元素，也即数组基地址。ElemType*top;//栈顶指针，指向栈顶元素的下一个位置(有的书上表示的是当前栈顶元素的位置)，便于判断栈空、
7、栈满和计算表长intstacksize;//栈当前可使用的最大容量。};顺序栈的类C语言实现栈底元素：*base，栈顶元素：*(top-1)栈空判断条件：top==base;或top-base==0;栈满判断条件：top-base==stacksize;栈的长度：top-base注意不同的课本上top的含义略有不同，导致判断条件也略有不同！初始化StatusInitStack(SqStack&S)//构造空栈{S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(S.base==NULL)exit(
8、OVERFLOW);S.top=S.base;//不是S.top=0或S.length=0S.stacksize=STACK_INI_SIZE;returnOK;}//InitStack插入StatusPush(SqStack&S,ElemTypee)//插入元素{if(S.top-S.base>=S.stacksize)//栈满则追加存储空间{S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(S.base==NULL)exit(OVERFLOW);S.
9、top=S.base+S.stacksize;//栈长不变，但栈顶指针会变S.stacksize+=STACKINCREMENT;}*S.top++=e;//先*S.top=e,再S.top++,使其指向栈顶下一个元素returnOK;}//Push删除StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;//一定要先判断栈是否为空栈e=*(--S.top);//先--S.top，使其指向栈顶，然后再e=*S.topreturnOK;}//Pop销毁、栈空StatusDestroyS
