数据结构——第三章 栈与队列（4）

1.基于队列的医院挂号模拟系统

代码实现分享

2.队列的运用

问题描述：某运动会设立N个比赛项目，每个运动成员可以参加1~3个项目。试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在同一时间进行，又可以使总的竞赛项目日程最短。
若将此问题抽象成数学模型，则归属于“划分子集问题”，即将集合A划分成k个不想交的子集：A1,A2…,Ak（K<=n），使得同一子集中的元素均无冲突关系，并要求划分子集数目尽可能地少。
也可以把这个问题表述为：同一子集的项目为可以同时进行的项目，并且希望运动会的日程尽可能的短。
解决划分子集问题可利用“过筛”的方法。从第一个元素考虑起，凡不和第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互补冲突的元素为第二子集，依此类推，直至所有元素都进入某个子集为止。

为了更好地描述用“过筛”的方法划分子集，用队列保存待选项目编号，用一维数组case保存待选项编号与已入选子集的项目编号的冲突情况。排在队头的项目编号i是当前的待选项目，能否入选由case[i]的值来决定，值为0表示与当前子集的项目无冲突，i出队并加入子集；反之则有冲突，i出队并重新排队，等待下一个子集的筛选。

下面给出划分第1个子集A1的主要步骤。
（1）将项目编号0~8依次进队列。将队头的项目编号0出队，放入子集A1中，将冲突数组与项目0对应的行取出放入一维数组case中。此时case中的每个元素的值表示元素下标的项目与项目0的冲突情况。
（2）当前队头是项目1，项目1能否加入子集A1由case[1]的值来决定。当前case[1]是1，表示项目1与子集A1中的项目0有冲突，项目1不能加入子集A1，出队后直接入队。
（3）当前队头是项目2，项目2能否加入子集A1由case[2]的值来决定。当前case[2]是0，表明项目2与子集A1中的已有项目没有冲突，项目2出队后加入子集A1。现在A1中已经有了2个项目，后来入选的项目必须与A1中的2个项目都没有冲突，为此将冲突表中与刚入选的项目2对应的行按下标与case数组相加，用两者的和更新case数组，此时的case数组是后续待选项目能否入选的依据。
（4）当前队头是项目3，项目3能否加入子集A1由case[3]的值来决定。当前case[3]是0，表明项目3与子集A1中的已有项目没有冲突，项目3出队后加入子集A1。现在A1中已经有3个项目，后来入选的项目必须与A1中的3个项目都没有冲突，为此将冲突表中与刚入选的项目3对应的行按小标与case数组相加，用两者的和更新case数组。此时的case数组是后续待选项目能否入选的依据。
（5）当前队头是项目4，项目4能否加入子集A1由case[4]的值来决定。当前case[4]是1，表明项目4与子集A1中的已有项目有冲突，项目不能加入子集A1，出队后直接进队。
（6）当前队头是项目5，项目5能否加入子集A1由case[5]的值来决定。当前case[5]是2，表明项目5与子集A1中的已有项目冲突，项目5不能加入子集A1，出队后直接入队。
（7）当前队头是项目6，项目6能否加入子集A1由case[6]的值来决定。当前是1，表明6与子集A1中的已有项目冲突，项目6不能加入子集A1，出队后直接入队。
（8）当前的队头是项目7，项目7能否加入子集A1由case[7]的值来决定。当前case[7]是0与子集A1中的已有项目没有冲突，项目7出队后放入子集A1。现在A1中已经有4个项目，后来的项目必须与A1中的4个项目都没有冲突，为此将冲突表中与刚入选的项目7对应的行按下标与case数组相加，用两者的和更新case数组，此时的case数组后续待选项能否入选的依据。
（9）当前队头是项目8，项目8能否加入子集A1由case[8]的值来决定。当前case[8]是1，表明项目8与子集A1中的已有项目有冲突，项目8不能加入子集A1，出队后直接入队。

当排在队头的项目编号小于刚加入子集的项目编号时，表示队列中的所有项目都被“过筛”一遍，第一个子集划分完成。用同样的方法划分其他子集，直到队列为空。

划分子集算法的基本思想如下。

pre = n；组号 = 0；//n为数据元素的个数
全体成员入栈
while(队列不能为空)
{ //队头元素i出队列；
if(i<pre)//开辟新的组
{
组号++；
case 数组初始化；
}
if(i能入组）//i与该组的元素没有冲突
{
i入组，记下序号为i的元素所属组号；
修改case数组；
}
else i重新入队列；
pre=i；//前一个出队列的元素序号
}