数据结构（C语言）-球钟问题（栈和队列）-学习笔记05

1. 球钟背景

• 球钟是一个利用球的移动来记录时间的简单装置
• 它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器
• 若分钟指示器中有两个球，五分钟指示器有六个球，小时指示器有五个球，那就代表时间是5：32

2. 工作原理

• 我们需要27个球放入一个队列
• 需要三个栈，分别代表分钟指示器，五分钟指示器，小时指示器
• 每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可以容纳四个球
• 放入第五个球的时候，分钟指示器清空，也就是把分钟指示器中的四个球按照被放入时的相反顺序加入到球队列的队尾，第五个球就会进入五分钟指示器中
• 以此类推，五分钟指示器最多可放11个球，小时指示器最多可以放11个球（按照12小时）
• 当分钟指示器有4个球，五分钟指示器有11个球，小时指示器有11个球的时候代表11：59，这个时候我们需要另外一个球表示最后一分钟来清空所有队列中的球，因此我们一共需要27个球

3. 实现

栈参考数据结构（C语言）-线性表之栈-学习笔记03
队列参考数据结构（C语言）-线性表之链式队列-学习笔记04

#include 
#include "linkqueue.h"
#include "sqstack.h"

int main(int argc, char *argv[]){
	linkqueue *lq;
	sqstack *hour, * five_min, *one_min;
	int min = 0, val;

	if ((lq = linkqueue_create()) == NULL)
		return -1;
	for (int i = 1; i <= 27; i++){
		linkqueue_enqueue(lq, i);
	}
	
	if ((hour = sqstack_create(11)) == NULL){
		return -1;
	}
	if ((five_min = sqstack_create(11)) == NULL){
		return -1;
	}
	if ((one_min = sqstack_create(4)) == NULL){
		return -1;
	}

	while(1){
		min++;
		if (!linkqueue_empty(lq)){
			val = linkqueue_dequeue(lq);
			if (!sqstack_full(one_min))
				sqstack_push(one_min, val);
			else{
				while(!sqstack_empty(one_min)){
					linkqueue_enqueue(lq, sqstack_pop(one_min));
				}
				if (!sqstack_full(five_min))
					sqstack_push(five_min, val);
				else{
					while(!sqstack_empty(five_min)){
						linkqueue_enqueue(lq, sqstack_pop(five_min));
					}
					if (!sqstack_full(hour))
						sqstack_push(hour, val);
					else{
						while(!sqstack_empty(hour)){
							linkqueue_enqueue(lq, sqstack_pop(hour));
						}
						linkqueue_enqueue(lq, val); // 00:00
						break;
					}
				}
			}
		}
	}
	printf("total min: %d\n", min);
	return 0;
}