长沙网站设计咨询电话,南通公司快速建站,wordpress上传svg,做淘宝网站报告呀哈喽#xff0c;我是结衣 今天给大家带来的内容如标题所述#xff0c;我们来设计环形队列#xff0c;虽然队列没有讲#xff0c;但是我就是想讲啊。那么环形队列现在开始。
队列的属性
在设计环形队列前#xff0c;我们先要了解队列的特点#xff08;先进先出#x…呀哈喽我是结衣 今天给大家带来的内容如标题所述我们来设计环形队列虽然队列没有讲但是我就是想讲啊。那么环形队列现在开始。
队列的属性
在设计环形队列前我们先要了解队列的特点先进先出就想现实中我们排队一样先到的人先得。所以现实中银行的取票机是可以用队列实现的。
循环队列
本次讲解是基于leetcode的以题来讲解的贴张图给大家介绍吧 看完题目不知道大家有没有思路呢没有的话就听我详细的解释吧。
顺序表or链表
看完题目你最先想到的实现方法是顺序表还是链表呢倒不是说这两种方法只能选择一个而是实现难易程度问题你觉得用顺序表难还是用链表难呢这里我选择用顺序表来讲解我觉得顺序表简单一些呢。
顺序表实现循环队列
在实现之前我们来看看题目要我们实现的功能吧
typedef struct {} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {}bool myCircularQueueDeQueue(MyCircularQueue* obj) {}int myCircularQueueFront(MyCircularQueue* obj) {}int myCircularQueueRear(MyCircularQueue* obj) {}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {}bool myCircularQueueIsFull(MyCircularQueue* obj) {}void myCircularQueueFree(MyCircularQueue* obj) {} 了解完要求下面我们就要分析了。
怎样实现循环
首先我们要定义一个头和尾。front和back他们就是下标哈。 有了头和尾。我们要把他们的初始值给多少呢都给‘0’还是给‘-1’呢这里我的做法是把头和尾都给‘0’你可能会说那如果插入了一个数back怎么办。哼哼我们把back我们让back指向的最后一个数的下一个而非最后一个数那么新的问题又来了当出现这种情况怎么办。 back不就出去了吗是的我们要解决这个问题就要多定义一个空间题目让我们定义k个空间我们就要定义k1个空间。但是有一个空间是不存储数据的。 在k1个空间中始终有一个空间是不存储数据的只有这样才能满足题目要求的k个空间。 这就是循环的示意图当前面有空间又要插入数据时在back的位置上插入数据后再将back 0。
结构体的创建
typedef struct {int* data;int front;int back;int k;
} MyCircularQueue;相信看完上面的简介这个结构体的创建是没有问题的吧。
函数的实现
这里的函数的实现并不是按照题目顺序来进行的。因为这里的函数也可以相互的调用为后续节省时间。
初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* tmp (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp-data (int*)malloc(sizeof(int) * (k 1));tmp-front 0;tmp-back 0;tmp-k k;return tmp;
}我们先要malloc一个结构体的空间然后再malloc tmp-data这个数组的大小因为我们有一个空位置所以就开了k1个的空间。还有头和尾的赋值尾‘0’在上面的实现循环里有讲解。
队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj-back obj-front){return true;}return false;
}这个代码就很直观了back front就直接判空了。因为我们这里的back是不会有数据的出现这种情况这样最初的时候在那种情况就是队列为空的情况。
队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if ((obj-back 1) % (obj-k 1) obj-front){return true;}return false;
}我们都知道当back的下一个为front的时候就是满的时候所以写成back1 front是不是就可以了呢不是不行多加个判断就可以了但是为我们要介绍的方法取余的方法在这种循环中就特别的好用利用的就是当被除数比除数小的时候余数为被除数。
数据插入
写完判空判满的函数我们下面就会轻松一些 要插入数据我们首先就是要判断队列有没有满如果满了就不能插入并且返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj-data[obj-back] value;if (obj-back obj-k)obj-back 0;elseobj-back;return true;
}除了判满我们还要小心当back在最后的情况下在最后的话如果我们还是back的话back就出界了后果可是很严重的后面返回为数据的时候就可能会访问野指针。导致程序崩溃。所以我们就要加判断呢。
数据删除
删除数据的时候我们要知道队列不能为空为空就不能删除返回false。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}if (obj-front obj-k)obj-front 0;elseobj-front;return true;
}当然后面判断和前面插入的时候相似front在最后的时候就不能了要让他等于0。
返回头
不能为空
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-data[obj-front];
}返回尾
不能为空的同时还要注意back为0的时候如果你还 减减 不久变成负数了吗这样肯定是不行的所以我们要再加一个判断咯。
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}if (obj-back 0)return obj-data[obj-k];elsereturn obj-data[obj-back - 1];
}
销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj);obj NULL;
}销毁就是十分的简单
循环队列代码
typedef struct {int* data;int front;int back;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* tmp (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp-data (int*)malloc(sizeof(int) * (k 1));tmp-front 0;tmp-back 0;tmp-k k;return tmp;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj-back obj-front){return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if ((obj-back 1) % (obj-k 1) obj-front){return true;}return false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj-data[obj-back] value;if (obj-back obj-k)obj-back 0;elseobj-back;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}if (obj-front obj-k)obj-front 0;elseobj-front;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-data[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}if (obj-back 0)return obj-data[obj-k];elsereturn obj-data[obj-back - 1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj);obj NULL;
}完
