【Python】（五）Python实现队列

我们可以以列表为基础实现队列。这里，我们将列表的最后一个元素作为队首，将第一个元素作为队尾。这也就意味着，入队的时间复杂度是O(n)，出队的时间复杂度是O(1)。

class Queue():
    # Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
    def __init__(self):
        self.items = []
    
    # enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
    def enqueue(self, item):
        self.items.insert(0, item)
    
    # dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
    def dequeue(self):
        item = self.items.pop()
        return item
    
    # isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
    def isEmpty(self):
        return 0 == len(self.items)
        
    # size() 返回队列中的项数。它不需要参数，并返回一个整数。
    def size(self):
        length = len(self.items)
        return length

击鼓传花大逃杀

你和你的 39 个同学外出露营，晚上无聊时，大家围在火堆边做游戏。
游戏规则如下：40人围成一个圈，其中一人被指定为第一个人，顺时针报数到第七人，就将他杀死。之后，下一个活着的人继续报数，每次都是杀死第七个人。直到只剩一人时，游戏结束。
如果你并不想死，那么应该坐到哪里才能成为最后一人？（假设第一个报数者的位置记为1）

这个问题其实可以抽象为一个队列问题。每一个报数的人都相当于一次“从队首出队，又从队首入队”的操作。没进行6次出入后的下一个人将只出队不入队。直至整个队列只有一个人，这个人的编号就是最初应该选择的位置编号。

class Queue():
    # Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
    def __init__(self):
        self.items = []
    
    # enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
    def enqueue(self, item):
        self.items.insert(0, item)
    
    # dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
    def dequeue(self):
        item = self.items.pop()
        return item
    
    # isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
    def isEmpty(self):
        return 0 == len(self.items)
        
    # size() 返回队列中的项数。它不需要参数，并返回一个整数。
    def size(self):
        length = len(self.items)
        return length

def DaTaoSha(name_list, kill_num):
    # name_list ：游戏者列表
    # kill_num ： 杀死第几个人
    
    que = Queue() # 初始化队列
    for name in name_list:
        que.enqueue(name) #将游戏者依次入队
    
    while que.size() > 1 :
        for i in range(kill_num-1):
            que.enqueue(que.dequeue()) # 出队又入队，相当于“报数”
        print("Kill the number %d"%que.dequeue()) # 出队不入队，杀死一个人 
    
    return que.dequeue() #返回存活者

def main():
    kill_num = 7 # 杀死第7个人
    original_list = list(range(1, 41)) # 为40个人编号
    Safe_name = DaTaoSha(original_list, kill_num) #进行大逃杀，返回存活者
    print("-----------------")
    print("Safe number is %d"%Safe_name)

if __name__ == "__main__":
    main()

运行结果为：
···
Kill the number 7
Kill the number 14
Kill the number 21
Kill the number 28
Kill the number 35
Kill the number 2
Kill the number 10
Kill the number 18
Kill the number 26
Kill the number 34
Kill the number 3
Kill the number 12
Kill the number 22
Kill the number 31
Kill the number 40
Kill the number 11
Kill the number 23
Kill the number 33
Kill the number 5
Kill the number 17
Kill the number 30
Kill the number 4
Kill the number 19
Kill the number 36
Kill the number 9
Kill the number 27
Kill the number 6
Kill the number 25
Kill the number 8
Kill the number 32
Kill the number 16
Kill the number 1
Kill the number 38
Kill the number 37
Kill the number 39
Kill the number 15
Kill the number 29
Kill the number 13
Kill the number 20

Safe number is 24
···
第24个人存活了下来。