题目编号0020
题目分析
这里直接看图
我们发现这里要求我们设计一个循环队列
这要怎么设计呢？
还是一样 我们先画图
我们首先假设只能储存四个数字
同学们看这张图能观察到什么呢？
是不是可以得到head 和 tail相等的时候整个队列为空
这里当插入一个数据之后 tail就往后走了一步
我们插入四个数据试试
咦 这个时候head和tail又相等了
这里好像队列满的条件和队列空的条件一样了
那么这个时候有没有什么好办法可以区分两种相等呢？
好像没有特别好的方法
那么我们加一个空数据
这样子可不可以呢？
这个时候呢？
我们好像可以使用公式
（tail+1）% （k+1） == head
来判断是否为满
那么我们接下来开始看题目
第一步 设计结构体
typedef struct { int*a; int tail; int front; int k; } MyCircularQueue;
我们需要用到的数据有
数组 头指针 尾指针 数字K
所以说我们定义这几个变量出来
第二步 初始化结构体
1 首先我们先动态开辟结构体的内存
2 因为需要k+1个数据的存贮空间 所以我们要开辟k+1个内存的大小
3 开始的头尾指针都设置为0
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue*)); cq->a = (int *)malloc(sizeof(int)*(k+1)); cq->tail = 0; cq->front = 0 cq->k = k; return cq; }
第三步 跳到第四步
第四步 判断队列是否空或满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //断言 assert(obj); //如果说 头等于尾就为空 //否则就为假 return head == tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { //assert assert(obj); //judge (tail +1) %(k+1)== head? return (tail+1)%(k+1) == head ; }
我们说有以上代码可以来判断
第五步 插入数据
这里主要分两种情况讨论
像这种情况 直接插入 tail+1就可以
但是如果是这样子呢？
像这个时候tail就要走到最前面了？
那么我们怎么来表示呢？
我们说
可以使用 tail=（tail+1）%（k+1）表示 想想看 是不是这样子
当tail等于4向前是不是就变成0了
所以我们开始敲代码
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { // 断言 assert(obj); //这个时候我们首先要判断整个队列是否为满 //所以我们先要判断队列是否为满 //来都来了 顺便判断下是否为空 if ((obj->tail+1)%(obj->k+1) == obj->front) { return false; } else { obj->arr[obj->tail] = value; //++obj->tail; obj->tail++; //obj->tail %= (obj->k+1); //++obj->tail; obj->tail %= (obj->k+1); return true; } }
这样子就完成了
第六步 删除数据
这个的判断和前面一样
参考前面的代码就能够写出来了
int myCircularQueueFront(MyCircularQueue* obj) { if (obj->front == obj->tail) { return -1; } else { return obj->arr[obj->front]; } }
第七步 返回头数据
int myCircularQueueFront(MyCircularQueue* obj) { if (obj->front == obj->tail) { return -1; } else { return obj->arr[obj->front]; } }
这个很简单 返回头部的数据就可以
数组越界问题跟前面的处理结果相似
第八步 返回尾数据
这里要考虑一个特殊情况
就是当尾指针在数组的0位置的时候
这个时候我们单拎出来分类讨论就可以
如果是0的话 我们返回最后面的数据就可以
int myCircularQueueRear(MyCircularQueue* obj) { if (obj->front == obj->tail) { return -1; } else { if (obj->tail == 0) { return obj->arr[obj->k]; } else { return obj->arr[obj->tail-1]; } } }
总结
问题一
今天写代码遇到了两个问题
一个是这个 我们开辟空间的时候 sizeof里面的内容填错了
上一次已经出现了一个没有填sizeof的问题 下次一定要注意
这里解决下就可以了
问题二
这里还有一个报错就是我们没有在前面声明就开始使用函数了
leetcode不会提前声明函数的
所以我们刷题的时候要自己来声明
源码
// 使用数组模式来设计 #include<stdbool.h> typedef struct { int* arr; int tail; int front; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->arr = (int *)malloc(sizeof(int)*(k+1)); cq->tail = 0; cq->front = 0; cq->k = k; return cq; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { // 断言 assert(obj); //这个时候我们首先要判断整个队列是否为满 //所以我们先要判断队列是否为满 //来都来了 顺便判断下是否为空 if ((obj->tail+1)%(obj->k+1) == obj->front) { return false; } else { obj->arr[obj->tail] = value; //++obj->tail; obj->tail++; //obj->tail %= (obj->k+1); //++obj->tail; obj->tail %= (obj->k+1); return true; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { assert(obj); // 这里相同 如果队列为空就返回false 如果不为空再讨论 if(obj->front==obj->tail) { return false; } else { obj->front++; obj->front %= (obj->k+1); return true; } } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->front == obj->tail) { return -1; } else { return obj->arr[obj->front]; } } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->front == obj->tail) { return -1; } else { if (obj->tail == 0) { return obj->arr[obj->k]; } else { return obj->arr[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->arr); obj->arr=NULL; 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); */
