题目一 设计循环队列
题目分析
这里直接看图
我们发现这里要求我们设计一个循环队列
这要怎么设计呢？
还是一样 我们先画图
我们首先假设只能储存四个数字
同学们看这张图能观察到什么呢？
是不是可以得到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); }
源码
1. ttypedef 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); }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
