网站备案是一年一次吗,网站建设需要经历什么步骤,在线简历,建一个免费看电影的网站犯法不#x1f9d1;#x1f393;个人主页#xff1a;简 料 #x1f3c6;所属专栏#xff1a;C #x1f3c6;个人社区#xff1a;越努力越幸运社区 #x1f3c6;简 介#xff1a;简料简料#xff0c;简单有料~在校大学生一枚#xff0c;专注C/C/GO的干货分… 个人主页简 料 所属专栏C 个人社区越努力越幸运社区 简 介简料简料简单有料~在校大学生一枚专注C/C/GO的干货分享立志成为您的好帮手 ~ C/C学习路线 (点击解锁)❤️C语言阶段(已结束) ❤️数据结构与算法(ing)❤️C(ing)❤️Linux系统与网络(队列中…) 文章目录 前言如何设计循环队列设计循环队列整体的代码写在最后 前言 前面我们 用队列实现了一个栈 用栈实现了一个队列 相信大家随随便便轻松拿捏而本章将带大家上点难度我们来 设计一个循环队列。 对于循环队列重点就在一个 “ 循环 ”意思也就是该队列首尾相连形成一个环但其本质还是不变队列 先进先出 的性质依旧存在只不过环的大小有限定限定放多少数据就只能放多少数据。 那么我们如何来设计这样的一个环使它既能够像队列一样又可以体现循环的性质下面就带大家探讨一波。 如何设计循环队列 那么该如何设计一个循环队列呢首先第一步当然就是选取一个存储结构来存放数据是选顺序表的数组呢还是链表呢 我们先来看看对循环队列的介绍循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
由以上所说既然是队尾被连接在队首之后形成一个循环并且之前我们讲解的队列是选用的链式储存结构那我们第一个想到的就是选用链式的储存结构来存储数据因为只要链表的尾节点的next指向头节点就形成了循环这是很容易想到的。那我们就先对链式这一储存结构进行分析看到底合不合适。
抽象图 既然是队列那就需要两个指针一个命名为front指向头一个命名为rear指向尾。由于是循环队列刚开始就将空间开好固定长度那么此时front和rear都指向同一个节点如下 那么此时入队列的操作过程如下 可以看到rear指向有效数据节点的下一个位置。当队列入满的时候rear指针此时又与front指针相等了我们再来看看出队列的过程出队列数据可以不用抹去访问不到 由上面的两个操作我们不难发现当队列为空的时候front指针与rear指针相等当队列满的时候front指针与rear指针也相等这不免就会出现冲突问题判空和判满将如何判断呢 这里有两种方案 第一个是多创建一个变量来统计数据的个数当判空和判满的时候根据这个变量就可以实现第二个是多开一个空间注意不是哨兵位节点也就是规定长度为多少开空间的时候开长度加一个空间如下图 可以看到方案二当循环队列为空的时候front rear当循环队列为满的时候如下图 由此图不难得出当循环队列为满时有rear-next front所以方案二对于判空和判满的区分也是挺不错的。不过大家有没有观察到对于链式储存结构无论是方案一还是方案二都不好找队尾数据因为它处在rear指针的前一个节点实在是要找的话就需要遍历一遍循环队列或者在一开始就另外再定义一个prev指针指向rear指针的前一个节点这些都是比较麻烦的。那么根据此问题由于数组存储形式支持随机访问所以下面我们再来看看数组的存储形式怎么样。 对于数组的存储形式整体上来说与链式存储形式差不太多。由于循环队列的长度是固定的因此数组的存储形式抛弃了扩容这一弱点。
数组存储形式图
有了链式存储的分析判断不难得出上图的数组存储形式也会出现判空和判满实现的冲突问题。因此这里也需要解决方案而数组存储形式的解决方案与链式存储形式的解决方案是相同的无非就是多定义一个变量来统计数据的个数或者多开一个空间。多定义一个变量来统计数据的个数固然可以实现但这里我们选取多开一个空间的形式来进行分析。
如果是多开一个空间那么当循环队列满时有以下情况 2.
(注意front与rear两个指针分别是对应数据的下标 | 设规定的长度为k) 如果是2情况判满可以判断 rear 1 front 但还有1情况rear 1不会等于front并且会超出数组的下标范围因此这里可以对rear 1取模也就是判断 (rear 1) % (k 1) front ? 即可。有了这种判断方式无论rear是否指向数组的最后一个位置他都可以判断因为当rear不是指向数组的尾时它加一模上一个(k 1)完全不会受到影响就相当于是判断 rear 1 front 一样。而rear指向数组的尾时这样操作最终就是判断 front 0 一样。 那数组的判满解决了判空如何呢其实判空很简单只需要判断rear是否等于front即可。
由于是数组存储形式因此支持下标的随机访问所以这里获取队头和队尾元素都非常的方便。
如果是获取队头元素直接返回front指向的数据即可如果是获取队尾元素只需要返回rear的前一个位置的数据即可但是如果rear此时指向数组的开头又该怎么找队尾元素呢? 这里我们将 rear k 然后模上 k 1 即可。因为如果rear是指向数组开头rear加上k后刚好指向数组的最后一个位置也就是循环队列的队尾。如果rear不是指向数组开头 (rear k) % (k 1) 刚好是rear的前一个位置所以这样的取模的方式完美的实现了取队尾的功能。
综上来看链式储存结构与数组储存结构还是数组储存结构更胜一筹因为在取队尾元素这一块数组储存结构碾压链式储存结构所以这里我们选择数组储存结构来实现循环队列。 这里我们采用多开一个空间的方式来实现。 确定了以数组存储结构来存储数据后那么该如何实现数据的入队和出队呢
首先来看看数据入队列示意图 对于第一张图的入队列就是在当前rear位置插入然后rear加加即可。但是对于第二张图rear在最后位置的时候插入数据此时rear加加就超过数组的长度了因此我们每次在rear加加后需要执行一下 rear % (k 1) 这条语句这样做rear在数组的尾插入数据时会将rear转算成0也就是指向数组的开头位置如果rear不在数组的尾插入数据此时rear的位置不会受任何的影响。
然后再来看看数据出队列示意图 对于第一张图每次删除其实只需要front加加即可如果为空就不能删了。对于第二张图当front指向数组的最后一个位置时出队过后front加加会越过数组因此每次出队列完成都需要执行 front % (k 1) 这条语句情况其实与上面入队列时的rear一样。 入队列与出队列介绍过了后面就是一些队列基本的接口操作了。有取队头数据取队尾数据判空和判满还有循环队列的销毁。 接下来就带大家来实现喽 设计循环队列
这里我们直接以题目的方式来实现题目链接- 传送门 -。 题目描述设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 该题提供的需要我们实现的接口
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) {}接下来就是对循环队列的一系列功能接口的实现了
1.
首先当然是定义一个循环队列的结构体。
相关代码实现
// 循环队列的结构
typedef struct {// 底层存储结构为数组int* a;// 指向队头int front;// 指向队尾int rear;// 规定的循环队列的长度// 这里存放一下规定的循环队列的长度是为了后面取模更方便int k;
} MyCircularQueue;2. 然后便是对一个循环队列的创造。 这里开辟一段连续的空间可以存放规定的长度加一个数据但其实总有一个空间是用不上的。 然后将front与rear都指向循环队列的队头就是置为0。 最后将规定的长度存起来即可。
相关代码实现
// 循环队列的创造构造器规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {// 先开辟一个循环队列的空间MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// assert防止开辟空间失败assert(obj);// 多开一个空间也就是开辟k 1个数据空间obj-a (int*)malloc(sizeof(int) * (k 1));// 开始头指针和尾指针都指向0也就是队头obj-front obj-rear 0;// 存放规定的队列长度obj-k k;return obj;
}3.
这里是入队列的实现。入队列就是在当前的rear位置插入数据然后rear加加。根据前面的解析入队列之后都需要取模一次避免rear越过数组。当然也可以通过判断的方式来处理特殊情况当队列为满的时候就不能入队列了。
相关代码实现
// 入队列插入数据插入成功返回true不成功队列已满那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {// 如果此时循环队列已经满了说明入队列不能进行直接返回 falseif (myCircularQueueIsFull(obj)) return false;// 在rear位置上插入数据然后rear加加obj-a[obj-rear ] value;// 每次都模上个 k 1obj-rear % (obj-k 1);// 入队列成功返回truereturn true;
}4.
接下来是出队列操作。出队列就是front加加根据前面的讲解每次出队列后都要记得需模上(k 1)。当然也可以通过判断的方式来处理特殊情况当队列为空的时候就不能出队列了。
相关代码实现
// 出队列删除数据删除成功返回true不成功队列为空那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {// 当循环队列为空说明不能再出队列了表明出队列失败直接返回falseif (myCircularQueueIsEmpty(obj)) return false;// 出队列直接front加加obj-front ;// 每次都模上个 k 1obj-front % (obj-k 1);// 出队列成功返回truereturn true;
}5.
获取队头数据直接返回front此时指向的那个位置上的数据即可。如果循环队列为空的话就取不了了依题目要求直接返回-1。
相关代码实现
// 获取队头元素如果队列为空返回-1
int myCircularQueueFront(MyCircularQueue* obj) {// 如果循环队列为空说明没有数据直接返回-1if (myCircularQueueIsEmpty(obj)) return -1;return obj-a[obj-front];
}6.
获取队尾数据根据前面的分析采用取模的方式获取。当然也可以通过判断的方式如果循环队列为空的话就取不了了依题目要求直接返回-1。
相关代码实现
// 获取队尾元素如果队列为空返回-1
int myCircularQueueRear(MyCircularQueue* obj) {// 如果循环队列此时为空直接返回-1if (myCircularQueueIsEmpty(obj)) return -1;// 以取模的方式来获取return obj-a[(obj-rear obj-k) % (obj-k 1)];
}7.
对于判空就是判断front是否等于rear即可。
相关代码实现
// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}8.
对于判满根据前面的分析也是通过取模的方式来实现的。当然也可以通过判断的方式来处理特殊情况
相关代码实现
// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-front;
}9.
最后就是销毁循环链表malloc了几次就free释放几次。
相关代码实现
// 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {// 有内到外依次释放空间// 释放数组free(obj-a);// 释放循环队列free(obj);
}整体的代码
// 循环队列的结构
typedef struct {// 底层存储结构为数组int* a;// 指向队头int front;// 指向队尾int rear;// 规定的循环队列的长度int k;
} MyCircularQueue;// 在这声明一下判空和判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);// 循环队列的创造构造器规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {// 先开辟一个循环队列的空间MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// assert防止开辟空间失败assert(obj);// 多开一个空间也就是开辟k 1个数据空间obj-a (int*)malloc(sizeof(int) * (k 1));// 开始头指针和尾指针都指向0也就是队头obj-front obj-rear 0;// 存放规定的队列长度obj-k k;return obj;
}// 入队列插入数据插入成功返回true不成功队列已满那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) return false;obj-a[obj-rear ] value;obj-rear % (obj-k 1);return true;
}// 出队列删除数据删除成功返回true不成功队列为空那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) return false;obj-front ;obj-front % (obj-k 1);return true;
}// 获取队头元素如果队列为空返回-1
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) return -1;return obj-a[obj-front];
}// 获取队尾元素如果队列为空返回-1
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) return -1;return obj-a[(obj-rear obj-k) % (obj-k 1)];
}// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-front;
}// 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}写在最后 设计一个循环队列还是有些复杂的呢不过看过本文章相信大家也可以轻松拿捏。 ❤️后续将会持续输出有关数据结构与算法的文章你们的支持就是我写作的最大动力 感谢阅读本小白的博客错误的地方请严厉指出噢~
