【队列】如何设计循环队列?-力扣622【超详细的解题思路和注释】

说在前面

其实数据结构-队列是一种特殊的线性表,设计循环队列其实也是队列方面的一道特别经典的题目,如果用纯C实现,它极好地考察了我们C语言的功底。
如果对数据结构-队列还没有很好了解的同志们,可以看看博主的数据结构专栏和有关栈和队列的总结博客哦!传送门在这里给到大家了。

此篇,博主带着大家用纯C实现这个循环队列,顺便巩固扎实我们的C语言基础

题目:622.design-circular-queue



博主给大家的话

在这里插入图片描述

那么这里博主先安利一下一些干货满满的专栏啦!

数据结构专栏:数据结构 这里包含了博主很多的数据结构学习上的总结,每一篇都是超级用心编写的,有兴趣的伙伴们都支持一下吧!
算法专栏:算法 这里可以说是博主的刷题历程,里面总结了一些经典的力扣上的题目,和算法实现的总结,对考试和竞赛都是很有帮助的!
力扣刷题专栏:Leetcode 想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴,这里面都是博主的刷题记录,希望对你们有帮助!
C的深度解剖专栏:C语言的深度解剖 想要深度学习C语言里面所蕴含的各种智慧,各种功能的底层实现的初学者们,相信这个专栏对你们会有帮助的!

题目描述和要实现的接口

在这里插入图片描述


要实现的接口:
在这里插入图片描述

题目和思路的分析详解-链式或数组?

图片来自比特就业课
在这里插入图片描述

分析:
其实看到循环,我们其实很容易可以想到环形链表,将单链表首尾相连。因为是静态的,我们如果队列是k个储存空间,现在我们开k个节点,依次链接起来。我们定义headtail指针,一开始head==tail,如果插入一个数据我们的tail=tail->next;如果删除数据,我们head=head->next;即可,这个我们是必须要想到的。
但是在这种情况下,我们发现一个问题,当队列为空的时候,head ==tail,当队列满的时候,也是head ==tail,这样就出问题了。因此,开k个节点是不够的!我们要开k+1个! 此时,当tail的下一个是next的时候,表示队列已满。
当然,除了这种解决方案,我们多加一个size表示队列的大小,当size==k的时候满也是可以的。
在这里插入图片描述

  • 这种思路是完全可以做出这道题的,但是我们考虑一下,去tail上的数据的时候,我们还需要一个prev记录前一个节点,因为我们插入一个数据是在tail位置上插入的,插入之后tail=tail->next;

但是如果我们使用数组来实现这个环形队列,我们就没有这个问题,因为数组可以做到数据的随机访问。

思路是一样的,只是我们的headtail不再是指针,是下标了。

  • 用数组实现要注意的点:注意边界的控制,如果指针出去了,越界了,绕一下绕回0的位置,或者用取模的方式都可以解决!

关于实现过程中边界控制等一些细节,博主将在代码的注释中给大家解释清晰!

实现完整代码

typedef struct {
    int* a;//数组
    int k;//队列的大小
    int head;//头下标
    int tail;//尾下标
} MyCircularQueue;

//isFull()和isEmpty()这两个函数放到前面来,因为后面要用,或者写一个前置声明也是可以的。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //注意tail在数组最后,head在最前的特殊情况
    int next = obj->tail + 1;//如果next超范围了,回去
    if (next == obj->k + 1) {
        next = 0;
    }
    return next == obj->head;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;//如果head==tail一定就是空的
}

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先搞一个节点出来
    //这里的malloc是将环形队列创建出来
    obj->a = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间
    //这里的malloc是将环形队列里面的数组创建出来
    obj->head = obj->tail = 0;//这里head tail是下标
    obj->k = k;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))return false;
    //满了,不能插入
    obj->a[obj->tail] = value;//在tail的位置放val
    obj->tail++;
    //但是要控制边界
    if (obj->tail == obj->k + 1) {
        obj->tail = 0;//把下标绕回来
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//空了,不能删除
    if (myCircularQueueIsEmpty(obj))return false;
    ++obj->head;
    if (obj->head == obj->k + 1) {
        obj->head = 0;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
//按照题目要求,如果空了,返回-1
    if (myCircularQueueIsEmpty(obj))return -1;
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
//空了,返回-1
    if (myCircularQueueIsEmpty(obj))return -1;
    int prev = obj->tail - 1;
    if (obj->tail == 0) {
        prev = obj->k;
    }
    return obj->a[prev];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    //先free数组
    //再free循环队列
    //否则会造成内存泄漏!
    free(obj->a);
    free(obj);
}

离开之前

看到这里,如果伙伴们觉得有帮助的话,不要忘记一键三连哦!


原文连接:https://blog.csdn.net/Yu_Cblog/article/details/124856100

相关推荐

领域驱动设计:事件溯源架构简介

Figma自编教程第三篇(也是做产品实习生的第三天)

Flutter 绘制探索 | 箭头端点的设计

为什么设计的软件不好用?那是因为不熟悉软件开发模型!一文熟悉软件开发模型

Netty 案例之 IM 方案设计

【设计模式】责任链模式(Chain of Responsibility Pattern)

VGA设计(原理说明。Verilog代码实现,仿真结果)

提升UI产品体验的14个细节!你都知道吗?

【毕业设计】深度学习 opencv python 实现中国交通标志识别

TiFlash 源码阅读(五) DeltaTree 存储引擎设计及实现分析 - Part 2

还记得当年的超级玛丽么?来吧,动手设计一款小霸王游戏机

Figma自编教程第二篇(也是做产品实习生的第二天)

【毕业设计】python+大数据构建疫情可视化分析系统

Go的错误处理设计

Figma自编教程第一篇(也是做产品实习生的第一天)

【设计模式】模板模式,学会它咱也写出优雅健壮的代码!

从全局角度,如何设计一个秒杀系统?

【分享】从Mybatis源码中,学习到的10种设计模式

【干货】MySQL底层架构设计,你了解多少?

【C++】从设计原理来看string类