资源描述：
《栈和队列素材说课材料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、栈和队列素材栈的特点：后进先出（LastInFirstOut，LIFO）若元素进栈顺序为a0，a1，…，an-1，则出栈顺序是an-1，an-2，…，a0，即后进栈的元素先出栈，故栈可称作“后进先出”的线性表。栈顶是唯一的出入口当栈中没有元素时，称“栈空”。若栈的存储空间已满，再作进栈操作时称“栈满溢出”。栈顶的位置随着进栈/出栈操作而发生变化栈的定义及其基本操作2栈的抽象数据类型：栈的定义及其基本操作ADTStack{数据元素集：D={ai
2、ai∈datatype,i=0,1,2,∙∙∙,n-1,n≥0}数据关系集：R={
3、ai,ai+1∈D,0≤i≤n-2
4、}约定an-1为栈顶元素基本操作集：PStackInit(&S)操作结果：创建一个空栈S。ClearStack(&S)初始条件：栈S存在。操作结果：将S清为空栈。EmptyStack(S)初始条件：栈S存在。操作结果：若S为空栈，则返回TRUE(或返回1)，否则返回FLASE(或返回0)。3栈的定义及其基本操作Push(&S,e)初始条件：栈S存在且未满。操作结果：插入数据元素e，使之成为新栈顶元素。Pop(&S)初始条件：栈S存在且非空。操作结果：删除S的栈顶元素并返回其值。GetTop(S)初始条件：栈S存在且非空。操作结果：返回栈顶元素的值。．．．．．．}ADTStack
5、;42.栈的顺序存储结构3.1栈（1）顺序栈的描述#defineMAXSIZE64//栈最大容量typedefstruct{datatypedata[MAXSIZE];//栈的存储空间inttop;//栈顶指针（或游标）}sqstack,*sqslink;//顺序栈说明符若说明sqslinkS;S=(sqlink)malloc(sizeof(sqstack))；则S指向一个顺序栈，如右图所示。栈顶元素an-1写作：S->data[S->top]栈空时S->top==-1栈满时S->top==MAXSIZE-1an-1…a1a0MAXSIZE-1S->top105（2）顺序栈基本
6、操作的实现栈的顺序存储结构1）voidClearStack(sqslinks)//置栈空{s->top=-1;}2）intEmptyStack(sqslinks)//判断栈空{if（s->top<0）return1;//栈空返回1elsereturn0;//栈非空返回0}3）intPush(sqslinks,datatypex)//x进栈{if(s->top>=MAXSIZE-1)return-1;//栈满溢出s->top++;s->data[s->top]=x;//x进栈return0;//成功}64）intPop(sqslinks,datatype*px)//出栈{if(E
7、mptyStack(s))return-1;//栈空，返回-1*px=s->data[s->top];s->top--;return0;//成功}//为简单起见，出栈操作常写成x=Pop(s)5）intGetTop(sqslinks,datatype*px){if(EmptyStack(s))return-1;//栈空，返回-1*px=s->data[s->top];return0;//成功}栈的顺序存储结构7栈的共享：栈的顺序存储结构a0……an-1空闲空间bm-1……b0S1S2S1底S->top1S->top2S2底多个栈共用一个数组可以将栈S1及栈S2的栈底分别设置在头
8、尾两端（a0,…,an-1）为栈S1中当前元素，S->top1为栈S1的栈顶指针（b0,…,bm-1）为栈S2中当前元素，S->top2为栈S2的栈顶指针82.栈的链式存储结构3.1栈（1）链式栈的描述typedefstructnode{datatypedata;//存储一个栈元素structnode*next;//后继指针}snode,*slink;a0^a1top……an-1top为栈顶指针，表示栈（a0，a1，…，an-1）。链式栈的基本操作如何实现？ClearStack,Push,Pop,EmptyStack9栈的链式存储结构（2）链式栈基本操作的实现1)Lclears
9、tack(slink*ptop)//置栈空,略去了栈非空时释放空间的操作{*ptop=NULL;}//调用方式：Lclearstack(&top);2)intLemptystack(slinktop)//判断栈空否{if(top==NULL)return1;elsereturn0;}3)Lpush(slink*ptop,datatypex)//进栈{slinkp=(slink)malloc(sizeof(snode));//生成进栈p节点p->data=x;p->next=*ptop;*pt
