python数据结构之队列


概念

与栈相似,队列也是线性结构的一种,队列内部的数据也是有序的。与栈不同的,数据项的添加在队列的一端,称为“队尾”,数据项的删除在队列的另一端,称为“队首”。

每次添加数据在队尾,移除数据在队首,这种排序原则称为先进先出(FIFO),队列只有一个路口和一个出口,不允许从队列中间插入或者删除数据,可以类比日常生活中的排队。

队列有两种常用的操作,入队和出队,在队尾添加数据称为入队(enqueue),从队首将数据项移出称为出队(dequeue)。

实现

与实现栈的方式一样,我们用python基础的数据结构列表list实现队列,将list的首端作为队列的尾端,list的末端作为队列的首端,那么队列的enqueue操作可以用list的insert(0, item)实现,时间复杂度为O(n),队列的dequeue操作可以用list的pop操作实现,时间复杂度为O(1)。

当然首尾也可以倒过来实现,这样入队用append实现,时间复杂度O(1),出队用pop(0)实现,时间复杂度为O(n)。

具体代码如下:

class Queue:
    """
    利用列表实现队列
    列表首端代表队尾,尾端代表队首
    """
    def __init__(self):
        # 将队列初始化为空列表
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        # 将数据item入队
        self.items.insert(0, item)

    def dequeue(self):
        # 将队首元素出队
        return self.items.pop()

    def size(self):
        # 查询队列的长度
        return len(self.items)

    def __str__(self):
        return str(self.items)



def queue_test():
    # 对队列进行测试
    q = Queue()

    print(q.isEmpty())
    q.enqueue(123)
    q.enqueue('abc')
    q.enqueue(True)
    print(q)
    print(q.size())
    q.dequeue()
    q.dequeue()
    print(q.isEmpty())
    print(q)

函数queue_test是测试函数,测试队列类的接口是否可以正确使用,输出结果如下:

True
[True, 'abc', 123]
3
False
[True]

由运行结果可知,队列类的实现没有问题。

队列的应用

现实应用

  • 打印机面向多用户/多程序工作
  • 计算机内部进程的调度
  • 键盘输入

模拟传土豆问题

几个小朋友围成一个圆圈,开始一个小朋友手里有土豆 依次传递土豆num次后,手里有土豆的小朋友退出游戏 其余小朋友继续,直到队列中只剩下一个小朋友,返回该小朋友的名字,即著名的约瑟夫问题。

代码实现:

def hot_potato(namelist, num):
    """
    模拟传土豆问题
    :param namelist: 参与传土豆的人的名字列表
    :param num: 土豆传递的次数
    :return: 剩余的最后一个人的名字
    """
    trans_queue = Queue()
    for name in namelist:
        trans_queue.enqueue(name)

    while trans_queue.size() > 1:
        # 开始传递
        for _ in range(num):
            trans_queue.enqueue(trans_queue.dequeue())
        # 移除队首
        trans_queue.dequeue()

    return trans_queue.dequeue()

模拟打印机问题

平均每天任意一个小时有大约 10 个学生在实验室里,在这一小时中通常每人发起 2 次打印任务,每个打印任务的页数从 1 到 20 页不等。实验室中的打印机比较老旧,如果以草稿模式打印,每分钟可以打印 10 页;打印机可以转换成较高品质的打印模式,但每分钟只能打印 5 页。较慢的打印速度可能会使学生等待太长时间。应该采取哪种打印模式?

分析问题,可以采用模拟打印的方式计算等待时间,需要三个对象,打印机、打印任务、打印队列。每次生成打印任务,将其加入打印队列,如果打印机处于空闲状态,就从队列中取出打印任务进行打印。

模拟打印机代码:

import random

class Printer:
    """模拟打印机"""
    def __init__(self, ppm):
        """
        初始化打印机,有三个属性,
        pagerate:打印机速度,currentTask:当前打印任务,timeRemaining:当前任务剩余时间
        :param ppm: 打印速度,页数/分钟
        """
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def busy(self):
        # 判断打印机当前是否有打印任务
        return False if self.currentTask == None else True

    def tick(self):
        # 打印机打印一秒
        if self.currentTask != None:
            self.timeRemaining -= 1
            if self.timeRemaining <= 0:
                self.currentTask = None

    def startnext(self, newtask):
        # 生成新的打印任务
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60 / self.pagerate

模拟打印任务代码:

class Task:
    """模拟打印任务"""
    def __init__(self, time):
        """初始化打印任务,有两个属性,timestamp:任务生成时间,pages:打印页数"""
        self.timestamp = time
        self.pages = random.randrange(1, 21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages

    def waitTime(self, currentTime):
        # 计算此任务从生成到开始打印的等待时间
        return currentTime - self.timestamp

模拟任务生成代码:

def newPrinterTask():
    """按照1/180的概率生成打印任务"""
    num = random.randrange(1, 181)
    return True if num == 180 else False

模拟打印过程代码:

def simualtion(numSeconds, pagesPerMinute):
    """
    打印机运行模拟程序
    :param numSeconds: 总共模拟运行的时间
    :param pagesPerMinute: 打印机的打印速度,即打印模式
    :return:
    """
    labprinter = Printer(pagesPerMinute)
    printQueue = Queue()
    waitingtimes = []

    for currentSecond in range(numSeconds):

        if newPrinterTask():
            task = Task(currentSecond)
            printQueue.enqueue(task)

        if not labprinter.busy() and not printQueue.isEmpty():
            nexttask = printQueue.dequeue()
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startnext(nexttask)

        labprinter.tick()

    averageWaitTime = sum(waitingtimes) / len(waitingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining." \
          % (averageWaitTime, printQueue.size()))

以不同的打印速度运行打印模拟程序,多次打印求平均值,即可得出应该采用哪种打印模式


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
  目录