Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列詳解
本文實(shí)例講述了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列。分享給大家供大家參考。具體分析如下：
一、概述
隊(duì)列（Queue）是一種先進(jìn)先出（FIFO）的線性數(shù)據(jù)結(jié)構(gòu)，插入操作在隊(duì)尾（rear）進(jìn)行，刪除操作在隊(duì)首（front）進(jìn)行。
二、ADT
隊(duì)列ADT（抽象數(shù)據(jù)類型）一般提供以下接口：
① Queue() 創(chuàng)建隊(duì)列
② enqueue(item) 向隊(duì)尾插入項(xiàng)
③ dequeue() 返回隊(duì)首的項(xiàng)，并從隊(duì)列中刪除該項(xiàng)
④ empty() 判斷隊(duì)列是否為空
⑤ size() 返回隊(duì)列中項(xiàng)的個(gè)數(shù)
隊(duì)列操作的示意圖如下：
三、Python實(shí)現(xiàn)
使用Python的內(nèi)建類型list列表，可以很方便地實(shí)現(xiàn)隊(duì)列ADT：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def empty(self):
return self.size() == 0
def size(self):
return len(self.items)
四、應(yīng)用
著名的 約瑟夫斯問(wèn)題（Josephus Problem）是應(yīng)用隊(duì)列（確切地說(shuō)，是循環(huán)隊(duì)列）的典型案例。在 約瑟夫斯問(wèn)題 中，參與者圍成一個(gè)圓圈，從某個(gè)人（隊(duì)首）開(kāi)始報(bào)數(shù)，報(bào)數(shù)到n+1的人退出圓圈，然后從退出人的下一位重新開(kāi)始報(bào)數(shù)；重復(fù)以上動(dòng)作，直到只剩下一個(gè)人為止。
值得注意的是，Queue類只實(shí)現(xiàn)了簡(jiǎn)單隊(duì)列，上述問(wèn)題實(shí)際上需要用循環(huán)隊(duì)列來(lái)解決。在報(bào)數(shù)過(guò)程中，通過(guò)“將（從隊(duì)首）出隊(duì)的人再入隊(duì)（到隊(duì)尾）”來(lái)模擬循環(huán)隊(duì)列的行為。具體代碼如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def josephus(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in xrange(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
if __name__ == '__main__':
print(josephus(["Bill", "David", "Kent", "Jane", "Susan", "Brad"], 3))
運(yùn)行結(jié)果：
$ python josephus.py Susan
希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了解讀Python中字典的key都可以是什么，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-09-09
Python tkinter實(shí)現(xiàn)桌面軟件流程詳解
這篇文章主要介紹了Python tkinter做一個(gè)好用的桌面軟件，100%你會(huì)愛(ài)上它，文中的示例代碼講解詳細(xì)，快跟小編一起動(dòng)手試一試吧2022-10-10
這篇文章主要介紹了fastapi框架異步執(zhí)行踩坑記錄,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-06-06
Python3實(shí)現(xiàn)生成隨機(jī)密碼的方法
這篇文章主要介紹了Python3實(shí)現(xiàn)生成隨機(jī)密碼的方法,是Python程序設(shè)計(jì)中非常實(shí)用的一個(gè)技巧,需要的朋友可以參考下2014-08-08
django celery redis使用具體實(shí)踐
這篇文章主要介紹了django celery redis使用具體實(shí)踐，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
對(duì)python中數(shù)據(jù)集劃分函數(shù)StratifiedShuffleSplit的使用詳解
今天小編就為大家分享一篇對(duì)python中數(shù)據(jù)集劃分函數(shù)StratifiedShuffleSplit的使用詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-12-12
PIL庫(kù)支持圖像存儲(chǔ)、顯示和處理,它能夠處理幾乎所有圖片格式,可以完成對(duì)圖像的縮放、剪裁、疊加以及向圖像添加線條、圖像和文字等操作,下面這篇文章主要給大家介紹了關(guān)于Python使用PIL.image保存圖片的相關(guān)資料,需要的朋友可以參考下2022-12-12
python網(wǎng)絡(luò)編程tcp客戶端及服務(wù)端解讀
Python的socket模塊提供了基本的網(wǎng)絡(luò)通信功能,包括創(chuàng)建socket對(duì)象、綁定地址、監(jiān)聽(tīng)連接、接受連接、發(fā)送和接收數(shù)據(jù)以及關(guān)閉連接等,TCP和UDP是常用的網(wǎng)絡(luò)協(xié)議,IP地址和端口號(hào)用于標(biāo)識(shí)通信端點(diǎn),通過(guò)這些功能,可以實(shí)現(xiàn)客戶端和服務(wù)器之間的網(wǎng)絡(luò)通信2025-01-01
langchain Prompt大語(yǔ)言模型使用技巧詳解
這篇文章主要為大家介紹了langchain Prompt大語(yǔ)言模型使用技巧詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07
這篇文章主要介紹了Python操作列表，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03