数据结构之python实现循环顺序队列
定义:
对于普通顺序队列,可能队列提示已满,但其实队头还有空位置,这时候就可以考虑用循环顺序队列,把新元素放在队头的空闲位置。循环顺序队列中的元素恒为(rear-front+MaxQueueSize)%MaxQueueSize,其中队空的条件为front = rear;队满的条件为front = (rear+1)%MaxQueueSize。
需要注意的是虽然如此,队头与队尾依旧还是front+1和rear位置,这就使得依旧是先进先出,没有违背原则。
python实现:
class CircularSequenceQueue():
def __init__(self):
self.MaxQueueSize = 10
self.s = [None for x in range(0,self.MaxQueueSize)]
self.front = 0
self.rear = 0
'''当前队列是否为空'''
def IsEmptyQueue(self):
if self.front == self.rear:
iQueue = True
else:
iQueue = False
return iQueue
'''获取队头元素'''
def GetHead(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
return self.s[self.front+1]
'''获取队列长度'''
def GetQueueLength(self):
return (self.rear - self.front+self.MaxQueueSize) % self.MaxQueueSize
'''元素进队'''
def EnQueue(self,x):
if (self.rear+1)% self.MaxQueueSize != self.front:
self.rear = (self.rear+1)% self.MaxQueueSize
self.s[self.rear] = x
print("当前进队元素为:",x)
else:
print("队列已满")
return
'''元素出队'''
def DeQueue(self):
if self.IsEmptyQueue():
print("队列为空")
else:
self.front = (self.front+1)% self.MaxQueueSize
return self.s[self.front]
'''创建队列'''
def CreateQueueByInput(self):
data = input("请输入入队元素(回车确定,#结束):")
while data != "#":
self.EnQueue(data)
data = input("请输入入队元素(回车确定,#结束):")
'''遍历顺序队列内的所有元素'''
def QueueTraverse(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
while self.front != self.rear:
result = self.DeQueue()
print(result)
sq = SequenceQueue()
sq.CreateQueueByInput() #在此处输入8个数,最多可以放入最大值-2个元素
print("循环顺序队列长度为:",sq.GetQueueLength())
sq.DeQueue()
sq.EnQueue(10)
print("循环顺序队列的元素为:")
sq. QueueTraverse()
结果如下: