欢迎光临散文网 会员登陆 & 注册

循环队列

2021-06-09 00:05 作者:呜啦拉辣蜡腊喇  | 我要投稿

循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。 [1]  循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。

循环队列的相关条件和公式:

1.队空条件:
  rear==front
 
2.队满条件:
  (rear+1) %QueueSize==front,其中QueueSize为循环队列的最大长度
 
3.计算队列长度:
  (rear-front+QueueSize)%QueueSize
 
4.入队:
  (rear+1)%QueueSize
 
5.出队:
  (front+1)%QueueSize

例如
一共10个元素 M=10
先入队9个元素,队头指向最后一个 即9
然后 出队5个元素,队尾指向5
再入队三个元素, 队头指向2
这是队内实际个数为(2-5+10)%10 = 7个

至于为什么要加上%
是因为 当F=9 R=5的时候 (9-5+10)=14 14%10才是正确结果4

循环队列的评论 (共 条)

分享到微博请遵守国家法律