刷爆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);
}

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

相关推荐

  1. WebGIS面试题(

    2024-06-06 18:12:01       21 阅读
  2. 力扣73天--动态规划

    2024-06-06 18:12:01       58 阅读
  3. LeetCode

    2024-06-06 18:12:01       66 阅读
  4. 力扣90天之hot100五连36-40

    2024-06-06 18:12:01       44 阅读
  5. 力扣91天之hot100五连41-45

    2024-06-06 18:12:01       46 阅读
  6. 力扣89天之hot100五连31-35

    2024-06-06 18:12:01       42 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-06 18:12:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-06 18:12:01       101 阅读
  3. 在Django里面运行非项目文件

    2024-06-06 18:12:01       82 阅读
  4. Python语言-面向对象

    2024-06-06 18:12:01       91 阅读

热门阅读

  1. pyqt5 tableView实现excel拖曳填充

    2024-06-06 18:12:01       32 阅读
  2. GPT-4o版本间的对比分析和使用心得

    2024-06-06 18:12:01       30 阅读
  3. php设计模式之策略模式详解

    2024-06-06 18:12:01       35 阅读
  4. XML语法规则介绍及总结

    2024-06-06 18:12:01       36 阅读
  5. EasyExcel之动态表头导出不生效

    2024-06-06 18:12:01       27 阅读
  6. 什么叫防御式编程

    2024-06-06 18:12:01       32 阅读
  7. C++:day2

    C++:day2

    2024-06-06 18:12:01      30 阅读
  8. 糖尿病相关的数据集

    2024-06-06 18:12:01       33 阅读
  9. ActiViz中的纹理映射

    2024-06-06 18:12:01       29 阅读