“enqueue和dequeue复杂度均为O(1)”的队列实现

投稿:蔡天泊(1300018705)


class queue2(object):#做了一个enqueue和dequeue的时间复杂度都为O(1)的简易队列类型,如有疏漏请多多指教...以及感谢老师和助教gg之前的改进建议〜
    def __init__(self):
        self.dic={}
        self.FrontNum=0
        self.EndNum=0
    def enqueue(self,ToAdd):#木有设返回值
        self.dic[self.EndNum]=ToAdd
        self.EndNum+=1#EndNum实际上表示的是队尾之后一位的key,但以下注释里就写成它“表示队尾位置”了〜
    def dequeue(self):
        a=self.dic[self.FrontNum]
        del self.dic[self.FrontNum]
        self.FrontNum+=1#EndNum实际上是队首之后一位的key,但以下注释里就写成它“表示队首位置”了〜
        return a
    def isEmpty(self):
        return self.dic=={}
    def size(self):
        return self.EndNum-self.FrontNum#继续利用已有的队尾和队首位置来减小复杂度
    __len__=size

2 条关于 ““enqueue和dequeue复杂度均为O(1)”的队列实现”的评论

  1. def dequeue(self):
    a=self.dic[self.FrontNum]
    del self.dic[self.FrontNum]
    self.FrontNum+=1
    经测试,本文中写成的queue2在dequeue时效率会略低于pythonds里Queue的dequeue…个人认为原因在于上述代码中“del self.dic[self.FrontNum]”这句话。如果不写这句话,queue2仍可正常使用且dequeue的效率和pythonds里Queue基本持平,但缺点是会浪费不少存储空间…个人觉得,如果想平衡时间复杂度和空间复杂度的话,还是保留这句话为好

    • 如果”del self.dic[self.FrontNum]”这句话被删掉了的话,isEmpty那里也要有所改动…刚刚没有想到不好意思…

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

*

code