解决顺序队列的“假溢出”问题之环形队列（循环队列）

2023-12-21 07:44| 来源: 网络整理| 查看: 265

队列是一种“先进先出”（FIFO）的数据结构，队列有两端，一边只进，一边只出，即：数据从尾部进入，从头部出来，先进去的就会先出来，就像我们平时食堂打饭排队一样，先去排的先打到饭，后去排的后打到饭。

队列通常可以用数组或者是链表实现。这里以数组举例，假设这儿有一个长度为5的数组，左端为头部，负责取出数据，右端为尾部，负责存入数据。

从尾部加入数据A

再从尾部加入数据B

再从尾部加入数据C

从头部取出数据A

再从尾部加入数据D

再从头部取出数据B

再从尾部加入数据E

这时加入数据F却失败了，可是数组的前两个位置明明就是空的，但是却由于数组的最后一个位置有数据导致新数据无法正常加入，这种情况就是“假溢出”。

有人肯定会说，数组中的数据向前移动两位不久可以了吗？这确实可以，但是如果数组的长度很长，那么需要移动的数据量就会非常大，既消耗时间，又消耗性能，所以这种方法不太好。我这里介绍另外一种解决队列“假溢出”问题的方法：环形队列。

环形队列就是将顺序队列首尾相连形成环形结构的队列，这样环形结构的好处就是：只要队列没有真正的满，永远不会溢出

比如上述顺序队列中的例子，若首位相连，那么F就会放到数组的第一个位置上去

下面我使用Python的列表结构实现了该环形队列

注意：环形队列在数据结构上它是一个环形结构，但是在本质上，它还是一个数组（Python中的列表）。

用两个指针分别指向队列的头部（front）和尾部（rear），front和real初始值为-1，若每存入一个数据，则rear加一，若每取出一个数据，则front加一，当rear等于front的时候，表示队列为空，当rear和front之间的差值等于数组长度的时候，表示队列已满。

具体实现如下（有详细注释）：

class CircularQueue: """环形队列""" def __init__(self): """初始化，定义队列容量，定义队列头部指针（front）和尾部指针（rear）""" self.max_queue = 5 self.queue = [None] * self.max_queue self.front = self.rear = -1 def is_empty(self): """判断队列是否为空""" if self.front == self.rear: return True else: return False def is_full(self): """判断队列是否已满""" if self.rear - self.front == self.max_queue: # 用尾部指针和头部指针的距离来判断队列是否已满 return True else: return False def enter_queue(self, data): """向队列中加入数据""" if self.is_full(): # 队列已满就不能加入数据 print("队列已满，无法再加入") else: self.rear += 1 # 尾部指针向后移动一位 data_index = (self.rear + 1) % self.max_queue - 1 # 根据尾部指针计算出新加入的数据应该在列表的哪个位置（索引） if data_index == -1: # 如果data_index == -1，说明该新加入的数据应该在列表的最后一个索引位置 data_index = self.max_queue - 1 # 计算出列表的最后一个索引位置 self.queue[data_index] = data # 将数据放入队列（列表）中 print("加入队列成功") def del_queue(self): """从队列中取出数据""" if self.is_empty(): # 队列已空就不能再取出数据了 print("队列已空，无法再删除") else: self.front += 1 # 头部指针向后移动一位 data_index = self.front % 5 # 计算出需要取出的数据所在列表中的索引位置 data = self.queue[data_index] # 拿到该数据 print("取出数据：", data) self.queue[data_index] = None # 取出后将队列（列表中的该位置重置为None） def show(self): """展示队列""" if self.is_empty(): print("队列为空，无法显示") return num = 0 # 该变量用来计数，表示拿到第几个数据了 while True: num += 1 data_index = (self.front + num) % 5 # 获取当前数据索引 data = self.queue[data_index] # 拿到数据 print(data, end=' ') if self.front + num == self.rear: # 当前情况表示已经拿完了队列中的最后一个数据，所以要跳出循环 break print() if __name__ == '__main__': cir_queue = CircularQueue() while True: num = input("1.存入队列 2.取出队列 3.查看队列 4.退出\n请输入：") if num == '1': try: data = int(input("输入存入数据：")) except ValueError: print("输入数据错误") continue cir_queue.enter_queue(data) elif num == '2': cir_queue.del_queue() elif num == '3': cir_queue.show() elif num == '4': print("成功退出") break else: print("输入选项错误，请重新输入")

部分运行结果如下：

【本文地址】

公司简介

联系我们