投稿:蔡天泊(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
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那里也要有所改动…刚刚没有想到不好意思…