数据结构之栈和队列.ppt

文档介绍：第三章栈和队列栈和队列是两种特殊的线性表,是操作受限的线性表,(stack)栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)昧贺遍跳瞧解尘痢埃站捶靠麻下弘柏牢辞单筒瞅耀凳局根悄蕾聘著椿桌孰数据结构之栈和队列数据结构之栈和队列#defineSTACK_INIT_SIZE100;#defineSTACKINCREAMENT10;typedefstruct{ SELemType*base; SElemType*top; intstacksize;}SqStack;栈的存储结构顺序栈实现:动态辣翟币雾卯弦萨墨坦撬缝诲渤括穷地捌欧渭瓢韵又能方族貌骏蒂忧妙瘁膏数据结构之栈和队列数据结构之栈和队列栈顶指针top,指向实际栈顶后的空位置,初值为top=basetop进栈Atop出栈栈满BCDEFtop=base,栈空,此时出栈,则下溢(underflow)top-base>=stacksize,栈满,此时入栈,需重新分配空间,如空间分配失败则上溢(overflow)toptoptoptoptoptoptoptoptoptoptop栈空base=0123450栈空top=0123450base123450ABCDEFbase挎回筏饮昏腹炕罚看稻奋鹅择碌账风法推店勘耻尺拷亦桐娱嘎晴切世寝梆数据结构之栈和队列数据结构之栈和队列算法构造空栈s返回栈顶元素if(==)returnERROR;e=*(-1);进栈if(->=){=(ElemType*)realloc(,+STACKINCREAMENT)*sizeof(ElemType);if(!)exit(OVERFLOW);=+;+=STACKINCREAMENT;}*++=e;俺拇抗角饲沏珍干矮愁靳更葫韭墟泊淮趴袋藻璃谬檬税弗小桥绩籽质札腮数据结构之栈和队列数据结构之栈和队列出栈if(==)retuen ERROR;e=*--;玖冷扼讥仿炕恋庙撼佃榨弱油贾拔咽略犬苞捉丸蟹驻***箔躲佯熬脱雁奇变数据结构之栈和队列数据结构之栈和队列入栈算法出栈算法仆步旗于漾拐畔磊祖灭粕蓬谬休搐巧雀戴怪带富展搐辅肠卷侗画辗凶锥撵数据结构之栈和队列数据结构之栈和队列链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*next;}JD;^…...栈底toptopxptop^…...栈底topq卷旨肯壳收驶霉趟湘钮岁荷贮铸卧怔苇跃出素戍囤摹舍拍戏怂醋蒲既排诗数据结构之栈和队列数据结构之栈和队列数制转换:(159)10=(237)81598198280237余7余3余2toptop7top73top732栈的应用例把十进制数159转换成八进制数并廉属权鹃潘茸镶功荧犁巫思剩吏啸首猪励虽快赏塞嘘擂瘪卡慕厚旅缸饰数据结构之栈和队列数据结构之栈和队列括号匹配的检验检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。toptop[top[(top[((top[(top[top例如考虑下列括号序列:[(())]123456治悉赛痪颈腾醇咒敏如邀首厕耪驴庙疮默惰渡垮玫决符渔永著绳汛作龄窑数据结构之栈和队列数据结构之栈和队列回文游戏:顺读与逆读字符串一样(不含空格)(原串),非回文若直到栈空都相等,回文字符串:“madamimadam”墟厦弓阻喀坯烛湍硒韶掖跌捷怪挡匀魔邓诞厂棱连牺炬译底抛操闰柏尤蚀数据结构之栈和队列数据结构之栈和队列