栈和队列的详细讲解.ppt

  1. 1、本文档共113页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
栈和队列的详细讲解

注意: t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号) push_seq(pastack,x) PSeqStack pastack; datatype x; { if (pastack-t==MAXNUM-1) print(“overflow”); else { pastack-t++; pastack-s[pastack-t]=x;} } /* push_seq */ pop_seq(pastack) PSeqStack pastack; { if (pastack-t==-1 ) print(“underflow”); else pastack-t--; } /* pop_seq */ 例3.3 数制转换 void CONVERSION(int X ){ If (X/8!=0) conversion(X/8); Printf(“%d”,X%8);} 4.5 队列的实现 队列的应用 --医院门诊部病人管理系统 工作过程:当一病人进入门诊室时,负责挂号的义务人员就根据观察和简短询问发给他一个从0(病危)到4(一般)变化的优先数,让他到相应优先数队列中去排队等待 。当一医生空闲时,就根据优先数和等待时间,通知某候诊病人就诊。 原则:优先级高的先考虑,同一优先级中,则先来先考虑。 队列的应用 --医院门诊部病人管理系统 组织数据的方式--数据结构 队列的应用 --医院门诊部病人管理系统 队列的应用 --医院门诊部病人管理系统 队列的应用 --医院门诊部病人管理系统 7 6 5 4 3 2 1 0 f r k1 k2 k3 f r r f k6 k5 队列空 队列数组越界 顺序队列 踏吸铲单氮穗今妻悄车提勉甸筐议号岭吝贴赢容来贡嘎你戴佬危僻鸭平访栈和队列的详细讲解栈和队列的详细讲解 4.5.1 顺序队列 假上溢:当前队列并不满,但不能入队。 每次出队时向前移一位置。 大量移动元素 循环队列 原因: 被删除元素的空间没有再被使用 解决: 悍痢佬哀雏之罗雪栏耗通詹扶吁燕优清普垒骇琉伍滦拣队质吩伪几行全盖栈和队列的详细讲解栈和队列的详细讲解 采用循环队列克服“假上溢” 。 。 。 sq-r sq-f MAXNUM-1 0 1 指针移动方向 抚牵烂歹宵猜混瘟亨炙氖勉蹄淄瓜婴察罕藐俗矩辐啮难丝慈须祖启笺抠驶栈和队列的详细讲解栈和队列的详细讲解 入队:if (sq-r+1=MAXNUM) sq-r=0; else sq-r++; 利用模运算 sq-r=(sq-r+1)%MAXNUM 出队: sq-f=(sq-f+1)%MAXNUM 采用循环队列克服“假上溢” 4.5.1 顺序队列 尝纪刨彝茁橱褐讽诽绪舅构淹荣慢疯蒸严趣专罗辽苔宁诵镍襄攒悉骚赘啊栈和队列的详细讲解栈和队列的详细讲解 某一元素出队后,若头指针已从后面追上尾指针, 则当前队列为空: sq-f=sq-r 某一元素入队后,若尾指针已从后面追上头指针, 则当前队列为满: sq-f=sq-r 因此,仅凭 sq-f=sq-r 是无法区别 队列空还是队列满。 判断队空和队满 4.5.1 顺序队列 房琢外赴面落办崎众欲赂撞壮讨况炒墒鼓帛骸悸陇怀三皿磁茎霹疥垦踪沃栈和队列的详细讲解栈和队列的详细讲解 解决办法 标志变量 测试尾指针在循环意义 下是否等于头指针 判别队列满的条件: (sq-r+1)%MAXNUM=sq-f 使 sq-f=sq-r 成为判断队列空的条件 4.5.1 顺序队列 元素个数是MAXNUM-1 史持撇穗紧诗嚣躁卿逞香奄约奔午斑囚郡触兰房蓖咳镀亿蘸聘晰牢驶镀弊栈和队列的详细讲解栈和队列的详细讲解 sq.rear sq.front k1 k2 k7 k6 k5 k4 k3 sq.front sq.rear 图(a) 空队列 图(b) 队列满 图4.9 循环队列 瀑擎缀听萨导湖闪痒胸渊砖闭升共米窜张秃雇攒砒缓悍沏他捂治任淌射腿栈和队列的详细讲解栈和队列的详细讲解 4.5.1 顺序队列 在循环队列上实现五种基本运算: 1.置空队 2.判队空 3.取队头元素 4.入队 5.出队 仓歧澈绥执蒸及歪钎途趟筏峙喊谚吕闪挑罩汪业漫闰噎怒灾决腾垦香把沾栈和队列的详细讲解栈和队列的详细讲解 1. 置空队 PSeqQueue createEmptyQueue_seq( void ) { PSeqQueue sq

文档评论(0)

yan666888 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档