在数据结构的栈和队列的学习过程中，除了需要了解栈、队列的基本特点外，需要掌握包括创建、出栈入栈、出队入队等基本操作。并熟悉一些常见的应用问题，比如球钟问题就是一个典型利用栈和队列实现的实际问题。本文描述球钟问题的具体实现过程。球钟是一个利用球的移动来记录时间的简单装置.它有三个可以容纳若干个球的指示器：分钟指示器,五分钟指示器,小时指示器.若分钟指示器中有2个球,五分钟指示器中有6个球,小时指示器中有5个球,则时间为5：32.球钟的工作原理如下：分钟指示器最多可容纳4个球.每过一分钟,球钟就会从球队列的队首取出一个球放入分钟指示器,当放入第五个球时,在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾.而第五个球就会进入五分钟指示器.按此类推,五分钟指示器最多可放11个球,小时指示器最多可放11个球.当小时指示器放入第12个球时,原来的11个球按照他们被放入时的相反顺序加入球队列的队尾,然后第12个球也回到队尾.这时,三个指示器均为空,回到初始状态,从而形成一个循环.因此,该球钟表示时间的范围是从0：00到11：59.现设初始时球队列的球数为x（27≤x≤127）,球钟的三个指示器初态均为空.问要经过多少天（每天24小时）,球钟的球队列才能回复原来的顺序。
相关代码如下
/** *@filename ballclock.c *@author haohaibo *@data 2017/4/13 *@brief 球钟问题解决 **/ #include "stack.h" #include "lqueue.h" #include "ballclock.h" /** *@brief 解决球钟问题 **/ int ball_clock() { int lq_i=1,mincount=0; int min,fmin,hour=0; lq_t *lq1=linkqueue_creat(); //创建一个队列 seqstack_t* s1=seqstack_creat(); //定义分钟栈，五分钟栈，小时栈 seqstack_t* s2=seqstack_creat(); seqstack_t* s3=seqstack_creat(); for(lq_i=1;lq_i<=M;lq_i++) linkqueue_in(lq1,lq_i); //队列加入1-27 //linkqueue_show(lq1); while(1) { if(s1->top<3) //-1~2 共容纳4个值 { seqstack_insert(s1,linkqueue_out(lq1)); //出列数据放入分钟栈 } else //分钟栈数值即将超过4 { for(min=0;min<4;min++) //栈内数据入列 { linkqueue_in(lq1,seqstack_out(s1)); } if(s2->top<10) //-1-9容纳11个值 { seqstack_insert(s2,linkqueue_out(lq1)); //出列入栈 } else //五分钟栈值即将超过11个 { for(fmin=0;fmin<11;fmin++) { linkqueue_in(lq1,seqstack_out(s2)); //出栈入列 } if(s3->top<10) { seqstack_insert(s3,linkqueue_out(lq1)); } else { for(hour=0;hour<11;hour++) { linkqueue_in(lq1,seqstack_out(s3)); } linkqueue_in(lq1,linkqueue_out(lq1)); } } } mincount++; if(lq_check(lq1)) break; } return mincount; } /** *@brief 检查数据是否回到最初状态 **/ int lq_check(lq_t *lq) { int count=0; lqn_t *p=lq->front->Next; while(p!=NULL&&p->Next!=NULL) { if(p->data>p->Next->data) //保证队列中的数据前一个都小于后一个 return 0; p=p->Next; count++; } return count==26?1:0; //且队列中一共有27个值 } /** *@brief 用于调试 **/ /* puts("!!*************"); linkqueue_show(lq1); printf("lq1->real=%p,lq->front=%p\n",lq1->real,lq1->front); printf("s3->top=%d,s2->top=%d,s1->top=%d\n",s3->top,s2->top,s1->top); puts("**************!!"); */
一下是全部文件的链接
http://download.csdn.net/detail/u010916862/9813659
