线性结构之----队列
程序员文章站
2024-03-18 12:04:46
...
什么是队列?
队列是一种有次序的数据集合,其特征是新数据项的添加总发生在一段(通常称为"尾端"),而现存数据项的移除总发生在另一端(通常"首端")
队列的例子
当数据项加入队列,首先出现在队尾,随着队首数据项的移除,他逐渐接近队首
我们生活中常说的,左耳朵进右耳朵出就是一个队列类型的
遵循的次序:先进先出(FIFO:First-in-first-out)
比如排队,队列仅有一个入口和一个出口,不允许插队,也不允许从中间移除
再比如,我们打印机打印任务,也是遵循FIFO形式,有任务正在打印,其他后加入任务的只能一个个排队,挨个打印
比如进程调度,也是遵循FIFO原则。因为进程数远多于CPU核心数,并且有的进程还要等待不同类型I/O事件,所以调度原则遵循“先到西安服务”及“资源充分利用”
这种例子在生活和我们实际开发的例子非常多,还有例如事务中,各个事务要让他有序执行,不发生死锁,就要遵循先到先服务的原则
队列的基本操作
-
Queue():创建一个空队列对象,返回值为Quene对象
-
enqueue(item):将数据项item添加到队尾,无返回值
-
dequeue():从队首移除数据项,返回值为队首数据项,队列被修改
-
isEmpty():测试是否空队列,返回值为布尔值
-
size():返回队列的数据项的个数
python实现ADT Quenue
采用List来容纳队列的数据项
将List首端作为队列首端
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
队列应用:打印机
多人共享一台打印机,采取“先到先服务”得队列策略来执行打印任务
用面向对象的思想来对问题进行建模,模拟打印任务
对象:打印任务(提交的时间,打印页数),打印队列(具有FIFO性质),打印机(打印速度,是否忙)
from pythonds.basic.queue import Queue
import random
import time
# 打印机的类
class Printer:
def __init__(self, ppm):
# 初始化打印速度
self.pagerate = ppm
# 初始化打印任务,为None
self.currentTask = None
# 任务倒计时
self.timeRemaining = 0
# 打印方法
def tick(self):
# 当前有打印的任务
if self.currentTask != None:
# 给倒计时减1秒
self.timeRemaining = self.timeRemaining - 1
# 如果减着减着小于或等于0了,那就是任务执行完毕了
if self.timeRemaining <= 0:
self.currentTask = None
# 判断打印机是否在忙
def busy(self):
# 不是None,忙
if self.currentTask != None:
return True
# 为不忙
else:
return False
# 开始打印新的作业
def startNext(self, newtask):
# 把当前的打印作业设置为传入的任务
self.currentTask = newtask
# 计算这个作业需要打印多久
self.timeRemaining = newtask.getPages() * 60 / self.pagerate
# 打印作业对象类
class Task:
def __init__(self, time):
# 时间戳,什么时候生成的
self.timestamp = time
# 指定打印的作业有多少页
self.pages = random.randrange(1, 20)
# 返回时间戳
def getStamp(self):
return self.timestamp
# 返回多少页
def getPages(self):
return self.pages
# 等了多久时间,当前时间-生成时间
def waitTime(self, currenttime):
return currenttime - self.timestamp
# 新生成打印作业类
def newPrintTask():
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
def simulation(numSeconds, pagesPerMinute):
# 创建打印对象
labprinter = Printer(pagesPerMinute)
# 生成空队列
printQueue = Queue()
# 等待的是时间放到列表中
waitingtimes = []
# 遍历时间
for currentSecond in range(numSeconds):
# 当这一秒有打印的概率,就开始打印
if newPrintTask():
# 生成一个任务对象
task = Task(currentSecond)
# 把任务对象放入到队列中
printQueue.enqueue(task)
# 如果打印机不忙,并且不为空
if (not labprinter.busy()) and (not printQueue.isEmpty()):
# 把任务队列中的task取出来
nexttask = printQueue.dequeue()
# 把他的等待时间加入到waitingtimes列表中
waitingtimes.append(nexttask.waitTime(currentSecond))
# 开始作业的打印
labprinter.startNext(nexttask)
labprinter.tick()
# 计算平均时间
averageWait = sum(waitingtimes) / len(waitingtimes)
print('Average Wait %6.2f secs %3d tasks remaining' % (averageWait, printQueue.size()))
if __name__ == '__main__':
for i in range(10):
simulation(3600, 5)
以上就是队列的概念和应用,有哪些不对的,欢迎来撩
上一篇: 栈实现队列
下一篇: 数据结构-线性结构之队列