Python队列实战：使用FIFO结构模拟传土豆游戏

慢慢来

发布时间：2026-10-12| 2人浏览过

原创

本文详细讲解如何利用Python的队列数据结构模拟经典的“传土豆”游戏场景。通过手动构建先进先出（FIFO）队列类，结合循环移位与条件剔除逻辑，完整实现了多轮传递淘汰算法的代码编写与测试，帮助开发者直观掌握队列在复杂交互逻辑中的核心应用价值。

传土豆游戏的FIFO原理

队列的一个典型应用场景是模拟需要以先进先出（FIFO）方式管理数据的现实环节。考虑经典的传土豆游戏：多名成员围成一圈依次快速传递物品。规定到达特定计数点时，当前持有物品的成员需退出游戏。该过程不断重复，直至圈内仅剩一人即为获胜者。

借助队列的环形特性，我们可以精准还原这一动态过程。假设当前持物者始终位于队列的最前端，模拟传递时将其名称从队列顶部移出并立即追加至底部。当累计触发指定计数次数后，位于顶部的下一位队员将被正式移除。此流程不断循环缩减名单，直到队列中仅保留一个名字。

构建基础队列类

在算法练习中，基于Python原生列表封装独立的队列类，能够清晰展现底层运作机制。我们需要实现判断空列、入列操作、出列操作以及获取尺寸的核心方法。

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)  # 返回当前队列容纳的元素总数

此处采用列表左侧作为队尾、右侧作为队头的设计。这种双向锚定方式确保了 `insert(0)` 和 `pop()` 均能在常数时间 $O(1)$ 内完成，大幅提升了高频进出列操作的执行效率。

编写传土豆模拟函数

第1步：初始化参与人员

实例化队列对象后，遍历传入的成员名单列表，逐一调用入列方法。此时列表源数据排在首位的名字，将自动占据队列逻辑上的最前端位置，成为第一轮计数的起始基准。

第2步：执行传递与淘汰循环

设定外层循环持续监测队列规模，只要剩余人员数量超过1便维持运行。内层循环负责具体的传递演练：连续执行“出列再接回队尾”的操作，让位置向前推移。变量 num 控制每次传递的步长。当内层步数跑满后，直接执行一次出列动作，正式剔除本轮应淘汰的队员。

第3步：获取最终幸存者

随着外层循环条件的逐步逼近，队列容量最终会收缩至1。此时跳出循环，再次执行出列操作提取残存的唯一元素，函数即返回该获胜者的名字。

def transmit_potato(name_list, num):
    queue_obj = Queue()  # 创建队列实例
    for person in name_list:
        queue_obj.enqueue(person)  # 统一录入参与成员
        
    while queue_obj.size() > 1:
        for _ in range(num):
            queue_obj.enqueue(queue_obj.dequeue())  # 模拟顺时针传递
        queue_obj.dequeue()  # 移除当前淘汰名额
        
    return queue_obj.dequeue()