第2章-3栈.

2019/12/2012.2栈和队列2019/12/2022.2.1栈(Stack)栈(stack)是限制线性表中元素的插入和删除，只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。an...a2a1栈顶TOP栈底Bottom2019/12/203栈(Stack)根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。2019/12/204栈的插入与删除进栈出栈进栈---最先插入的元素放在栈的底部。出栈---最后插入的元素最先退栈。an...a2a1栈顶TOP栈底Bottom2019/12/205栈的基本运算置空栈:Init_Stack()——初始化判空栈IsEmpty_Stack(S)进栈:Push_Stack(S,x)——插入操作出栈:Pop_Stack(s,x)——删除操作取栈顶元素:GetTop_Stack(s)2019/12/206顺序栈：栈的顺序结构顺序栈：用向量定义（类似于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。顺序栈的定义：#defineMaxSize1024Typedefstructstack{elemtypedata[MaxSize];inttop;}SqStack;/*顺序栈类型定义*/2019/12/207顺序栈A321032103210TOPA进栈DCBA3210BA3210Top=-1，B、A退栈Top=-1空栈B、C、D依次进栈D、C依次退栈TOPTOP2019/12/208顺序栈主要运算栈底位置固定在向量的低端，即：S-data[0]——表示栈底元素；进栈：S-TOP加1（正向增长）。出栈：S-TOP减1。空栈：s-top=-1栈满：S-TOP=maxsize-1上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。下溢：栈空时再做出栈运算将产生溢出，这是一种正常状态（因为栈的初态和终态都是空栈，下溢常用作程序控制转移的条件）。2019/12/209顺序栈的几种基本运算例置空栈：//也可以认为是初始化SqStack*Init_SqStack()//将顺序栈S置为空{SqStack*ss=(SqStack*)malloc(sizeof(SqStack));s-top=-1;returns;}2019/12/2010判栈空intIsEmpty_SeqStack(SqStack*S)//判定顺序栈S是否为空{if(s-top==-1)return1;//栈空elsereturn0;}2019/12/2011进栈：intPUSH_SeqStack(SqStack*S,Elemtypex){if(s-top==maxsize-1){printf(“上溢\n”);return0;}else{s-top++;//先指向一个空的存储单元s-data[s-top]=x;//再放入数据元素return1}}2019/12/2012出栈intPop_SeqStack(SqStack*S,elemtypex){if(IsEmpty_SeqStack(S)){printf(“下溢”\n);return0;}else{x=s-data[s-top];s-top--;//top指向新的栈顶元素return1;}}2019/12/2013取栈顶元素elemtypeTop_SeqStack(SqStack*s){if(IsEmpty_SeqStack(s)){printf(“underflow\n”);return0;}elsereturn(s-data[s-top]);}//取栈顶元素并不修改栈顶指针2019/12/2014两个堆栈共享空间共享空间顺序栈示意图共享顺序栈的定义：#defineMaxSize100Typedefstructstack{elemtypedata[MaxSize];inttop1,top2;}SharedStack;/*顺序栈类型定义*/0maxsize-1S-Top1S-Top2…………2019/12/2015共享顺序栈的判空s-top1==-1和s-top2==MaxSize共享顺序栈的判满s-top1+1==s-top22019/12/2016共享顺序栈的初始化SharedStack*InitSharedStack(){SharedStack*s;s=(SharedStack*)malloc(sizeof(stack));s-top1=-1;s-top2=MaxSize;returns;}2019/12/2017共享顺序栈的插入与删除插入左边的栈：s-top1++;s-data[s-top1]=x;右边的栈：s-top2--;s-data[s-top2]=x;删除左边的栈：x=s-data(s-top1)s-top1--;右边的栈：x=s-data(s-top2)s-top2++;2019/12/2018插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈无栈满问题，空间可扩充当栈的最大容量事先无法估计时，可采用链栈结构栈的链式存储结构2019/12/2019链栈的特点插入和删除(进栈/退栈)仅能在表头位置上(栈顶)进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针top就是链表(即链栈)的头指针。2019/12/2020栈的链式存储结构链栈的逻辑示意图TOPdata……栈顶链栈结点的定义#defineLinkStackstructlinkstackLinkStack{elemtypedata;LinkStack*next;};2019/12/2021链栈的初始化LinkStack*Init_LinkStack(){LinkStack*top;top=(LinkStack*)malloc(sizeof(LinkStack));top=NULL;returntop;}//top==NULL作为链栈判空的条件2019/12/2022链栈的插入(push)操作LinkStack*Push_LinkStack(LinkStack*top,elemtypex){LinkStack*s;s=(LinkStack*)malloc(sizeof(LinkStack));s-data=x;s-next=top;top=s;returntop;}//链栈一般不需要判满2019/12/2023链栈的删除(pop)操作LinkStack*Pop_LinkStack(LinkStack*top,elemtype*x){LinkStack*p;if(top==NULL)//链栈空的条件{printf(“underflow\n”);returnNULL;}else{*x=top-data;p=top;top=top-next;free(p);returntop;}}2019/12/2024链栈的小结顺序栈会发生上溢，而链栈通常不会发生栈满（除非整个空间均被占满）。因此，链栈的PUSH操作不需要判满。链栈删除时仍然需要判空；只要满足LIFO原则，均可采用栈结构。2019/12/2025栈的举例例：一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB2019/12/2026栈的应用临时存储区域子程序调用表达式求值……2019/12/2027栈的应用—递归函数intFACT(intn){if(n==1)return(1);elsereturn(n*FACT(n-1));}2019/12/2028数制转换十进制数N和其他D进制数的转换是计算机实现计算的基本问题，解决办法好多，其中一个简单算法下列原理：N=(Ndivd)*d+Nmodd(mod为求余)例如(1348)₁₀=(2504)₈NNdiv8Nmod81348168416821021252022019/12/2029数制转换从转换过程可知首先得到的是结果数据的最后一位，而最后得到的是结果数据的第一位。如果按转换过程把所得每位进栈，那么从栈中退出便为最终结果。2019/12/2030数制转换算法voidconversino()//输入非负十进制整数，输出等值八进制数{InitStack(s);//形成空栈sscanf(“%d”,N);//读入十进制整数Nwhile(N){push(S，N%8);//将余数进栈Nmod8N=N/8;}//Ndiv8得到的商，作为下次的Nwhile(!IsEmpty(s))//当栈不空时，执行退栈{pop(S,e);//将栈顶数据退出，存储到E中printf(“%d”,e);//打印输出E}}