python特殊循环队列_队中元素个数代替队尾指针

        对于循环队列来说，如果知道队头指针和队中元素个数，则可以计算出队尾指针。也就是说，可以用队中元素个数代替队尾指针。设计出这种循环队列的判队空、进队、出队和取队头元素的算法。

        本例的循环队列包含data 数组、队头指针 front和队中元素个数count，可以由front 和count求出队尾位置，公式如下。

rear1=(self.front+self.count)% MaxSize

        初始时front和count均置为0。队空条件为count==0；队满条件为count==MaxSize；元素e进队操作是先根据上述公式求出队尾指针rearl，将rear1循环增1，然后将元素e放置在rearl处；出队操作是先将队头指针循环增1，然后取出该位置的元素。设计本例的循环队列类CSqQueuel如下：

#rear=(self.front+self.count)%MaxSize
#队空:count==0
#队满:count==Maxsize
MaxSize = 5
class CircleQueue:  # 循环队列"""这种循环队牛逼之处就是:中元素个数代替尾指针,队满不存在空值,可存Maxsize个元素"""def __init__(self):self.data = [None] * MaxSize  # 初始空间self.front = 0self.count = 0def push(self, e):  # 元素e进队rear=(self.front+self.count)%MaxSize #得到队尾指针assert self.count!=MaxSize # 判断队满rear=(rear+1)%MaxSize #和前面的循环队列一个道理self.data[rear] = eself.count+=1def is_empty(self):  # 判断队空return self.count == 0def pop(self):  # 元素出队assert not self.is_empty()  # 先判断是否为空self.count-=1self.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，此方法出错rear = (self.front + self.count) % MaxSizereturn (rear - self.front + MaxSize) % MaxSize #该式满足上叙所有情况def dispaly(self):q=self.frontif self.count != 0: #判断队空for i in range(self.getsize()):q = (q+1)%MaxSize #符合两种情况的式子print(self.data[q], end=",")else:return 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
# #当rear<front时
#     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