Python數(shù)據(jù)結構與算法中的隊列詳解(2)

更新時間：2022年03月09日 16:52:51 作者：姜學遷

這篇文章主要為大家詳細介紹了Python中的隊列，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

傳土豆

隊列的一個典型方法是模擬需要以 FIFO 方式管理數(shù)據(jù)的真實場景?？紤]這樣一個游戲：傳土豆。在這個游戲中，成員們圍成一圈，并依次盡可能快地傳遞一個土豆。在某個時刻，大家停止傳遞，此時手里有土豆的成員就得退出游戲。重復上述過程，直到只剩下一個成員。

在這里插入圖片描述

我們將針對傳土豆游戲實現(xiàn)通用的模擬程序。該程序接受一個名字列表和一個用于計數(shù)的常量 num ，并且返回最后剩下的那個人的名字。

我們使用隊列來模擬一個環(huán)。即假設握著土豆的人位于隊列的頭部。在模擬傳土豆的過程中，程序將這個人的名字移出隊列，然后立刻將其插入隊列的尾部。隨后，這個人會一直等待，直到再次到達隊列的頭部。在出列和入列 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()     # 創(chuàng)建隊列
    for name in nameList:  # 遍歷成員姓名列表
        simqueue.enqueue(name)   # 成員姓名入隊列
    while simqueue.size() > 1:  # 當隊列元素個數(shù)大于1時 循環(huán)執(zhí)行
        for i in range(num):  # 循環(huán)num次(土豆傳遞num次)
            # 成員姓名從隊頭轉換至隊尾
            simqueue.enqueue(simqueue.dequeue())
        # 成員姓名出隊(此成員淘汰出局)
        simqueue.dequeue()
    return simqueue.dequeue()  # 返回隊列里最后剩下的名字

調用 transmitPotato 函數(shù)，使用 7 作為計數(shù)常量，將得到以下結果：

在這里插入圖片描述