Python数据结构队列解决约瑟夫斯问题

时间:2023-02-03 西召人气:0

1、队列

队列是一种遵循先进先出(FIFO)原则的数据结构。

可以使用数组实现队列的基本操作。当进行入队操作的时候，即在队列尾部插入一个元素，由于需要将所有元素向后移动一个位置，因此添加操作的时间复杂度是O(n)；

当进行出队操作的时候，只需要在队头移除一个元素，其他元素的序号不变，因此移除操作的时间复杂度是O(1)。

使用Python数组实现队列源码：

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)

2、使用队列解决约瑟夫斯问题

弗拉维奥·约瑟夫斯是公元1世纪著名的历史学家。相传，约瑟夫斯当年和39个战友在山洞中对抗罗马军队。眼看着即将失败，他们决定舍生取义。于是，他们围成一圈，从某个人开始，按顺时针方向杀掉第7人。约瑟夫斯同时也是卓有成就的数学家。据说，他立刻找到了自己应该站的位置，从而使自己活到了最后。当只剩下他时，约瑟夫斯加入了罗马军队，而不是自杀。

这个故事有很多版本，有的说是每隔两个人，有的说最后一个人可以骑马逃跑。不管如何，问题都是一样的。

约瑟夫斯问题等价于一个儿童游戏：传土豆。

在这个游戏中，孩子们围成一圈，并依次尽可能快地传递一个土豆，在某个时刻，大家停止传递，此时手里有土豆的孩子就得退出游戏。重复上述过程，直到只剩下一个孩子。

import my_queue
def hotPotato(namelist, num):
    queue = my_queue.Queue()
    for name in namelist:
        queue.enqueue(name)
    while queue.size() > 1:
        for i in range(num):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.dequeue()
print(hotPotato([1, 2, 3, 4, 5, 6], 7))

执行过程如下，最终输出结果为 3 。

234561
345612
456123
561234
654321
543216
432165
43216 弹出4
3216 弹出3

3、双端队列

双端队列是一种允许我们同时从队头和队尾进行出队和入队操作的特殊队列，它是队列和栈的结合体。

使用数组实现双端队列源码：

class Deque:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def addFront(self, item):
        self.items.append(item)
    def addRear(self, item):
        self.items.insert(0, item)
    def removeFront(self):
        return self.items.pop()
    def removeRear(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)

4、使用双端队列解决回文问题

回文是指从前往后读和从后往前读都一样的字符串，例如radar、toot，以及madam。

需要构建一个程序，它接受一个字符串并且检测其是否为回文。

import my_deque
def palchecker(aString):
    chardeque = my_deque.Deque()
    for ch in aString:
        chardeque.addRear(ch)
    stillEqual = True
    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False
    return stillEqual
print(palchecker('aaaabaaaa'))
print(palchecker('aaaabaaab'))

输出结果为：

True
False

加载全部内容