前言
舒文未来目标: 进大厂啊进大厂~🤪.让我家人放松一些,努力让生活更棒,好耶!
舒文现状:大一菜鸡,从食品转码,目前已经结识了很多学习的朋友.(挺棒的👍)
博客目的:写博客是为了记录自己的学习路径.也是为了让面试官眼前一亮,然后就是装逼.
小小推荐: 我在CSDN和朋友创建管理了一个社区大家如果感兴趣的话可以来看看👉非科班转码社区.👈
现阶段目标: 好好学习基础知识多多了解计算机行业情况.保持良好的身体素质,多多交朋友,多多犯错多多从错误中学习😍.
之前的博客是整理了两道关于队列和栈的题目:👉用队列实现栈&用栈实现队列👈.
本篇文章就主讲一道题(多少有亿点水🤪).不过下次博客就进入二叉树了,谁会不喜欢二叉树呢?
设计循环队列
👉连接👈.
题目意思: 要求实现一个循环队列,要有队列的格式(先进先出).循环队列内的空间固定不会增加.被删除的部分应该可以被再次应用.
所以格式应该如下图:
现在就有一个问题我们是使用数组来实现还是通过队列来实现呢?
我认为各有各的优缺点
队列:在从尾部回到头部的部分比较简单.但是在记录head和tail的时候比较麻烦(可以用全局变量但是这样我们的结构体就很功能缺失=-=.)好吧舒文用了3h没有写出来这个队列版的但是我知道错误在哪里,所以准备先记录一下错误代码.我愿称之为痛苦的一天🤦♂️🤦♂️🤦♂️🤦♂️.写出来了!!!有一说一我现在对这道题的理解挺深的了,马上写出来给大家看看
顺序表: 我写了而且比较简单,思路较简单除了在tail从为到头时有一点点的麻烦之外没啥其他的困难了😍.
代码&&讲解
单链表实现🤦♂️&粗讲解
这个单链表实现我甚至用了三个全局变量实在是拉的很的一个代码🤦♂️.
typedef struct MyCircularQueue { int date; struct MyCircularQueue* next; } MyCircularQueue; static MyCircularQueue* g_head; static MyCircularQueue* g_tail; static MyCircularQueue* g_tailprev; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { int tmpk = k; MyCircularQueue* head = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); MyCircularQueue* prev = head; while(tmpk) { MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); newnode->next = head; //newnode->date = 0; prev->next = newnode; prev = newnode; tmpk--; } g_head = head; g_tail = head; g_tailprev = NULL; return head; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } g_tail->date = value; g_tailprev = g_tail; g_tail = g_tail->next; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } g_head = g_head->next; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return g_head->date; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } if(g_tailprev!=NULL) return g_tailprev->date; else return -1; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //if(g_tailprev!=NULL) // return g_head == g_tailprev; //else // return g_head == g_tail; return g_tail == g_head; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return g_tail->next == g_head; } void myCircularQueueFree(MyCircularQueue* obj) { MyCircularQueue* cur = g_head->next; MyCircularQueue* next = cur->next; while(cur!=g_head) { free(cur); cur = next; next = next->next; } free(g_head); g_head = NULL; g_tail = NULL; } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
这次博客分为两次完成所以我现在这里讲解一下
因为是单链表的原因我们不能在每一个节点的部分都放上head tail tailprev来记录, 所以我的脑子就只想到了全局变量🤦♂️🤦♂️.
在创建时我们要多创建一个节点不然是没办法判空和判满的,原因是我们的tail指针是指向我们节点内容的下一位,当我们想判空时如果我们没有多给一个空间的话我们的tail就可能和head相同这样我们就无法判断是空还是满了🤦♂️.
在顺序表时也是这个原因🤪.
我们如果想用链表的话,我个人认为是极为麻烦的,因为他实在是很难保存住我们的head tail的位置而且我们尾部之前的内容也比较难得到,如果用双向循环链表倒是会可以得到尾部前的内容不过没有顺序表香.
我们的判空时靠尾指针和头指针的相等,判满是通过tail->next==head;
细致亿些的讲解
typedef struct MyCircularQueue { int date; struct MyCircularQueue* next; } MyCircularQueue; static MyCircularQueue* g_head; static MyCircularQueue* g_tail; static MyCircularQueue* g_tailprev;
看见这个结构体我相信大家都知道了,我用的是单链表,实话实说我感觉双向循环链表好像也就是解决了尾部的前一个元素的内容得到=-=.
MyCircularQueue* myCircularQueueCreate(int k) { int tmpk = k; MyCircularQueue* head = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); MyCircularQueue* prev = head; while(tmpk) { MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); newnode->next = head; //newnode->date = 0; prev->next = newnode; prev = newnode; tmpk--; } g_head = head; g_tail = head; g_tailprev = NULL; return head; }
这里我们多创建了一个空间节点,因为我们在使用时我们的tail是指向下一个空的节点的.
当我们判满的时候如果我们不多给一个空间节点的话g_tail就会跑到和head一起的位置也就是说满的时候g_tail = g_head
你可能感觉没啥但是我们在判空的时候就是通过g_tail和g_head的相同来得到的.
这是你可能会想到我们还有g_tailprev但是g_tailprev的存在其实就只能为我们拿到tail的前一个值的功能而已,如果通过tailprev来看到底是满还是空也是不行的,我试了至少我们想出来🤦♂️.
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //if(g_tailprev!=NULL) // return g_head == g_tailprev; //else // return g_head == g_tail; return g_tail == g_head; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return g_tail->next == g_head; }
而我们在多创建了一个空间后我们的判断就会轻松很多因为我们可以之间通过tail和head进行判断了👍.
如果不信邪的同学可以试试,至少菜鸡的我没搞定.🤦♂️🤦♂️.
(我会尽量在这两天把链表这个优化一下来尽量得到更完美的他.)
其他的其实都没啥了😎.
顺序表版
正确代码&粗讲解
typedef int QDate; typedef struct { QDate* date; int k; int head; int tail; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->date = (QDate*)malloc(sizeof(QDate)*(k+1)); obj->k = k; obj->head = obj->tail = 0; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { assert(obj); if(myCircularQueueIsFull(obj))//用自身函数表达即可 { return false; } obj->date[obj->tail] = value; obj->tail++; obj->tail =obj->tail % (obj->k+1);//防止tail大于k,使用k+1是因为要符合两种情况一种是tail=k时先++再%=k+1刚好为0要么就是正 //常情况比如从1->2的时%=k+1再++也可 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->head++; obj->head = obj->head % (obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->date[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } if(obj->tail == 0) { return obj->date[obj->k]; } else { return obj->date[obj->tail-1]; } } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { if(obj->tail == obj->k&&obj->head == 0) { return true; } else { return obj->tail+1==obj->head; } } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->date); obj->tail = obj->head = obj->k = 0; free(obj); } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
先粗讲解一下,
在结构体哪里可以看见我们用的是date来储存我们的数据,date来作为顺序表的头部就可以了,我们的head和tail都可以很棒的得到储存.
在队列创建可以看到我们也是多创建了一个空间,原因和上面一样,我们想要方便我们判空和判满就要多一块空间来让我们tail位置不在满的时候和head相同就需要这样做.
想队列里增加内容时,我们的tail不能比我们的空间内容大.所以我们用%=操作符来进行操作.值得注意的是我用的是%=(k+1)是为了防止tail大于k,使用k+1是因为要符合两种情况一种是tail=k时先++再%=k+1刚好为0要么就是正常情况比如从1->2的时%=k+1再++也可.
删除数据就简单了很多我们只需head++即可👍.
判满和判空时要注意判满是要分两种情况的当head还在0的位置时我们需要额外的判断才可🤪.
结尾
这道题对于栈和队列的初学者应该挺有难度的,但是没难度上哪来成长,我建议大家都来试试😎.
