欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线性结构之----队列

程序员文章站 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)

以上就是队列的概念和应用,有哪些不对的,欢迎来撩