队列的Python实现与实例分析

迷南。 2022-05-31 10:28 187阅读 0赞

队列是只有一端可以进行插入操作，而另一端可以进行删除操作的有序线性存储结构，满足先进先出的约束。

生活中典型的实例就是排队，先到的人排在前面，可先得到服务，后到的人排在后面，并且不能插队。

计算机应用中典型的实例就是打印机，先发送的打印任务可以先被执行，之后的都要排队等候

### Python实现 ###

在 Python 中，和栈一样，同样可以用列表作为队列的底层实现，只需要确定列表的哪一端作为队列的头，也即删除操作端，哪一端作为队列的尾，也即插入操作端。同时，把队列抽象为类，队列的先进先出操作实现为类的方法

假定队尾在列表中的位置为 0。这允许我们使用列表上的插入函数向队尾添加新元素。弹出操作可用于删除队首的元素（列表的最后一个元素）。这样入队的复杂度为 O(n)，出队为 O(1)。如果队尾和队首在列表中的位置换一下，则入队的复杂度为 O(1)，出队为 O(n)。

以下为按照前面一种方式的队列的Python实现

Queue 实现一个队列类，可通过 Queue() 建立一个空队列

is\_empty 操作判断队列是否为空

enqueue 操作将新元素插入到列尾

dequeue 操作将弹出并删除队首的元素

size 操作返回队列的大小

class Queue:
        def __init__(self):
            self.items=[]
        def is_empty(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)

以上为队列的最简单实现，对比栈的实现，可以看出两者非常相像，只在插入操作上有所不同。

### 应用实例 ###

约瑟夫问题：n个人围成一个圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。

解约瑟夫问题的一种方法是模拟这个过程，模拟的载体可以是队列，也可以是链表，下面就用列队来模拟这个过程

循环报数的过程可以看作是一个先报数先出的过程，用队列来模拟时，将当前报数的人弹出，如果报的不是k时，再插入到队尾，从而得以循环，如果报的是k，则抛弃。直至剩下最后一个人。

下面是在生成 Queue 类的基础下，Python 解决约瑟夫问题的一个实例代码，以实际人名来仿真n个人，报数为7时删除，输出最后的胜利者。

#约瑟夫问题仿真函数
    def circle(k,nameList):
        queue1=Queue()
        for i in range(len(nameList)):  #将名字列表逐个插入队列
            queue1.enqueue(nameList[i])
        i=1
        while queue1.size()!=1:
            temp=queue1.dequeue()       #叫到哪个将哪个弹出
            if i!=k:
                queue1.enqueue(temp)    #不是第k个再插入
            else :
                i=0                     #是第k个重新计数
            i+=1
        return queue1.dequeue()
    #主函数
    if __name__=='__main__':
        nameList=["Bill","David","Susan","Jane","Kent","Brad"]
        print(circle(7,nameList))
    #输出结果
    Kent