抽象數據類型queue的定義

實現了以下數據結構與操作方法的數據類型稱為queue

一、隊列的python實現

• 方法一：標準庫

from queue import Queue

基于list實現

class Queue():def __init__(self):self.items = []def enqueue(self, item):#左邊為rear,右邊為front;即右邊為隊首#insert(0)操作為O（n)self.items.insert(0, item)def dequeue(self):return self.items.pop()def isEmpty(self):return self.items == []def size(self):return len(self.items)

二、隊列應用

2.1 hot potato問題

from queue import Queue#熱土豆/擊鼓傳花問題;從0開始數 def hot_potato(players, num):q = Queue()for player in players:q.enqueue(player)while q.size() > 1:for i in range(num):q.enqueue(q.dequeue())q.dequeue()#循環結束后，只剩下一個playerreturn q.dequeue()if __name__ == '__main__':print(hot_potato(["Bill","David","Susan","Jane","Kent","Brad"],7))

2.2模擬打印機平均等待時間

• 每180秒產生一個打印task
• 每個task打印1-20頁
• 打印機速率有兩種：10頁/min,5頁/min
• 求1小時內task的平均等待時間（進入隊列到彈出隊列）以及未完成的task數目

關鍵：模擬的本質：for i in range(3600) ,遍歷一次代表1秒，而非真正的時間戳

from queue import Queue from random import randrangeclass Printer():def __init__(self, pagerate):#參數1：當前處理任務剩余秒數；參數2：當前任務對象；參數3：每分鐘打印張數self.seconds_ramianing = 0self.current_task = Noneself.pagerate = pageratedef start_task(self,task):self.current_task = taskself.seconds_ramianing = task.get_page()* 60/self.pageratedef tick(self):#減小一個點數；消耗一秒if self.current_task != None:self.seconds_ramianing -= 1if self.seconds_ramianing == 0:self.current_task = Nonedef busy(self):return self.current_task != Noneclass Task():def __init__(self, current_time):self.page = randrange(1,21)self.timestamp = current_timedef wait_time(self,current_time):return current_time - self.timestampdef get_page(self):return self.pagedef task_appear():#隨機發生器，看能否在【1,180】內命中180，命中即判定該秒發生了一個task#該函數執行平均180次有一次成功num = randrange(1,181)return num == 180def simulation(sum_seconds,pages_per_min):#參數1：總的模擬時間；參數2：打印機速率printer = Printer(pages_per_min)task_queue = Queue()wait_times = []for i in range(sum_seconds):#秒為最小模擬單位#模擬task是否產生if task_appear():newtask = Task(i)task_queue.enqueue(newtask)#模擬是否提交task隊列中的taskif not printer.busy() and not task_queue.isEmpty():current_task = task_queue.dequeue()wait_times.append(current_task.wait_time(i))printer.start_task(current_task)#printer計時也要減小printer.tick()#計算平均等待時間ave_wait_time = sum(wait_times)/len(wait_times)print('Average waiting time is {}, and {} tasks remaining!'.format(ave_wait_time,task_queue.size()))if __name__ == '__main__':for i in range(10):simulation(3600, 5)print('*'*100)for i in range(10):simulation(3600, 10)

總結

以上是生活随笔為你收集整理的队列的实现与应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。