【数据结构初阶第十二节】设计循环队列

云边有个稻草人-CSDN博客

必须有为成功付出代价的决心，然后想办法付出这个代价。

还有最后一道关于队列的习题，这题有点难，准备好迎接挑战吧！

1.【题目】

2.实现循环队列推荐用数组，Why?

3.Q1：如何来判断队列是满的？

4.上代码！

5.【注意】

这题得多画图理解，不能空想，而且要结合我写代码中穿插的注释，这样就会好理解点

1.【题目】

2.实现循环队列推荐用数组，Why?

链表：如果像我们实现队列一样使用链表，定义两个指针，phead为头删除数据，ptail为尾插入数据，一开始每次插入数据都要申请节点，在队列满了之后，我们在队头删除数据，之后再要插入数据时我们就要判断要插入的节点数据是否为空，节点虽在，但内容数据被删掉了，此时需要status来存储节点的状态，记录空还是非空，比较麻烦。

数组：直接申请一块连续的空间，不需要像链表那样不断申请结点，也不需要指针来指来指去。定义两个变量，front 和 rear 分别指向队头和队尾，往 rear 指向的位置插入数据，之后 rear++，在 front 指向的位置删除数据，之后 front++。大体思路就是这样，操作比链表要简单。但是还有很多细节需要去补充调整，接下来跟着我的思路开始。

3.Q1：如何来判断队列是满的？

一开始 front 和 rear 都指向下标为0的位置，此时队列为空，每插入一次数据 rear 都要++指向下一个位置，因为是循环队列所以当队列插满的时候 rear 和 front 指向同一个位置，这时我们发现队列满时和队列为空时都是 rear == front ，那么该如何分辨队列满和为空时？

A1：如上图所示，我们多申请一个空间，一开始 front 和 rear 还是指向同一个位置（此时front 和 rear 相等，循环队列为空），假如我们要插入4（k）个数据为满，插入完最后一个数据时 rear 指向多申请的那个空间，此时队列满了，按照（rear+1）% （k+1）== front，为满，这样我们就可以分清何时为满何时为空了。

4.上代码！

//创建循环队列的结构
typedef struct {int* arr;int front;int rear;int capacity;
} MyCircularQueue;//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));pst->arr = (int*)malloc(sizeof(int)*(k+1));pst->front = pst->rear = 0;pst->capacity = k;return pst;
}//判断队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1) % (obj->capacity+1) == obj->front;
}//向循环队列里面插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear++] = value;//防止rear越界obj->rear %= obj->capacity+1;return true;
}//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列不为空if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;//防止front越界obj->front %= obj->capacity+1;return true;
}//取循环队列队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}//取循环队列队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//return obj->arr[obj->rear-1];//但是当rear == 0时，指向队头第一个位置时，rear-1 == -1，//此时出现错误,需要我们特殊处理一下int prev = obj->rear-1;if(prev == -1){prev = obj->capacity;}return obj->arr[prev];
}//销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);obj->arr = NULL;free(obj);obj = NULL;
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

5.【注意】

在取队尾元素的时候，是取 rear-1 指向的元素，若 rear-1 == -1，我们就需要特殊处理一下，具体详见代码。
在实现操作的时候我们要注意 front 和 rear 不能越界，obj->front %= obj->capacity，这样之后就从越界的位置变成下标为0的位置，如果没有越界，这样操作也不会改变 front 和 rear 的原始值。
我们申请的空间是比要存储数据的空间多一个。
我们定义一个 capacity 来保存要存储有效数据的个数。

这道题还是比较难的，我们需要多多思考细节思路+回顾敲代码。

完——