另外扩展一下，实际中我们有时还会使用一种队列叫循环队列。它可以重复利用之前的空间。如操作系统课程讲解生产者消费者模型时就会使用循环队列。环形队列可以用数组实现，也可以用循环链表实现。多数都是用循环链表实现的。本文嘞，两个都实现一下吧！
正文开始@边通书
1. 题目
题目链接：设计循环队列
注意：
无论是数组实现还是链表实现，都要多开一个空间，否则无法区分判空判满。即要存k个数据的循环队列，要开(k+1)个空间。
写的过程也是出现了各种各样的小问题，它们都化作小注意写在文章中了。
2. 用循环链表实现循环队列
2.1 思路
思路无非是实现题目要求，做过队列基本操作，以及昨天的栈和队列相互实现，就应该清晰很多。
:blue_heart:1. 入数据。同时也要注意，取队尾数据是tail的上一个节点中val
:blue_heart:2. 出数据，front向后挪一个位置即可。
:blue_heart:3. 判空判满的条件，画图（上图）即可知
注意：
:yellow_heart:1.create时，弄清你要申请的空间，头脑中有类似下面的图。昨天做了栈和队列的相互实现，这个就是一样的。
:yellow_heart:2.遇到这样的报错，其实是因为前面的函数调用了后面的函数接口，那在前面声明一下就好了。
2.2 题解
typedef struct CircularListNode{
int val;
struct CircularListNode* next;
} CircularListNode;
typedef struct {
CircularListNode* front;
CircularListNode* tail;
//int k; //不写这个也完全可以
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
q->front = q->tail = (CircularListNode*)malloc(sizeof(CircularListNode));
//q->k = k;
CircularListNode* cur = q->front;
while(k--)
{
CircularListNode* newnode = (CircularListNode*)malloc(sizeof(CircularListNode));
cur->next = newnode;
cur = newnode;
}
cur->next = q->front;//尾链上头
return q;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->tail->val = value;
obj->tail = obj->tail->next;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->front = obj->front->next;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->front->val;
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
//找tail的上一个节点
CircularListNode* prev = obj->front;
while(prev->next != obj->tail)
{
prev = prev->next;
}
return prev->val;
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->tail == obj->front;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
return obj->tail->next == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
CircularListNode* cur = obj->front;
while(cur->next != obj->front)
{
CircularListNode* next = cur->next;
free(cur);
cur = next;
}
free(cur);
free(obj);
}
/**
* 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);
*/3. 用数组实现循环队列
3.1 思路
这个难点在于控制下标，但其实只需要把握好两个地方，画两个图就出来了 ——
:yellow_heart:1. 入队出队自己画图。
:yellow_heart:2. 保证front和tail下标实时有效。每次++，下一次都可能越界，就 %= k+1处理一下。下图解释为什么是k+1
:yellow_heart:3. 取队尾元素，是取tail前一个元素。注意tail为0时，直接跳后面取
:yellow_heart:4. 如何判满？下面两幅图都是满的情况，找关系吧！
(tail+1)%(k+1) == front3.2 题解
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
q->a = (int*)malloc((k+1)*sizeof(int));
q->front = q->tail = 0;
q->k = k;
return q;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
obj->tail %= obj->k+1;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->front++;
obj->front %= obj->k+1;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
if(obj->tail == 0)
return obj->a[obj->k];
else
return obj->a[obj->tail-1];
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1) == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->front = obj->tail = 0;
free(obj);
}
/**
* 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);
*/