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