🔥引言
本篇将介绍如何实现循环队列并实现过程需要注意的事项,虽然篇幅较小,但是其中逻辑还是值得引人思考的,循环队列可以采用数组或链表实现,这篇将采用数组实现循环队列
🌈个人主页:是店小二呀
🌈C语言笔记专栏:C语言笔记
🌈C++笔记专栏: C++笔记
🌈初阶数据结构笔记专栏: 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
- 一、循环队列的概念
- 二、实现循环队列的知识铺垫(核心实现逻辑)
- 2.1 队列满足什么条件为空
- 2.2 解决何时为空何时为满的方案
- 2.3 小总结
- 2.4 循环队列中如何保证闭环
- 2.5 计算循环队列的数据个数
- 三、实现循环队列相关步骤
- 3.1 循环队列的搭建
- 3.2 构建器(设置队列长度为 k)
- 3.3 判断循环队列是否为满和空的情况
- 3.4 检查是否能插入数据和删除数据
- 3.5 获得队首元素和队尾元素
- 3.6 循环的销毁
一、循环队列的概念
循环队列是一种用数组实现的队列数据结构,与普通队列不同的是,循环队列允许队列的头尾相接,实现循环利用数组空间。它解决了普通队列在出队操作频繁时需要大量元素迁移的效率问题。循环队列通常通过两个指针来实现:一个指向队列的头部(front),一个指向队列的尾部(rear)。当队列满时,rear 指针可以绕回到数组的起始位置,实现循环存储;当队列为空时,front 和 rear 指针指向同一个位置。
二、实现循环队列的知识铺垫(核心实现逻辑)
2.1 队列满足什么条件为空
当front==back时不一定为空。这里是循环队列,如果出现front= =back时会出现下列两种情况
- back通过循环与front相遇,此时front==back,则队列满了
- 一开始back没有移动,back和front在同位置,此时front==back,则队列为空
对此我们无法通过front==back区分开空和满的情况,需要重新定义为空或满的标志
2.2 解决何时为空何时为满的方案
关于front和back初始位置,front指向对头,而由于back指向队尾会很难看,需要手动back置为-1,对此这里back指向队尾的下一个元素(跟栈中top定义问题是类似的)
判断满的两种方案:
- 增加一个size,当front== back并且size= =0就为空,size!=0就是为满
- 多开一个空间,这样的好处就是back+1==front为满(不要存储数据,这样又回到了不能判断空或满)
2.3 小总结
这里我们选择第二种方案进行实现,对此我们总结下,定义好的方式。
- front == back就是为空
- back + 1 == front就是为满
2.4 循环队列中如何保证闭环
如果遇到循环相关问题,可以考虑取模(解决问题上十分巧妙)。我们想要达到的目的是当back到达空位置时,就是相当于到了头位置。
同时取模中,如果左边小于右边,没有改变。如果左边大于左边,就会删除右边的倍数,直到左边小于右边(这里就是取模的逻辑,如果很难理解,可以通过图来理解下)
这里需要注意的是:这张图我们需要关注的地方back + 1和 head的位置
,k +1是空位置
,下标为4和0位置重叠处
三处。这里size为有效元素个数,这里只多开一个空间并没有算上有效元素,然后k + 1到达空位置,我们想要的结果是我们想要达到的目的是当back到达空位置时,就是相当于到了头位置,这里(obj->back+1)%(obj->size+1)==obj->head;
就满足了这种情况,相同数据取模模为0
,意味着下标为0
2.5 计算循环队列的数据个数
如果是计算队列的数据个数,通常就是back - front,但是这里是循环队列可能会出现back在front前面的特殊情况。
解决措施:(back+(k+1)-front)%k+1。这里担心back - front出现负数,个数不是存在负数这种情况的。那么可以将back + (k + 1) - front % k + 1
这样保证了back - front + (k + 1) % k + 1
当back - front出现负数,增加k + 1保证了正数再取模保证数据没有超过循环队列的长度,那么这样得到数据个数是否正确呢?通过画图在整个循环中的代表位置是相同的。
只要理解上面相关知识,模拟实现循环队列也变得简单起来了,让我们模拟实现起来吧!
三、实现循环队列相关步骤
3.1 循环队列的搭建
typedef struct
{int *a;int size;int head;int back;//元素的下一个位置
} MyCircularQueue;
//head 和 back都为下标
这里需要注意的是:这里没有跟队列一样采用两个结构体设计,而是采用在结构体对象内开辟一块空间用于存储节点,再调用结构体成员进行头尾操作,达到循环队列的功能。
3.2 构建器(设置队列长度为 k)
MyCircularQueue* myCircularQueueCreate(int k) //为结构体开辟空间
{ MyCircularQueue *obj=(MyCircularQueue *)malloc(sizeof(MyCircularQueue));if(obj==NULL)return NULL;obj->a=(int *)malloc(sizeof(int)*(k+1));//多开一个空间if(obj->a==NULL)return NULL;obj->size=k;obj->back=obj->head=0;return obj;
}
这里需要注意的是:关于两次调用malloc
函数开辟空间,第一次malloc
开辟空间,用于为该结构体对象开辟空间,第二次malloc
开辟空间,是为了队列元素开辟空间(包含了不存放数据的空间),这空间是关联在一起的,对此需要搞清楚需要开辟多大的空间和交给什么数据类型维护
3.3 判断循环队列是否为满和空的情况
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj->back+1)%(obj->size+1)==obj->head;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);return obj->head==obj->back;
}
这里需要注意的是:对于判断是否为空,不是重点,对于判断是否为满,根据取模的特点进行处理,对于数据结构处理建议画图分析
3.4 检查是否能插入数据和删除数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj->back++;//防止越界obj->back%=(obj->size+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return false;obj->head++;//防止越界obj->head%=(obj->size+1);return true;
}
这里需要注意的是:这里无论是插入还是删除数据,需要对x %= (obj->size+1);
防止超过队列长度,而且这里需要注意顺序问题
3.5 获得队首元素和队尾元素
int myCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;if(obj->back==0)//插入的时候return obj->a[obj->size];//表示尾的情况elsereturn obj->a[obj->back-1];//return obj->a[(obj->back-1+obj->size+1)%(obj->size+1)];
}
这里需要注意的是:这里获得队首元素和队尾元素,都需要先判断循环队列是否为空。在获得队尾元素中,一般情况下 obj->a[obj->back-1]
是没有问题的,但是如果在插入一个数据,back回到首元素位置上,back-1
就会出现问题,会导致越界访问,对此obj->a[(obj->back-1+obj->size+1)%(obj->size+1)];
可以将这个循环队列展开一段,加obj->size+1
再取obj->size+1
模,这里同计算循环队列有效数据长度的方式是一样的。
3.6 循环的销毁
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj->a);free(obj);
}
以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二初阶数据结构笔记,希望对你在学习初阶数据结构中有所帮助!