一、Python实现队列的思路

• 用Python内置的list实现队列
• 实现设置队列的尾部在列表的位置0处

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

二、利用队列解决约瑟夫环问题

此处用模拟传土豆解释约瑟夫环问题的求解方法

游戏规则

传土豆，在这个游戏里，孩子们围成一圈，并依次尽可能快地传递一个土豆，如下图所示。在某个时刻（类似报数）,大家停止传递，此时手里有土豆的孩子就得退出游戏。重复上诉过程，直到只剩下一个孩子。

yuesefu.png

解决方法

使用队列模拟一个环，假设手握土豆的孩子位于队列的头部。在模拟传土豆的过程中，程序将这个孩子的名字移出队列，然后立刻将其插入队列的尾部。随后，这个孩子一直等待，直到再次到达队列的头部。在出队和入队num次之后，此时位于队列头部的孩子出局，新一轮游戏开始。如此反复，直到队列只剩下一个孩子的名字。如下图所示。

potato.png

代码实现

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())
        simqueue.dequeue()
    return simqueue.dequeue()

测试及结果

测试：print(hotPotato(["Bill", "David", "Susan", "Jane", "Kent", "Brad"], 7))
输出：Susan