设计循环队列oj题（力口622）

目录

题目描述

题目解析分析

解决代码

题目描述

题目解析分析

这道题让我们写一个数据结构为循环队列。首先读题先进先出和我们队列差不多，其次队尾和队首形成一个循环，基本上到这题目意思差不多了知道了，需要我们首尾链接的队列，让我们实现这些功能。        

这里归根结底是判断哪个底层用数组方便还是循环链表方便。

 通过对比可知，在结构方面数组会略显一筹，但是数组在判断循环队列是否插满和是否为空时会冲突。为了弥补这一缺陷，我们有两种想法，一种是在循环队列中的结构体中插入有效值，另一种则是设置固定capacity+1个空间，多出来一个数组元素，然后通过对比(rear+1)%(capacity+1) 是否等于begin来判断。当然写到这里，肯定会想到我不扩容这个空间，(rear+1)%(capacity)观察是否等于begin是否可以，答案是不行的，因为我们在插入过程中是rear是先插入再++，这就会导致在下标第capacity-2位置上插入数据后到达下标capacity-1，而到了下标capacity-1时，(rear+1)%(capacity)时就会等于begin，导致内部数据从capacity到capacity-1就满了。

这里还需要主要取尾数据时方法，rear可以通过取模来在数组中循环。而我们需要取队尾数据时，采用的时rear-1来获取尾数据，当rear循环到0时这个方法就不好用了。这里我们可以用if来分类，当rear等于0时就可以让他加capacity来取队尾。 

解决代码

typedef struct {int begin;int rear;int* arr;int capacity;
} MyCircularQueue;//构造
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->rear = cq->begin = 0;cq->arr = (int*)malloc(sizeof(int)*(k+1));cq->capacity = k;return cq;
}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->begin;
}//判是否插满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1) % (obj->capacity+1) == obj->begin;
}//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear++] = value;obj->rear %= (obj->capacity+1);return true;
}//删头
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->begin++;obj->begin %= (obj->capacity+1);return true;
}//取头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->begin];
}//取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}int prev = obj->rear -1;//考虑rear=0if(obj->rear == 0){prev = obj->capacity;}return obj->arr[prev];
}//销毁
void myCircularQueueFree(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return;}free(obj->arr);obj->arr = NULL;obj->rear = obj->begin = obj->capacity = 0;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);
*/