栈和队列的应用 ——球钟算法
1.球钟背景
球钟是一个利用球的移动来记录时间的简单装置
它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器
若分钟指示器中有两个球，五分钟指示器有六个球，小时指示器有五个球，那就代表时间是5：32
2. 工作原理
每过一分钟球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。
当放入第五个球时，在分钟指示器的4个球就会照他们被放入时的相反顺序出栈并加入球队列的队尾。
而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。
当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。
因此，该球钟表示的时间范围是从00:00到11:59。（12小时制）
3. 问题：
假设有1-27个升序排列的球钟在球队列中，球钟的三个指示器初态均为空。求经过多长时间，球队列的排序再次回到1-27的升序顺序？
4. 代码实现
使用顺序栈和顺序队列实现，整体流程如下
#include<stdio.h>
#include<stdlib.h>
#include "../test8-stack/sqstack.h"
#include "../test10_squeue/queue.h"
//球钟算法：三个栈，一个队列，12小时制，27个球，求什么时候球的顺序排列再为1~27
//包含其他头文件，注意要改下前面定义相同的变量，如MAXSIZE,struct
#define NR_BALL 27 //定义27个球
static int check(queue *qu)
{
//循环队列，i为第一个值指向head的下一个数据（head不放数据）
int i=(qu->head+1)%MAXSIZE;
while (i!=qu->tail)
{
//若队列为1~27的顺序，则每个数小于后一个数
if(qu->data[i]>qu->data[(i+1)%MAXSIZE])
return 0;
i=(i+1)%MAXSIZE;
}
return 1;
}
int main()
{
queue *qu;//存放球
int t,time=0,value=0,hour;//t存放出队的球,time存放时间
sqstack *st_min,*st_fivemin,*st_hour;//三个时间栈
qu=qu_create();
if(qu==NULL) return -1;
st_min=st_create();
if(st_min==NULL) return -1;
st_fivemin=st_create();
if(st_fivemin==NULL) return -1;
st_hour=st_create();
if(st_hour==NULL) return -1;
//球入队
for(int i=1;i<=NR_BALL;i++)
qu_enqueue(qu,&i);
while (1)
{
//球出队
qu_dequeue(qu,&t);
time++;//时间自增
//1min栈球数不到4，直接入栈 top从0开始入栈 0,1,2,3（最多放四个1min的球）
if(st_min->top!=3)
{
st_push(st_min,&t);
}
else
{
//1min的球栈满了，要全部出栈清空
while (!st_isempty(st_min))
{
st_pop(st_min,&value);
//出栈后的球重新入在原来队列的后面
qu_enqueue(qu,&value);
}
//1min的球栈清空后，如果5min的栈未满，出队的球要入5min的球栈，否则5min的球栈要出栈进入1hou栈
if(st_fivemin->top!=10)
st_push(st_fivemin,&t);//5min球栈满为11个球，top从0开始，满表示10
else
{
//5min球栈满，要出栈入队
while (!st_isempty(st_fivemin))
{
st_pop(st_fivemin,&value);
qu_enqueue(qu,&value);
}
//如1hour栈,11个球表示栈满（12小时制）
if(st_hour->top!=10)
st_push(st_hour,&t);
else
{
//1hour球栈满，出栈，球入队
while (!st_isempty(st_hour))
{
st_pop(st_hour,&value);
qu_enqueue(qu,&value);
}
//此时栈全部清空，最后一个球也进入原来的对列中，这时才可能会有球的重新排序为1~27的情况
qu_enqueue(qu,&t);
check(qu);//检测队列情况
//队列为所求，退出循环
if(check(qu))
break;
}
}
}
}
printf("The order of the balls is:\n");
qu_travel(qu);
hour=time/60;//计算时间
time=time%60;//计算分钟
printf("time:%d hour %d min after success!\n",hour,time);
qu_destroy(qu);
st_destroy(st_min);
st_destroy(st_fivemin);
st_destroy(st_hour);
return 0;
}
//gcc.exe .\bowlTime.c ..\test8-stack\sqstack.c ..\test10_squeue\queue.c -o main.exe