循环队列

 

相信绝大多数都学习过《数据结构》这门课程，而对这门课程里最熟悉的应该是堆栈和队列。本人前段时间买了一本有关算法（C语言实现）的书，发现其中对循环队列这一结构的算法存在漏洞，故写此文与大家交流探讨。

首先提一下循环队列的概念：队头指针head,队尾指针tail。

很显然，当队列满后，即便全部元素都出队，队列还是满的状态。这种情况就叫做“假溢出”，即数组中明明有可用空间，但却无法使用。

 

这是由定长数组的特性决定的。但我们可用改变一下思路，当队尾指针指向数组最后一个位置时，如果再有数据入队，并且队头指针没有指向数组的第一个元素，那么就让队为指针绕回到数组头部。这样就形成了一个逻辑上的环 即（循环队列）。

注：以上对循环队列的介绍系转载一高人博客。

书中所述对循环队列的代码如下：

 

#define MAXSIZE 10
typedef struct _QUEUE
{
  int elems [ MAXSIZE ] ;
  int front,rear;
}QUEUE;

int Initialize(QUEUE *queue)/*初始化队列*/
{
  queue->front=queue->rear=0;
}
int InQueue(QUEUE *queue,int x)/*元素‘x’入队函数*/
{
  if (((queue->rear+1) % MAXSIZE)==queue->front)
   {
     printf("Queue is overflow!\n");
     return 0;
   }

  queue->rear=(queue->rear+1)% MAXSIZE;
  queue->elems [ queue->rear ] =x;
}
int OutQueue(QUEUE *queue)/*出队函数*/
{
  if (queue->rear==queue->front)
   {
     printf("Queue is Empty!\n");
     return 0;
   }
  queue->front=(queue->front+1)% MAXSIZE;
}
int Show(QUEUE *queue)/*显示整个队列*/
{
  int i=(queue->front+1)%MAXSIZE;
  if (queue->front==queue->rear)
   {
     printf("Queue is Empty!\n");
     return 0;
   }
  for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE))
  {
     printf("queue->elems [ %d ] =%d\n ",i,queue->elems [ i ] );
  } 
   printf("\nQueue head is %d\n",queue->front);
   printf("Queue rear is %d\n",queue->rear);
}

 

 所有问题就出在 Show(QUEUE *queue) 这个函数上，我们做第一个测试代码：

 

main()
{
 /*Initialize a queue and show it.*/
 QUEUE queue;
 Initialize(&queue);
 Show(&queue);

 /*Add elems int a queue and show it.*/
 InQueue(&queue,1);
 InQueue(&queue,2);
 InQueue(&queue,3);
 InQueue(&queue,4);
 InQueue(&queue,5);
 InQueue(&queue,6);
 InQueue(&queue,7);
 InQueue(&queue,8);
 InQueue(&queue,9);
 Show(&queue);
}

 由于队列中始终要有一个空元素，根据此段代码定义 #define MAXSIZE 10 ，所以实际队列最多存在9个元素。但我们运行程序以后会发现程序陷入死循环，即循环打印整个队列，截图如下：

 

经分析出现死循环的原因很简单，在 Show(QUEUE *queue) 里的循环条件：

for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE)) ，在上述测试代码下，9个元素入队后，

queue->front=0,queue->rear=9,FOR语句在此条件下即为：for(i=(0+1)%10;i<=9;i=((i+1)%MAXSIZE)) ,当i=9,

执行 printf("queue->elems [ %d ] =%d\n ",9,queue->elems [ 9 ] ); 之后，i=(9+1)%10,即 i 又变为 0 ，又重新符合 i<=9 的循环条件，如此反复，陷入死循环。

该程序还有个漏洞。我们来做第二个测试代码：

 

main()
{
 /*Initialize a queue and show it.*/

 QUEUE queue;
 Initialize(&queue);
 
 /*Add elems int a queue and show it.*/
 InQueue(&queue,1);
 InQueue(&queue,2);
 InQueue(&queue,3);
 InQueue(&queue,4);
 InQueue(&queue,5);
 InQueue(&queue,6);
 InQueue(&queue,7);
 InQueue(&queue,8);
 InQueue(&queue,9);
 
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 InQueue(&queue,11);
 InQueue(&queue,10);
 Show(&queue);
 
}

 这段代码运行后，发现它根本没有显示整个队列。运行结果截图如下：

 

分析原因：在上述测试代码下，先是9个元素入队，5个元素出队，又2个元素入队，即 queue->front=5 , queue->rear=1 。在此条件下，for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE))   就变成

for(i=(5+1)%10;i<=1;i=((i+1)%MAXSIZE)) ，从一开始就不符合 i<=1 的条件 ，故循环体没有执行。

故，Show(QUEUE *queue) 函数代码有严重漏洞。发现此问题后，本想偷懒，写封邮件给作者，希望他能修改代码，可能是作者又忙着出别的什么书了，没功夫陪我们“小孩”玩。“被逼无奈”之下，自己重写Show(QUEUE *queue) 函数，只要能摆平以上两个Bug就成。

经分析发现，若我们将循环队列看成一个首尾相连的火车轨道，无论是入队还是出队， queue->front 和 queue->rear 都是顺时针方向运动的，故新的 Show 函数如下：

 

int Show(QUEUE *queue)
{
  int i=(queue->front+1)%MAXSIZE;
  if (queue->front==queue->rear)
   {
     printf("Queue is Empty!\n");
     return 0;
   }

 while(i!=queue->rear)
 {
   printf("queue->elems [ %d ] =%d\n",i,queue->elems [ i ] );
   i=(i+1)%MAXSIZE;
 }
   if(i==queue->rear)/*如果不加这句，此程序将有一个Bug，即队尾元素（最后一个元素）打印不出来*/
   {
    printf("queue->elems [ %d ] =%d\n",i,queue->elems [ i ] );
   }
   printf("\nQueue head is %d\n",queue->front);
   printf("Queue rear is %d\n",queue->rear);
}

 经初步测试，上文所述的两个BUG不会出现。但感觉代码写的有点窝囊，由于本人水平与学识的限制，不排除会被大本营的高人找出Bug，希望大家能写出更好的代码，供大家交流学习。

 

转自：http://student.csdn.net/space.php?uid=50992&do=blog&id=20368