循环队列判满和判空的两种方式

时间:2024-03-29 09:38:30

  在循环队列中,Q.front表示对头,Q.rear表示队尾。因为队列大小是有限的,所以在队列指针移动的时候,会出现到头的情况,这时候需要指针回到起点。

所以入队时Q.rear=Q.rear+1%Maxsize,出队时,Q.front=Q.front+1%Maxsize.而如果一个队列是如下这种结构

 

循环队列判满和判空的两种方式

  • 在这种结构下,当出现队列满和队列空的情况,这两种情况是一样的,Q.rear=Q.front.为空,一直移除,Q.front一直与rear接近在这种结构下,当出现队列满和队列空的情况,这两种情况是一样的,Q.rear=Q.front.为空,一直移除,Q.front一直与rear接近,入队时,一直增大rear,直到等于front。在这种情况下,是无法判断谁是空,谁是满,所以有了另外的一些小处理。

  • 在这两种结构下都是队列满,但是第二种是Q.rear指向空,下一位是Q.front才代表队列满。所以牺牲了一个空间,而这种情况下,Q.rear=Q.front代表队列空,也就区分开了,还可以把Q.front指向空下一位是第一个元素,这样的话,就会出现Q.front下一位是Q.rear代表空,而Q.rear=Q.front代表队列满,这与刚刚的方式是相反的。
  • 循环队列判满和判空的两种方式