【初阶数据结构】深入解析循环队列:探索底层逻辑

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 【初阶数据结构】深入解析循环队列:探索底层逻辑

一、循环队列的概念

循环队列是一种用数组实现的队列数据结构,与普通队列不同的是,循环队列允许队列的头尾相接,实现循环利用数组空间。它解决了普通队列在出队操作频繁时需要大量元素迁移的效率问题。循环队列通常通过两个指针来实现:一个指向队列的头部(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 小总结

这里我们选择第二种方案进行实现,对此我们总结下,定义好的方式。

  1. front == back就是为空
  2. 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];//表示尾的情况
    else
    return 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);
}





目录
打赏
0
0
0
0
21
分享
相关文章
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
69 29
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
101 27
Spring AOP深度解析:探秘动态代理与增强逻辑
Spring框架中的AOP(Aspect-Oriented Programming,面向切面编程)功能为开发者提供了一种强大的工具,用以将横切关注点(如日志、事务管理等)与业务逻辑分离。本文将深入探讨Spring AOP的底层原理,包括动态代理机制和增强逻辑的实现。
72 4
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
339 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77

热门文章

最新文章

推荐镜像

更多