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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 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);
}





相关文章
|
2月前
|
Java 开发者 Spring
Spring AOP深度解析:探秘动态代理与增强逻辑
Spring框架中的AOP(Aspect-Oriented Programming,面向切面编程)功能为开发者提供了一种强大的工具,用以将横切关注点(如日志、事务管理等)与业务逻辑分离。本文将深入探讨Spring AOP的底层原理,包括动态代理机制和增强逻辑的实现。
53 4
|
2月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
3月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
2月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
3月前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
|
3月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
2月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
102 2
|
3月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
89 0
|
19天前
|
存储 设计模式 算法
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
|
19天前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析

推荐镜像

更多