【严蔚敏】数据结构 在C语言中不能用动态分配的一维数组来实现循环队列

【严蔚敏】数据结构 在C语言中不能用动态分配的一维数组来实现循环队列

对于这个问题的考虑源于我在做2019-408真题的算法设计题时想到的方案：
原题目如下：

#define MAXSIZE 50
typedef struct{
ElemType data;
int front,rear;
int length = MAXSIZE;
}SqQueue;
void InQueue(SqQueue &Q, ElemType x)
{
if(Q.front==(Q.rear+1)%Q.length)
{
ElemType base = (ElemType)realloc(Q.data,sizeof(ElemType)(Q.length+MAXSIZE));
Q.data = base;
Q.length += MAXSIZE;
}
Q.data[rear] = x;
Q.rear = (Q.rear + 1) % Q.length;
}
bool DeQueue(SqQueue &Q, ElemType &x)
{
if(Q.front==Q.rear) return false;
x = Q.data[front];
Q.front = (Q.front+1)%Q.length;
return true;
}

然后翻阅严蔚敏的数据结构发现，关于循环队列的动态分配是这么说的：在C语言中不能用动态分配的一维数组来实现循环队列。

其实循环队列可以实现动态分配，在队列满时再开辟一个新的连续的更大的空间，但我的实现方法有问题，只有当rear大于front时，上述代码才能实现循环队列的动态分配，因为此时rear+1指向的新开辟空间的第一个空的位置，而如果front大于rear，此时rear+1指向的就不是新开辟空间的第一个空的位置，该情况需要重新修改front和rear指针，front指向新开辟空间的第一个位置，rear指向新开辟空间的第一个空的位置即可。

综上，循环队列是可以实现动态分配内存空间的，只不过修改指针的过程略有复杂，故常采用开辟一片较大的连续空间来实现队列元素的存放。