循环队列
循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。 [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