数据结构之 |
您所在的位置：网站首页 › 循环队列实现约瑟夫环的条件是 › 数据结构之 |
数据结构之
|
栈是先入后出，与之相反的是队列，队列是先进先出的线性结构。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。  这里写图片描述图1 队列的定义 队列的存储结构中使用的最多的是循环队列。循环队列包括两个指针， front 指针指向队头元素， rear 指针指向队尾元素的下一个位置。 队列为空的判断条件是： front == rear 队列满的判断条件是： (rear+1)%maxsize == front 队列长度的计算公式： (rear-front+maxsize)%maxsize 具体的python实现代码如下： 代码语言：javascript复制class SqQueue(object): def __init__(self, maxsize): self.queue = [None] * maxsize self.maxsize = maxsize self.front = 0 self.rear = 0 # 返回当前队列的长度 def QueueLength(self): return (self.rear - self.front + self.maxsize) % self.maxsize # 如果队列未满，则在队尾插入元素，时间复杂度O(1) def EnQueue(self, data): if (self.rear + 1) % self.maxsize == self.front: print("The queue is full!") else: self.queue[self.rear] = data # self.queue.insert(self.rear,data) self.rear = (self.rear + 1) % self.maxsize # 如果队列不为空，则删除队头的元素,时间复杂度O(1) def DeQueue(self): if self.rear == self.front: print("The queue is empty!") else: data = self.queue[self.front] self.queue[self.front] = None self.front = (self.front + 1) % self.maxsize return data # 输出队列中的元素 def ShowQueue(self): for i in range(self.maxsize): print(self.queue[i],end=',') print(' ') # 测试程序 if __name__ == "__main__": # 建立大小为15的循环队列 q = SqQueue(15) # 0~9入队列 for i in range(10): q.EnQueue(i) q.ShowQueue() # 删除队头的5个元素：0~4 for i in range(5): q.DeQueue() q.ShowQueue() # 从队尾增加8个元素：0~7 for i in range(8): q.EnQueue(i) q.ShowQueue()程序输出的结果为： 0,1,2,3,4,5,6,7,8,9,None,None,None,None,None, None,None,None,None,None,5,6,7,8,9,None,None,None,None,None, 5,6,7,None,None,5,6,7,8,9,0,1,2,3,4, |
【本文地址】
今日新闻 |
推荐新闻 |