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

说在前面

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

  • 数据结构
  • 【栈和队列】纯C实现栈和队列以及其基本操作-宝藏级别数据结构教程【保姆级别详细教学】

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

题目:622.design-circular-queue


导航小助手

  • 说在前面
  • 博主给大家的话
  • 题目描述和要实现的接口
  • 题目和思路的分析详解-链式或数组?
  • 实现完整代码
  • 离开之前


博主给大家的话

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

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

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

题目描述和要实现的接口

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


要实现的接口:
【队列】如何设计循环队列?-力扣622【超详细的解题思路和注释】_第3张图片

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

图片来自比特就业课
【队列】如何设计循环队列?-力扣622【超详细的解题思路和注释】_第4张图片

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

  • 这种思路是完全可以做出这道题的,但是我们考虑一下,去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);
}

离开之前

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

你可能感兴趣的