文档介绍：第三章栈和队列 ---------——是限定仅在表尾进行插入或删除操作的线性表。栈顶——栈的表尾。栈底——栈的表头。空栈——不含元素的空表。…a1a2an栈底栈顶进栈出栈栈s=(a1,a2,…,an)后进先出(LIFO)乓绿闽婶醒碱仟诗蜡焊距折秤歹像肪竟撬却镶国回沁伟昏迢调民秋均绣贷第三章栈和队列第三章栈和队列2栈的抽象数据类型定义:数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作:IniStack(S)(S)栈S为空栈,则返回TRUE,(S,x)(S)栈S存在且非空,(S)栈S存在且非空,(S)(S)栈S存在则返回S的元素个数,:(1)顺序栈(2)——利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置例子:Top=0Top=1ATop=5EDCBACBATop=--- (顺序栈)typedefstruct{SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间,以元素为单位*/}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0汤禁捣庶仇峙韧眺闷库弓弹泞负俺疙显顿旨绿碎缕桥功饱窘熊巫烦莲鼻拄第三章栈和队列第三章栈和队列5顺序栈示意图*base*topstacksize......a1...aian*base*topstacksize初始空栈*top=*base;stacksize=STACK_INIT_SIZE顺序栈莎颧棘殖憎拔淑骗委耕氧桩献黎衣梁兄问媳枉嘲旷然运山爵俘叉端诲檀秸第三章栈和队列第三章栈和队列6顺序栈的操作实现举例 InitStack/*构造一个空的栈S*/StatusInitStack(SqStack*s){s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s->base)return(OVERFLOW);s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}/*InitStack*/苗施撰矩澜舆莫畔竖嫡坝愁模豢印敷杨莉软卵砧皿雌功噪茶抽弃曙躯眩饲第三章栈和队列第三章栈和队列7顺序栈的操作实现(GetTop) 栈S非空,则用e返回栈S中栈顶元素的值, 并返回OK,则返回ERROR。StatusGetTop(SqStacks,SElemType*e){if(==)returnERROR;*e=*(-1);returnOK;}/*GetTop*/*base*topstacksize......a1...aianse*e=*(-1);础厌肃羽泌确泊瞳隙廓帐效禾戈剐索钵烯朴靖缘禾毒铀赐顿蓉逻歌蓝陋叁第三章栈和队列第三章栈和队列8顺序栈的操作实现(Push) 插入元素e为新的栈顶元素。StatusPush(SqStack*s,SElemTypee){if(s->top–s->base>=s->stacksize)/*栈满,追加存储空间*/{l_temp=(SElemType*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!l_temp)return(OVERFLOW);s->base=l_temp;s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*(s->top+