UVa 133

The Dole Queue

from Volume 2. Data Structures :: Lists

Description

• 有 n 个人（从0到 n – 1）排成一队，队头和队尾相连，变成一个圈。
• 然后有两个 official ，一个从队头开始顺序点人头，一个从队尾开始逆序点人头。
• 分别从第1个数到第 m 个和第 k 个，就让此时点的到人出队，然后再从1开始数。
• 点人头和出队的顺序是，两个 official 先同时点人头，然后让点的到人同时出队。
• 当两个 official 数到的是同一个人的时候，就只有这个人出队。
• 一直数到全部人出队为止。 输入队列人数 n，和两个official分别报的数 m， k ，输出出队的顺序。

Solution

用双向循环列表模拟这个队列。然后用两个official指针去模拟数人出队的过程。注意在出队的时候，第一个official点到的人出队后，可能指向第二个 official 点到的人，即马上要出队的人，如果直接让第二个official点到的人出队，表示第一个official的指针会变成野指针。