Python 队列之传土豆(《Python数据结构与算法分析》第二版)

前提条件:队列的实现:

class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.item == []
    def enqueue(self,item):
        self.items.append(item)
    def dequeue(self):
        self.items.pop(0)
    def size(self):
        return len(self.items)

考虑下面的问题:

Bill David Susan Jane Kent Brad 六个人,按照这样的顺序,传递一个土豆并报数,当遇到某个数字时,这个人就要退出游戏,假定我们遇到的退出数字为7,请问在这个位置的条件下,谁能留到最后呢?(Bill从0开始报数)

可以用队列来解决这个问题,这几个人“排队”就类似于队列的一种组合。先来看第一次传土豆的顺序,土豆用P表示,把带土豆的那个人看作队首,如:

Bill(P) David Susan Jane Kent Brad  
David(P) Susan Jane Kent Brad Bill

发现在这里这几个人的排队方式类似于一个环状的结构,上次的队首会在下次变成队伍末尾的元素,所以我们不妨在处理的过程中把队首的元素弹出,再把弹出的元素添加到末尾,这是最关键的一步。

所以整体的分析如下:

首先,定义一个队列,让人按照顺序入队,其代码段如:

def hotPotato(namelist,num):
    s = Queue()
    i=1
    for name in namelist:
        s.enqueue(name)

然后,开始传土豆的模拟部分,只要队伍不为空,我们就可以把队伍中队首的元素弹出,从上面的叙述可以看出,从现在手里拿土豆的人的角度来看,这个人在队伍的末尾,添加到末尾去。

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

这个循环的过程类似于报数的过程,Bill报0,报完之后被扔到末尾去,接着David报1,Susan报2,即循环的i就是每个人报的数,我们在这里以题目中的7为例,i的取值有0,1,2,3,4,5,6七个,也就是说,循环停止后,整个队列的头部就是要退出游戏的人,因而在退出循环后,我们要请队首的人出队,其代码如:(注意要和前面的循环对齐)

        s.dequeue()

接下来,循环一直运行,直到整个队伍里只剩下最后一个人,因此我们这个函数只需要返回最后一个人的名字就可以了,如:

    return s.dequeue()

把上面的代码组合起来,就是我们整个的传土豆的函数。

上一篇:Android Activity启动模式


下一篇:Python编程:用两个栈实现队列