网站源码下载免费源码,网站兼容视图,东营市两学一做考试网站,合肥的网站建设剂屏1.循环队列简介#xff1a;
循环队列是一种队列的实现方式#xff0c;它可以避免队列空间的浪费。循环队列的特点是队列的末尾连接到队列的开头#xff0c;形成一个循环。这样当队列尾部元素达到队列的最大容量时#xff0c;新的元素可以循环地放入队列的开头。这种设计使…1.循环队列简介
循环队列是一种队列的实现方式它可以避免队列空间的浪费。循环队列的特点是队列的末尾连接到队列的开头形成一个循环。这样当队列尾部元素达到队列的最大容量时新的元素可以循环地放入队列的开头。这种设计使得循环队列可以在一定程度上实现队列的循环利用提高了队列的空间利用率。
2.队列及循环队列定义
队列是一种先进先出的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头如下图所示。 普通的顺序队列我们设置队头指针front和队尾指针(rear)来描述队列里的数据存储位置。初始两个指针都指向0号元素如下图所示。 当入队时rear指针向尾部移动front指针则依旧指向首元素如下图所示。 当出队时front指针向下一个元素移动释放出队元素尾指针不变入下图所示。 这就是所谓的队列“假溢出”现象所造成得空间浪费所以我们需要使用循环队列来解决。所谓循环队列就是将队列的头尾相接这样就不会出现上述问题。 但是由于rear指针相当于头指针是不指向元素的所以我们实际的元素数量要比队列空间少一个如下图所示队列总长度为6实际元素个数为5个还有一个被rear指针使用。 3.循环队列代码
# 队空条件rear fornt
# 队满条件(rear1)%MaxSize front(零位置没放元素)
# 元素进队rear (rear1)%MaxSize
# 元素出队front (front1)%MaxSize
MaxSize 5
class CircleQueue: # 循环队列若只剩下一个空位置该循环列表锁定不能再加但其优势在于可边删边加剩两个及以上空位时避免了假溢出def __init__(self):self.data [None] * MaxSize # 初始空间self.front 0self.rear 0def push(self, e): # 元素e进队assert (self.rear 1) % MaxSize ! self.front # 判断队满self.rear (self.rear 1) % MaxSizeself.data[self.rear] edef is_empty(self): # 判断队空return self.rear self.frontdef pop(self): # 元素出队assert not self.is_empty() # 先判断是否为空self.front (self.front 1) % MaxSizereturn self.data[self.front]def gethead(self): # 获取头元素assert not self.is_empty()return self.data[(self.front 1) % MaxSize]def getsize(self): # 获取队列长度在front下标小于rear时size可以直接用rear-front获取但是如果边删边加导致rear小于front此方法出错return (self.rear - self.front MaxSize) % MaxSize #该式满足上叙所有情况def dispaly(self):qself.frontif self.front !self.rear: #判断队空for i in range(self.getsize()):q (q1)%MaxSize #符合两种情况的式子print(self.data[q], end,)else:creturn Nonedef pushk(qu, k, e):n qu.getsize()if k 1 or k n 1: #k必须正常return Falseif k n:for i in range(1, n 1): #边删边进if i k: #插个队它插完后面的再边删边进qu.push(e)x qu.pop()qu.push(x)e1se: qu.push(e)return Truedef popk(qu, k):n qu.getsize()assert 1 k nfor i in range(1, n 1): #和上面的思想一样x qu.pop()if i ! k:qu.push(x)else:e x # 取第k个出队的元素return eif __name____main__:hh CircleQueue()# print(hh.is_empty())# hh.push(0)# hh.push(1)# hh.push(2)# hh.push(3)# print(hh.getsize())# hh.dispaly()
# True
# 4
# 0, 1, 2, 3,
# Process
# finished
# with exit code 0
#当rearfront时# hh.push(3)# hh.push(4)# hh.push(5)# hh.push(6)# hh.pop()# hh.pop()# hh.pop()# hh.push(7)# hh.push(8)# print(hh.getsize())# hh.dispaly()
# 3
# 6,7,8,
# Process finished with exit code 0
#新增两算法调试# hh.push(2)# hh.push(3)# hh.push(4)# hh.dispaly()# hh.pushk(1,50)# print(hh.getsize())# hh.dispaly()
# 2,3,4,4
# 50,2,3,4,
# Process finished with exit code 0
# hh.push(2)
# hh.push(3)
# hh.push(4)
# hh.dispaly()
# hh.popk(1)
# print(hh.getsize())
# hh.dispaly()
# 2,3,4,2
# 3,4,
# Process finished with exit code 0
