学步园

之前写过一篇博客介绍队列：http://blog.csdn.net/thefutureisour/article/details/7835273

后来发现这个这个队列是有问题的：

bool enQueue(Queue *q,ElemType e)
{
	//如果队列已满，重新分配内存
	if(q->rear == q->Qsize-1)
	{
		q->data = (ElemType*)realloc(q->data,2*q->Qsize*sizeof(ElemType));
		if(q->data == NULL)
			return false;
		else
			q->Qsize *= 2;
	}
	//先赋值，然后队尾循环加1
	q->data[q->rear] = e;
	q->rear = (q->rear+1)%q->Qsize;
	return true;

}

这个判断队列满的办法明显是错误的，因为有可能在多次出队、入队操作以后，data[1]代表rear，data[0]代表front，此时队列已经满了应该重新分配内存，而这个程序并没有做出正确的判断。然后我对作了修改，改成了

if(Qlength(q) == q->Qsize-1)

这个代码看似正确，但是如果进行下面的测试，就会发现问题了：

	int a = 100;
	Queue myQueue;
	
	initQueue(&myQueue,4);
	//先把队列充满
	for(int i = 0 ; i < 3 ;++i)
		enQueue(&myQueue,i);
	printQueue(&myQueue);
	
	deQueue(&myQueue,&a);	
	enQueue(&myQueue,3);
	printQueue(&myQueue);

	deQueue(&myQueue,&a);	
	enQueue(&myQueue,4);
	printQueue(&myQueue);

	enQueue(&myQueue,5);
	printQueue(&myQueue);

	destroyQueue(&myQueue);

最后一次入队5以后，打印为空，通过单步调试，我发现问题因为此时Qlength的返回值为0.我才恍然大悟，问题的严重性：

当data[0]为rear而data[1]为front时，虽然这时候队列实际已经满了，我也重新分配了内存，但是rear和front下标却没有修改，进而导致重新分配的后的数组是类似于下面的结构：

data      0         1         2         3         4         5         6         7

             rear     front    数据   数据    {      新分配的空间      }

首先：enqueue以后rear会++，所以此时会出现Qlength为0，其次这已经完全不是循环队列的结构了，rear的前一个数据是没有初始化的内存。

怎么解决这个问题呢？

我也没有特别高明的办法，只能重新分配的时候新建一个数组，数组中的元素按照队列从头至尾的顺序保存，然后重新分配内存之后，把新内存的前Qsize-1个元素用新建的数组初始化，然后把rear置为Qsize，新来的元素放到rear的位置，然后rear再自增。这样就搞定了：

bool enQueue(Queue *q,ElemType e)
{
	//如果队列已满，重新分配内存
	if(q->Qsize-1 == Qlength(q))
	{
		//先把原来的按顺序记录在tmp中
		ElemType* tmp = (ElemType*)malloc(sizeof(ElemType) * q->Qsize);
		for(int i = 0; i< q->Qsize-1;++i)	
		{
			tmp[i] = q->data[(q->front+i+q->Qsize)%q->Qsize];
		}
		//重新分配内存
		q->data = (ElemType*)realloc(q->data,2*q->Qsize*sizeof(ElemType));
		if(q->data == NULL)
			return false;
		//用tmp初始化q->data
		for(int i = 0; i< q->Qsize-1;++i)
		{
			q->data[i] = tmp[i];
		}

		//重新设定front、rear标记
		q->front= 0;
		q->rear = q->Qsize;
		//新来的元素放入队尾
		q->data[q->Qsize] = e;
		//队尾指针自增
		q->rear++;
		//容量翻倍
		q->Qsize *= 2;
		free(tmp);
	}
	else
	{
		//先赋值，然后队尾循环加1
		q->data[q->rear] = e;
		q->rear = (q->rear+1)%q->Qsize;
	}
	return true;

}

由于时间匆忙，可能会有小的纰漏，但是大方向上应该是没有问题的。