快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法中的隊(duì)列詳解(2)

更新時(shí)間：2022年03月09日 16:52:51 作者：姜學(xué)遷

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

傳土豆

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

在這里插入圖片描述

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

我們使用隊(duì)列來(lái)模擬一個(gè)環(huán)。即假設(shè)握著土豆的人位于隊(duì)列的頭部。在模擬傳土豆的過(guò)程中，程序?qū)⑦@個(gè)人的名字移出隊(duì)列，然后立刻將其插入隊(duì)列的尾部。隨后，這個(gè)人會(huì)一直等待，直到再次到達(dá)隊(duì)列的頭部。在出列和入列 num 次之后，此時(shí)位于隊(duì)列頭部的人出局，新一輪游戲開始。如此反復(fù)，直到隊(duì)列中只剩下一個(gè)名字（即隊(duì)列的大小為 1）。

class Queue:
    def __init__(self):
        self.items = []            # 構(gòu)建空隊(duì)列
    def isEmpty(self):
        return self.items ==[]     # 判斷是否為空
    def enqueue(self,item):
        self.items.insert(0, item) # 在隊(duì)列尾部(列表左端)插入元素
    def dequeue(self):
        return self.items.pop()    # 在隊(duì)列頭部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 隊(duì)列(列表)長(zhǎng)度
    def look(self):
        print(self.items)
        
def transmitPotato(nameList, num):
    simqueue = Queue()     # 創(chuàng)建隊(duì)列
    for name in nameList:  # 遍歷成員姓名列表
        simqueue.enqueue(name)   # 成員姓名入隊(duì)列
    while simqueue.size() > 1:  # 當(dāng)隊(duì)列元素個(gè)數(shù)大于1時(shí) 循環(huán)執(zhí)行
        for i in range(num):  # 循環(huán)num次(土豆傳遞num次)
            # 成員姓名從隊(duì)頭轉(zhuǎn)換至隊(duì)尾
            simqueue.enqueue(simqueue.dequeue())
        # 成員姓名出隊(duì)(此成員淘汰出局)
        simqueue.dequeue()
    return simqueue.dequeue()  # 返回隊(duì)列里最后剩下的名字

調(diào)用 transmitPotato 函數(shù)，使用 7 作為計(jì)數(shù)常量，將得到以下結(jié)果：

在這里插入圖片描述

注意，在上例中，計(jì)數(shù)常量大于列表中的名字個(gè)數(shù)。這不會(huì)造成問(wèn)題，因?yàn)殛?duì)列模擬了一個(gè)環(huán)。同時(shí)需要注意，當(dāng)名字列表載入隊(duì)列時(shí)，列表中的第一個(gè)名字出現(xiàn)在隊(duì)列的頭部。在上例中，小明是列表中的第一個(gè)元素，因此處在隊(duì)列的最前端。