本文主要是介绍刷爆leetcode第八期，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目一 设计循环队列
题目分析
这里直接看图
我们发现这里要求我们设计一个循环队列
这要怎么设计呢？
还是一样 我们先画图
我们首先假设只能储存四个数字
同学们看这张图能观察到什么呢？
是不是可以得到front 和 rear相等的时候整个队列为空
这里当插入一个数据之后 rear就往后走了一步
我们插入四个数据试试
咦 这个时候front和rear又相等了
这里好像队列满的条件和队列空的条件一样了
那么这个时候有没有什么好办法可以区分两种相等呢？
好像没有特别好的方法
那么我们加一个空数据
这样子可不可以呢？
这个时候呢？
我们好像可以使用公式
（tail+1）% （k+1） == head
来判断是否为满
这不就形成循环了嘛
那么我们接下来开始看题目、
第一步 设计结构体
typedef struct {int*a;int front;int rear;int k;
} MyCircularQueue;我们需要用到的数据有
数组 头指针 尾指针 数字K
所以说我们定义这几个变量出来
第二步 初始化结构体
1 首先我们先动态开辟结构体的内存
2 因为需要k+1个数据的存贮空间 所以我们要开辟k+1个内存的大小
3 开始的头尾指针都设置为0
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*(k+1));obj->front = obj->rear = 0;obj->k = k;return obj;
}第三步 我们先判断队列是否空或满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;判断满的情况我们就可以用公式啦
我们说有以上代码可以来判断
第四步 重新回到插入数据
这里主要分两种情况讨论
像这种情况 直接插入 rear+1就可以
但是如果是这样子呢？
像这个时候tail就要走到最前面了？
那么我们怎么来表示呢？
我们说
可以使用 tail=（tail+1）%（k+1）表示 想想看 是不是这样子
当tail等于4向前是不是就变成0了
所以我们开始敲代码
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++] = value;obj->rear%=(obj->k+1);return true;
}这样子就完成了
第五步 删除数据
这个的判断和前面一样
参考前面的代码就能够写出来了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front%=(obj->k+1);return true;
}第六步 返回头数据
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}这个很简单 返回头部的数据就可以
数组越界问题跟前面的处理结果相似
第七步 返回尾数据
这里要考虑一个特殊情况
就是当尾指针在数组的0位置的时候
这个时候我们单拎出来分类讨论就可以
如果是0的话 我们返回最后面的数据就可以
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;if(obj->rear==0){return obj->a[obj->k];}else{return obj->a[obj->rear-1];}
}第八步 释放
这个也很简单，先释放结构里面的再释放结构体
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}源码
typedef struct {int*a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*(k+1));obj->front = obj->rear = 0;obj->k = k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++] = value;obj->rear%=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front%=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;if(obj->rear==0){return obj->a[obj->k];}else{return obj->a[obj->rear-1];}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
这篇关于刷爆leetcode第八期的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
