题目一 设计循环队列

题目分析

这里直接看图

我们发现这里要求我们设计一个循环队列

这要怎么设计呢？

还是一样 我们先画图

我们首先假设只能储存四个数字

同学们看这张图能观察到什么呢？

是不是可以得到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);
}

以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言