开发者

Python数据结构与算法中的队列详解(2)

目录
  • 传土Srfxqq
  • 总结

传土豆

队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景。考虑这样一个游戏:传土豆。在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆。在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏。 重复上述过程,直到只剩下一个成员。

Python数据结构与算法中的队列详解(2)

我们将针对传土豆游戏实现通用的模拟程序。该程序接受一个名字列表和一个用于Srfxqq计数的常量&nbs编程客栈p;num ,并且返回最后剩下的那个人的名字。

我们使用队列来模拟一个。即假设握着土豆的人位于队列的头部。在模拟传土豆的过程中,程序将这个人的名字移出队列,然后立刻将其插入队列的尾部。随后,这个人会一直等待,直到再次到达队列的头部。在出列和入列 num 次之后,此时位于队列头部的人出局,新一轮游戏开始。如此反复,直到队列中只剩下一个名字(即队列的大小为 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)     # 队列(列表)长度
    def look(self):
        print(self.items)
        
def transmitPotato(nameList, num):
    simqueue = Queue()     # 创建队列
    for name in nameList:  # 遍历成员姓名列表
        simqueue.enqueue(name)   # 成员姓名入队列
    while simqueue.size() > 1:  # 当队列元素个数大于1时 循环执行
        for i in range(num):  # 循环num次(土豆传递num次)
            # 成员姓名从队头转换至队尾
            simqueue.enqueue(simqueue.dequeue())
        # 成员姓名出队(此成员淘汰出局)
        s编程客栈imqueue.dequeue()
    return simqueue.dequeue()  # 返回队列里最后剩下的名字

调用 transmitPotato 函数,使用 7 作为计数常量,将得到以下结果:

Python数据结构与算法中的队列详解(2)

注意,在上例中,计数常量大于列表中的名字个数。 这不会造成问题,因为队列模拟了一个。同时需要注意,当名字列表载入队列时,列表中的第一个名字出现在队列的头部。在上例中,小明是列表中的第一个元素,因此处在队列的最前端。

总结

本篇文章就到这里了,希Srfxqq望能够给你带来帮助,也希望您能够多多关注我们的更多内容!    

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新开发

开发排行榜