数据结构与算法（python） 线性结构：队列Queue

参考自

一、什么是队列Queue

队列是一种有次序的数据集合，其特征是： – 新数据项的添加总发生在一端（"尾rear"端） – 而现存数据项的一处总发生在另一端（“首front”端） 遵循先进先出（FIFO:First-infirst-out） 队列的例子：排队,不允许数据项直接插入队中，也不允许从中间移除数据项 计算机科学中队列的例子：打印队列

二、抽象数据类型Queue

2.1 Queue的基本操作

2.2 Python实现ADT Queue

采用List来容纳Queue的数据项，将List首端作为队列尾端，List的末端作为队列首端，enqueue()复杂度为O(n)，dequeue()复杂度为O(1)

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)

三、队列的应用

3.1 约瑟夫问题

传说犹太人反叛罗马人，落到困境，约瑟夫和39人决定殉难，坐成一圈儿，报数1～7，报到7的人由旁边杀死，结果约瑟夫给自己安排了个位置，最后活了下来…… 算法流程：

采用队列来存放所有参加游戏的人名，按照数字传递方向从队首排到队尾 模拟游戏开始，每一次传递， 将队首的人移到队尾，达到num次后，将队首的人移除，剩下的人继续轮回

代码如下：

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)
    
def Joseph(namelist, num):
    liveQueue = Queue()
    for name in namelist:
        liveQueue.enqueue(name)
    while liveQueue.size()>1:
        for i in range(num):
            liveQueue.enqueue(liveQueue.dequeue())
        liveQueue.dequeue()       
    return liveQueue.dequeue()
print(Joseph(["Justin Bieber","Eason","Leslie","Bille Eilish","Taylor Swift","Sia","Lana Del Rey","Troye Sivan"],4))

试着跑跑程序哈~