商务网站建设与维护 ppt,软件开发app制作公司,网站怎样绑定域名,做网站需要理解什么目录
0.前言
1. 什么是环形队列 2. 如何使用数组结构 / 链表结构 对环形队列封装
3. 代码手撕环形队列各个接口
3.1 代表封装一个环形队列
3.2 环形队列的初始化
3.3 环形队列的插入
3.4环形队列的删除
3.5环形队列的判空
3.6环形队列的判满
3.7环形队列的队头
3.8环…目录
0.前言
1. 什么是环形队列 2. 如何使用数组结构 / 链表结构 对环形队列封装
3. 代码手撕环形队列各个接口
3.1 代表封装一个环形队列
3.2 环形队列的初始化
3.3 环形队列的插入
3.4环形队列的删除
3.5环形队列的判空
3.6环形队列的判满
3.7环形队列的队头
3.8环形队列的队尾
3.9环形队列的销毁 0.前言 4栈和队列OJ题集合/CircularQueue.h · onlookerzy123456qwq/data_structure_practice_primer - 码云 - 开源中国 (gitee.com)https://gitee.com/onlookerzy123456qwq/data_structure_practice_primer/blob/master/4%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97OJ%E9%A2%98%E9%9B%86%E5%90%88/CircularQueue.h本文所有代码资源已经上传至gitee如上可自取。 622. 设计循环队列 - 力扣LeetCodehttps://leetcode.cn/problems/design-circular-queue/这是本题的OJ链接是骡子是马可以拉出去练练。 1. 什么是环形队列 环形队列也称循环队列它是一种特殊的队列则其必首先符合队列的性质即先进先出后进后出First In First Out。 环形队列特殊在哪里呢 1.这个队列是定长的在初始化的时候这个队列的长度就已经定了即再也不能改变它所能容纳元素的最大数量了。 2.这个队列从抽象图看来形状上不是平常我们看到是直线型的而是一个环形的。 3.这个队列的队头和队尾首和尾在插入删除的过程当中是一直在不断变化的。相比普通队列它的首尾并不是在完全固定的位置。 环形队列的逻辑是一个head记录当前环形队列的队头位置一个tail记录当前环形队列的队尾位置当然我们这里tail实际代表意义是队尾元素的下一个位置如果删除的话就前移head代表删除如果要插入的话就后移tail代表增加一个环形队列的元素。这是环形队列的插入删除逻辑。 那环形队列毕竟是定长的队列当超过定长即把这个环形队列插满时那就会插入失败。所以我们需要设定一个head和tail的状态以之作为判断环形队列是否为满的标准。同时我们也要设定一个head和tail的状态以之作为判断环形队列是否为空的标准。 我们这样设定初始状态的环形队列即环形队列是空的话此时head和tail是重合的。 然后你插入一个元素队列是从队尾插入的所以我们就把当前tail所指向的位置插入新元素然后tail指向队尾的下一个位置因为如果不tail的话head和tail还是重合的这是时候我们是认为此环形队列是空。 如果再一直一直插入新元素直到插入为满的时候tail能最远到达的位置决定了最多能插入的元素而且铭记tail指向的是队尾元素的下一个位置head和tail重合代表环形队列为空根据上述规则的限定我们最终可以允许tail最远到head的前一个位置。 这样虽然会浪费掉一个小元素的空间但是这就一小点并不重要实在不行你想最多插入k个有效元素你再多开一个元素的空间k1不就中了嘛~ 当然啦删除元素队列就是删除队头的元素然后head指向的就是队头元素我们head即可完成删除。 2. 如何使用数组结构 / 链表结构 对环形队列封装 使用链表结构进行对一个环形队列的实现我们很简单就是用head和tail两个指针然后记录一个当前长度int num然后就依次进行对于该队列的插入删除这个和我们这篇博客所写的j基本一样3.用C语言实现队列 然后我们再需要做的就是当总数据num达到了定长即达最大可容纳数目之后那我们就禁止插入这个很简单的。 本博客我们使用数组结构来仿生实现该环形队列你可能会产生疑问链表姑且可以通过next成员指针找到下一个元素做到首尾相接那一个数组的首尾又不相连怎么会实现出一个环形队列呢其实我们是借助 % array_len 的方式实现的一手首尾互通可以循环的走。 举一个简单的例子 我们在插入的时候是直接在tail位置进行插入因为tail始终是指向最后一个队尾元素的下一个元素但是上图当中我们刚刚插入7这个元素之后就需要我们tail但是这样就完了吗这样会产生越界而且你是环形队列你index8的下一个位置应该是循环回头[0]我们的解决方法是%arr_len的方式。8 1之后再 % 数组长度9结果是0就回到了数组头的位置了 3. 代码手撕环形队列各个接口
3.1 代表封装一个环形队列 我们选择了数组结构实现环形队列那么我们就要在堆区开辟一个数组所以我们存储封装一个数组指针成员int* _a。 然后任何一个环形队列都是定长的所以我们不妨定义一个int _k代表当前队列最多能存储的有效元素的数量。这个_k也是 然后环形队列控制首尾也是必要的所以我们定义一个head和tail分别管理队头和队尾即分别负责删除和插入tail指代的是队尾元素的下一个位置空时与head重合。 //我们使用数组来模拟实现循环队列
typedef struct {int* _a; //数组实体int _k; //最大容纳有效数据个数int _head; //队头[删除]int _tail; //队尾[插入]
} MyCircularQueue;
3.2 环形队列的初始化 我们创建一个环形队列或者任何一个类对象就要对之完成初始化这里我们把创建环形队列的方法封装成一个接口myCircularQueueCreate返回的是一个在堆区创建环形队列的指针然后在这个接口当中我们对之完成初始化。 MyCircularQueue* myCircularQueueCreate(int k) {//在堆区开辟一个环形队列变量MyCircularQueueMyCircularQueue* p_circularQueue (MyCircularQueue*)malloc(sizeof(MyCircularQueue));p_circularQueue-_k k;p_circularQueue-_head 0;p_circularQueue-_tail 0; //默认一开始首尾指针指向[0]的位置//构造可以存储k个有效数据的环形队列空间需要我们开辟k1的空间int* ptmp (int*)malloc(sizeof(int)*(k1));if(ptmpNULL){exit(1);}p_circularQueue-_a ptmp;//返回创造的环形队列实体return p_circularQueue;
}
3.3 环形队列的插入 这里要两个需要特别注意的点一个判断当前环形队列是否为满环形队列是定长的如果为满就是插入失败。第二个点是tail的更新需要考虑从尾至首。 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//向循环队列插入一个元素。如果成功插入则返回真。//循环队列存满了就不让存了所以存在false插入失败的情况//1.判断是否为满(tail-nexthead)//tail的next不能简单我们需要考虑到从数组尾[k]到数组头[0]的情况,所以(tail);tail%(k1);即可int next_tail (obj-_tail1)%(obj-_k1);if(next_tailobj-_head){return false;}//2.进行插入obj-_a[obj-_tail] value;//更新tailobj-_tail next_tail;return true;
}
3.4环形队列的删除 如果为空不能删除删除就是直接head更新头的位置即可完成伪删除法但是此时还时要考虑head从尾至首这样的一个特殊情况。 bool myCircularQueueDeQueue(MyCircularQueue* obj) {//从循环队列中删除一个元素。如果成功删除则返回真。//存在是空的环形队列所以存在删除失败false的情况//1.判断是否为空:head与tail重合if(myCircularQueueIsEmpty(obj)) //obj-_headobj-_tail{return false;}//2.删除就是把head,指向下一个元素即可 //可是head也存在从数组尾更新到数组头的情况obj-_head;obj-_head%(obj-_k1);return true;
}
3.5环形队列的判空 我们设定head和tail重合的时候为空。 bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//两个指针重合代表空return obj-_headobj-_tail;
}
3.6环形队列的判满 满的时候我们设定的状态是tail的next值就是head那就是满状态。当然这里要记住我们存在从数组尾n-1到头0的转变所以说不能直接无脑对tail1哦 bool myCircularQueueIsFull(MyCircularQueue* obj) {//tail-nexthead代表满return (((obj-_tail)1)%(obj-_k1))obj-_head;
}
3.7环形队列的队头
int myCircularQueueFront(MyCircularQueue* obj) {//从队首获取元素。如果队列为空返回 -1 。//存在从空队列中取数据的情况,这种情况是非法情况if(myCircularQueueIsEmpty(obj)){return -1;}//队头的数据,就是head指向的数据return obj-_a[obj-_head];
}
3.8环形队列的队尾
int myCircularQueueRear(MyCircularQueue* obj) {//获取队尾元素。如果队列为空返回 -1 。//存在从空队列中取数据的情况,这种情况是非法情况if(myCircularQueueIsEmpty(obj)){return -1;}//tail指向的是下一个要插入的数据的位置//所以上一个队尾的数据应该是tail-1的位置//但是在这种情况下,tail也有从队首回到队尾的情况出现//所以我们需要淡出讨论这种情况if(obj-_tail 0){return obj-_a[obj-_k];}return obj-_a[obj-_tail-1];
}
3.9环形队列的销毁 环形队列的成员变量都是定义在堆区的然后指向的数组空间也是存储在堆区的我们使用完环形队列要对之销毁。 void myCircularQueueFree(MyCircularQueue* obj) {//释放所有的堆区空间free(obj-_a);free(obj);
}
