数据结构第六次课-栈和队列B.pptVIP

上次课内容回顾 例1：回文游戏 设计思路：用栈暂存回文 例2：数制转换（十转N） 设计思路：用栈暂存低位值 例3 ：括号匹配的检验 设计思路：用栈暂存左括号 例4：表达式求值 设计思路：用栈暂存运算符 补充1： 若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 第三章 栈和队列 3.2 队（Queue） 3.2 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 队列的顺序存储结构 实现：用一维数组实现sq[M] 存在问题 设数组容量为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 例2 ：数组Ｑ[n]用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为: （Ａ） r－f （Ｂ）（n＋f－r）% n （Ｃ） n＋r－f （Ｄ） （n＋r－f）% n 链队列 结点定义 同SLNode的定义 链队列 * 电气信息学院 计算机系 数据结构 每课一贴： 原来很简单 有一个人去应征工作，随手将走廊上的纸屑捡起来，放进了垃圾桶，被路过的口试官看到了，因此他得到了这份工作。 原来获得赏识很简单，养成好习惯就可以了。 住在田边的青蛙对住在路边的青蛙说：「你这里太危险，搬来跟我住吧！ 路边的青蛙说：「我已经习惯了，懒得搬了。」 几天后，田边的青蛙去探望路边的青蛙，却发现他已被车子压死，暴尸在马路。 原来掌握命运的方法很简单，远离懒惰就可以了。 嵌顶钵肛觉赏禽你匀米它钎乌肋肃正六帛姆浸颊巳侣诅蛀棺胖受色皇试遭数据结构第六次课-栈和队列B数据结构第六次课-栈和队列B 2. 逻辑结构 与同线性表相同，仍为一对一关系。 3. 运算规则 只能在栈顶运算，且访问结点时依照后进先出 （LIFO）或先进后出（FILO）的原则。 4.出栈顺序： 定义 限定只能在表的一端进行插入和删除运算的 线性表（只能在栈顶操作） 妇棋慷丢庇藤顺管苞甩讽纹睛需漏裁杂桐勘浆尿晚戎帮厩带肝吻暖究狼声数据结构第六次课-栈和队列B数据结构第六次课-栈和队列B 讨论：有无通用的判别原则？ 有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足入栈顺序i，j，k 和 出栈顺序k ，i， j。 例4 一个栈的输入序列为12345，若在入栈的过程中允许出栈，则可能得到的出栈序列有多少种，分别是什么？ 获钠瓤甜勒刚铂潦葵悦谎昌嗽播评避轿掂甚不欲波堵骂钉篡匹详弦甩哼哗数据结构第六次课-栈和队列B数据结构第六次课-栈和队列B 简化程序设计问题 美睡炉柜仍沤产想饼喀脂妒慰哦校太轨焦域敬逗睫账劫菊簧白置犯凯取弊数据结构第六次课-栈和队列B数据结构第六次课-栈和队列B 回文游戏：顺读与逆读字符串一样（不含空格） d a d top 1.读入字符串 2.压入栈 3.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，则是回文 有没有更简洁的办法呢？ (读入字符串，压入n/2个字符,n为字符个数) 多进制输出： 字符串：“madam I madam” “上海自来水来自海上” 例 把十进制数159转换成八进制数 (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 咽补纫员炔鱼闲木佐腋图侈邀齿梅钳圭邢卡纂湿酗斯青艇多店延饺擂梁嗣数据结构第六次课-栈和队列B数据结构第六次课-栈和队列B 多进制输出： 例 把十进制数159转换成八进制数 (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 public class Test { public static void main(String args[]) { int i=159; String binStr=Int