《队列及其实现.ppt》由会员分享，可在线阅读，更多相关《队列及其实现.ppt（35页珍藏版）》请在三一文库上搜索。
1、Houfeng Wang, ICL of PKU,1,队列及其实现,愚健竭茸粮驰腋颠拉辅奋顾广弟辈捂盆娱境景释店桐布败颂崇晒馏诬狞鸥队列及其实现队列及其实现,排队上车,聘度欺朝缀亢悸语河氖恿哨淌闭腮令专挖彰漾鹃修棕娃妻也诺硕日态且皮队列及其实现队列及其实现,排队上车,阎坏裙贼酥铂毗嫂伺柞补婚垦茁叔攫戈星揭奔牺命嫡僳在来内肿恍歇貉更队列及其实现队列及其实现,Bus Stop Queue,付早范伪姐法尉绅心娄集假蟹碉跳狈我西声菱腋翌栗宣育霍舶师跃争戴氯队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,5,队列的特点,队列也是一种特殊的线性表，是一种只允许在表的一端进行插入
2、操作，而在另一端进行删除操作的线性表。允许进行删除的这一端叫队列的头，允许进行插入的这一 端叫队列的尾。当队列中没有任何元素时，称为空队列。 队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。,竖挤其敷砧弗幌扶腊皱僧囤毅翱孜区鲜堤亲腊锨纸舟吻丹涅宙嫌镶筐舔尤队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,6,队列也称作先进先出表(First In First Out表，简称FIFO表）图4.7是队列的示意图,昧畅久怀违冷檬坍神汕慕书摧较伶赦蒸计胞哲轿踏谨牺盾综浆捅丝奏膘微队列及其实现队列及其实现,Houfeng Wang, ICL of P
3、KU,7,队列的基本运算,1. Queue createEmptyQueue ( void ) 创建一个空队列2. int isEmptyQueue ( Queue qu ) 判队列qu是否为空队列，当qu为空队列时取真值，否则取假值 3. void enQueue ( Queue qu, DataType x ) 往队列qu中插入一个值为x的元素4. void deQueue ( Queue qu ) 从队列qu中删除一个元素 5. DataType frontQueue ( Queue qu ) 求队列qu头部元素的值,夸馅稻滇轧长融脸恿届牺眷淡锑状纫提邵诞荫眉吐便屁雨厌铭呵君隆忍题队列及
4、其实现队列及其实现,Houfeng Wang, ICL of PKU,8,队列的实现,吭槛朱插猛纪骸问欺洗况辫炼寒笋梗扦窒哭穿酞浮砷堵福笼市纪恼面砒曹队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,9,顺序表示,队列的顺序表示，约定：队头指针指出实际队头元素所在的位置，而队尾指针指出实际队尾元素所在位置的下一个位置。 结构定义： #define MAXNUM / 队列中最大元素个数struct SeqQueue/ 顺序队列类型定义 DataType qMAXNUM; int f,r; /f 指向队列头，r 指向队列尾 ;typedef struct SeqQueue
5、 *PSeqQueue; /* 顺序队列类型的指针类型 */,辜拥焙馋拟没胎崔出赞拦鲸拖纂赌崎仓下御贱忠曼埃翁令售捌耕疹糜坏铜队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,10,设paqu是PSeqQueue类型的变量，则头变量paqu-f存放即将要被删除的元素的下标，尾变量paqu-r存放即将要被插入的元素（当前还不是队列中的元素）的下标。 初始时paqu-f = paqu-r = 0。 队列中元素的个数可以用paqu-r - paqu-f计算得到，当paqu-r = paqu-f时，元素的个数为0，即为空队列。 例子：观察变化过程,约定,靛巩鸿檄屈唆夏测鸵坷眺
6、无巾捆玛淑狭鸦羡粪币堡汤墩侮戌亚蓝肿纤藉遂队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,11,鉴此齐元戒徊愉铡沈歼嘱悦召即彦娇逊完逛胞鱼阔炊礁申形愧哑版批骡悔队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,12,基本运算,PSeqQueue createEmptyQueue_seq( void )创建一个空队列，返回指向空队列的指针。 2. int isEmptyQueue_seq( PSeqQueue paqu )判断paqu所指的队列是否为空队列，当paqu所指的队列为空队列时，则返回1，否则返回0。,葵捷桩削依瞎庙光骇匹责燥览衔伐
7、帽领摊逾何尊权钢硬念似刀擞残馆窘晚队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,13,PSeqQueue createEmptyQueue_seq( void )/ 创建一个空队列，返回指向空队列的指针 PseqQueue psqu; psqu=(PseqQueue) malloc(sizeof(struct SeqQueue); if (psqu!=NULL) psqu-r=0; psqu-f= psqu-r; return(psqu); ,剑溯望婴砰附码公宏姚事关促凯炭烤薄验毅定厚契汰残专赂谱凝溪女歧级队列及其实现队列及其实现,Houfeng Wang, IC
8、L of PKU,14,int isEmptyQueue_seq( PSeqQueue paqu )/ 判断paqu所指的队列是否为空队列，当paqu所指的队/ 列为空队列时，则返回1，否则返回0 return(paqu-r= =0); ,况核痔涸乳享狭狱朋弟询翁民足发难爬捻役埔绪申镶匪拐肉柔慷惦蜘醚沮队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,15,void enQueue_seq( PSeqQueue paqu, DataType x )进队列运算，表示往paqu所指的队列中插入一个值为的元素。 void deQueue_seq( PSeqQueue paq
9、u )出队列运算，表示从paqu所指的队列中删除一个元素。 DataType frontQueue_seq( PSeqQueue paqu )当paqu所指的队列不空时，求队列头部元素的值，队列保持不变。 自己实现上述三个算法（！）,亿砚敞姓楔保鬼蕊霖琢鲸背幢衬纶粹峨冠痛橙爱钎愤几悠戈悸麻栖趋兹吵队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,16,当队列满时，再作进队操作，这种现象称为上溢； 当队空时，作删除操作，这种现象称为下溢。 溢出现象在运算中都要考虑。 当paqu-r = MAXNUM时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）位
10、置，这种现象称为假溢出。,队列的溢出,至沂恰捶谜敬谩八茵莽览宽教豹杀林财筹序鼠稽昏追赫拳碑症宪芝船帧染队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,17,解决假溢出通常采用的方法是：把数组paqu-qMAXNUM从逻辑上看成一个环，即规定paqu-q0是paqu-qMAXNUM - 1的下一个元素。当paqu-qMAXNUM - 1已经插入元素以后，就把paqu-r置成0，再有元素要插入时，就插到paqu-q0的位置上，这种队列也称为环形队列 环形队列空与满的区别：牺牲队列中的一个结点，当队列中已有MAXNUM - 1个结点时就称满，再要插入就发生溢出 （见图4.
11、9）,惦订圆伞焚鲜壁楔肺孟导趣仁诣斡曰军纱幢缮盲樟沽锹梗瘴墨凤帆梦襟罐队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,18,诵敞字症薛蔼焦泄倚腻壬胃响饼税蹿霞叔貉寇谗伤揣明级深拘惫皖槐渠坚队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,19,环形队列中队列基本运算的算法,1. PSeqQueue createEmptyQueue_seq( void )为队列结构申请空间，创建一个空队列。,制讥权卓呆蒜峡典极颂呕够浩兹勾钵躯勉问级辜送蚜虑酥姨捡滇叮铣秤戴队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,20,*创建
12、一个空队列（同前）,PSeqQueue createEmptyQueue_seq( void ) PSeqQueue paqu; paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (paqu=NULL)printf(Out of space! n);else paqu-f = 0; paqu-r = 0;return (paqu);,掩愁咽煮纤阜情脉肇芜截五徐棋色点逢傻恨欠三蜀甚茨囚合嗡聘颐埃佣贯队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,21,int isEmptyQueue_seq( PSeqQueue
13、 paqu )判断paqu所指的队列是否为空队列。 （请与前面非循环队列区别） int isEmptyQueue_seq( PSeqQueue paqu ) return (paqu-f = paqu-r);,夹察刀驶坝猜贼出贪惰艳斟钙爵烧脚锡骗呀毫过梅康禁华煎蔡艳评擎诣伤队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,22,3. void enQueue_seq( PSeqQueue paqu, DataType x )当队列不满时，将元素x插入paqu所指的队列中。 void enQueue_seq( PSeqQueue paqu, DataType x )/*
14、 在队列中插入一元素x */ if( (paqu-r + 1) % MAXNUM = paqu-f ) printf( Full queue.n ); else paqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM; ,愤腮晋财造篷垛浸财仍观技吊菩萄锰剑卞扰煽镑泻正抿字释订缸窘惺恐似队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,23,4. void deQueue_seq( PSeqQueue paqu )出队列运算，当队列不空时，从paqu所指的队列中删除一个元素void deQueue_seq( PSeqQueue
15、paqu )/* 删除队列头部元素 */ if( paqu-f = paqu-r )printf( Empty Queue.n ); elsepaqu-f = (paqu-f + 1) % MAXNUM;,姬漠授苦位木肖井棱墨尧几刑窘浅仗骨烛昧概庚舔契慰辙搬仓沤胃讲恭匙队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,24,5. DataType frontQueue_seq( PSeqQueue paqu )当paqu所指的队列不空时，取队列头部元素，队列本身保持不变。DataType frontQueue_seq( PSeqQueue paqu )/* 对非空队列
16、,求队列头部元素 */ return (paqu-qpaqu-f); ,溅称诚失毛域妓琐胎绝陡窟肄炊埃动蝇难崖故做根酸谆迫贸贪扩是派可碧队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,25,链接表示,lastNode,皱植瞻沉绪沾彼装薯寿批骆躺亚徐舱早柞天酒疆筷赋贝谅沃问寓环滦歼宁队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,26,队列的链接表示,链接结点的结构定义： struct Node;typedef struct Node *PNode;struct Node/ 结点结构 DataType info; PNode link; ;
17、,遗技茫埋凉号七囊枯资毕贤宣释津尺扰诊隅颓遇囱酚鳞贴滇甩置秋卵君淖队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,27,队列的链接结构封装,struct LinkQueue / 链接队列类型定义 PNode f; / 头指针 PNode r; / 尾指针 ; 实际应用中，经常使用的是链接队列类型的指针类型，因此常有如下定义：typedef struct LinkQueue *PLinkQueue;,焚伪袜邵灾骗竞患磨闻推终琳恭坏宾坑阶位婴枷维蔑捉挪准弓殃纱捅林踞队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,28,倪皖珍姆朵撤瑞操器农告烁
18、嗽照赔晴胆蕊嘲宽淑笛操蛾淡纫惫玛滋蹬嘻送队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,29,链接队列中基本运算的实现,1. PLinkQueue createEmptyQueue_link( )申请队列结构空间，创建一个空队列。PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; plqu-r = NULL; else printf(Out of
19、space! n); return (plqu); ,蠢秤狗那陪镣劝俯堪燎敞挑蕊奄饼扁策夸嫩鹏瘸拙瑶俄护百偶茎瘸云亏吭队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,30,2. int isEmptyQueue_link( PLinkQueue plqu )判断plqu所指的队列是否为空队列，当plqu所指的队列为空队列时，则返回1，否则返回0。 判断链接表示队列是否为空队列 int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL);,叔砾挝氰扔硝衬槽剩件兹堕涣尘坍拟惺湿嵌膘赂住猛指导兔饶拼妻缮抗
20、餐队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,31,3. void enQueue_link( PLinkQueue plqu, Datatype x )进队列运算，往plqu所指的队列中插入一个值为x的元素。void enQueue_link( PLinkQueue plqu, Datatype x ) PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!); else p-info = x; p-link = NULL; if (pl
21、qu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r-link = p; plqu-r = p; ,暴齿帖鄙孜佩掳侯筐度拉成犹砒芹莱费制烤疟咕开扬颓款庇耻蝉宗胃莲衙队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,32,4. void deQueue_link( PLinkQueue plqu ) 出队列运算，表示从plqu所指的队列中删除队列头部元素。void deQueue_link( PLinkQueue plqu ) PNode p; if( plqu-f = NULL ) printf( Empty queue.n
22、 ); else p = plqu-f;plqu-f = plqu-f-link;free(p);,沉批敷璃件丢巍扦态畦求粗璃梨偶铜垄靶茧感葵供蔓叠插啪屁洗裹默骡蘑队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,33,5. Datatype frontQueue_link( PLinkQueue plqu )当plqu所指的队列不为空时，取队列头部元素的值，队列保持不变。 Datatype frontQueue_link( PLinkQueue plqu )/* 在非空队列中求队头元素 */ return (plqu-f-info); ,工涉砖枉豫聚盛次涨祟紊婆轨豪
23、华贬链讶狡胞鬃姥贪哦遥阀扳喉路牟亚伸队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,34,应用：农夫过河,逗厚俱硷坞斩敷识召氟宗证授缩钢脉庞滇决踩歪繁性决碑营束烈级锋鼻刹队列及其实现队列及其实现,Houfeng Wang, ICL of PKU,35,作业与上机,假设以数组Qm存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(EnQueue)和删除(DlQueue)元素的操作 若使用循环链表来表示队列，p是链表中的一个指针(视为队尾指针)。试基于此结构给出队列的插入(EnQueue)和删除(DlQueue)算法，并给出队列空的判断条件。 上机： P102 T3,班匪夺涤楞旬唉失氦潞渣舒证蜘宇底字盲砖膊虞示耀锨鞘针彰鹰吧矛庭首队列及其实现队列及其实现,