资源描述：
《数据结构.第3章.栈和队列.1.栈课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日队列类型的定义和实现第3章栈和队列栈的类型定义栈的应用举例栈类型的实现§3.1栈的类型定义§3.1栈的类型定义§3.1栈的类型定义栈示意图§3.1栈的类型定义a1a2a3an栈顶栈底……栈的相关概念§3.1栈的类型定义1.定义与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。3.存储结构4
2、.运算规则5.实现方式2.逻辑结构限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）栈与一般线性表有什么不同§3.1栈的类型定义栈与一般线性表的区别：仅在于运算规则不同。一般线性表栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝压入=PUSH（x)“出”＝弹出=POP(y)栈的相关概念§3.1栈的类型定义栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶Top；表头(即a1端)称为栈底Base例如：
3、栈s=(a1,a2,a3,……,an-1,an)a1称为栈底元素an称为栈顶元素插入元素到栈顶(即表尾)的操作，称为入栈。从栈顶(即表尾)删除最后一个元素的操作，称为出栈。思考题一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。§3.1栈的类型定义A）edcbaB）decbaC）dceabD）abcde栈的抽象数据类型定义§3.1栈的类型定义ADTStack{数据对象：D={ai
4、ai∈ElemSet,i=1,2,...,n)数据关系:R={
5、ai-1,ai∈D,i=2,.
6、..,n)约定an端为栈顶，a1端为栈底基本操作：InitStack(&S)操作结果：构造空栈SDestroyStack(&S)初始条件：栈S已存在操作结果：销毁栈SClearStack(&S)初始条件：栈S已存在操作结果：将S置为空栈StackEmpty(S)初始条件：栈S已存在操作结果：判别栈S是否为空栈StackLength(S)初始条件：栈S已存在操作结果：返回栈S中元素个数(栈长)GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push(&S,e)初始条件：栈S已存在
7、操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在操作结果：删除S的栈顶元素，用e返回值}ADTStack栈的物理存储栈的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，栈的存储方式也分为两种，即顺序栈和链栈。§3.2栈的表示和实现顺序栈的定义§3.2栈的表示和实现#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//base的初
8、值为NULL，表明栈结构不存在SElemType*top;//栈顶指针，初值指向栈底，//即top=base作为栈空的标记intstacksize;//当前已分存储空间，即指示当前栈//可使用的最大容量，以元素为单位}SqStack;栈顶指针和栈中元素之间的关系§3.2栈的表示和实现1）空栈中的栈顶指针的指向和栈底指针一致2）非空栈中的栈顶指针始终在栈顶元素的下一个位置AABCDABbasetopbasetopbasetopbasetop栈在抽象类型中的几种操作举例§3.2栈的表示和实现例1：构造一个空栈St
9、atusInitStack(SqStack&s){//构造一个空栈Ss.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));If(!s.base)exit(OVERFLOW);//存储分配失败s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack;栈在抽象类型中的几种操作举例§3.2栈的表示和实现例2：取栈顶元素StatusGetTop(SqStacks,SElemtype&
10、e){//若栈不空，用e返回S的栈顶元素if(s.top==s.base)returnERROR;e=*(s.top-1);//操作后s.top不变，并将当前栈顶元素赋给ereturnOK;}//GetTop;等同于删除栈顶元素（出栈），区别在于：e=*--s.top;//操作后stop减１，并将当前出栈的元素赋给etopbaseACBDbasetoptop-1e=D栈在抽象类型中的几种操作举例§3
