当前位置： 首页 > article >正文

循环队列（C语言版）

article 2025/1/23 9:35:19

循环队列(C语言版）

  • 1.简单介绍循环队列
  • 2.使用何种结构来实现
  • 3.基本结构
  • 4.初始化
  • 5.判空判满
  • 6.向循环队列插入一个元素
  • 7.从循环队列中删除一个元素
  • 8.获取队头队尾元素
  • 9.释放空间
  • 10.完整代码

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：简单介绍循环队列；使用何种结构来实现；基本结构；初始化；判空判满；向循环队列插入一个元素；从循环队列中删除一个元素；获取队头队尾元素；释放空间；完整代码
⬆⬆⬆⬆上一篇：C++priority_queue模拟实现
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

1.简单介绍循环队列

循环队列本质上是也是一个队列，也是“先进先出”的特性，只不过循环队列有空间限制，而不是可以无限添加元素，同时从逻辑上看，它是一个首尾相连的一个环形。
在这里插入图片描述在leetcode上有一道题，也是实现循环队列的，可以看一下☞设计循环队列

2.使用何种结构来实现

对于实现循环队列，有两种选择，一种是使用顺序表，一种是使用链表，但是哪种更好呢？
在这里插入图片描述
在这里插入图片描述
我们先来看一下leetcode上要求写的函数，需要实现判空判满还有获取队尾数据等，首先谈谈判空判满，见下图：在这里插入图片描述
可以发现，当循环队列满或者空时，front和rear都指向同一个结点，这样我们就难以区分，因此需要增加一个节点，因为它是循环的，这个节点在front，rear的调整的过程中也会存储上数据，但是下图中是不存储数据的，因为整个链表中必须有一个空的节点来保证能够区分空和满
在这里插入图片描述
但是链表能否完成获取队尾的数据，我们的链表是单循环链表，无法找到前置节点，所以说对于链表实现循环队列会比较麻烦，不过也可以使用双向循环链表来实现。
我们这边还是主要考虑使用顺序表来实现，front和rear都是下标，顺序表简单来讲只需要通过rear-1即可获取到我们的队尾元素。
顺序表的判满和判空和链表一样，需要多开一个空间，其实也可以增加一个size来判断满和空
在这里插入图片描述

3.基本结构

typedef struct {
    int* arr;//指向开辟的空间
    int k;//有效空间个数
    int front;//队头
    int rear;//队尾

} MyCircularQueue;

我们直接在leetcode上完成循环队列的实现
按照我们之间画的图以及理解的，我们先需要声明一个结构体来预想一个循环队列

4.初始化

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先在堆上创建一个结构体变量
    obj->arr=(int*)malloc(sizeof(int)*(k+1));//顺序表的开辟；k+1是为了能多一个空间来区别空和满
    obj->k=k;
    obj->front=obj->rear=0;//队头和队尾一开始都指向顺序表的头，此时为空
    return obj;
}

5.判空判满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    if(obj->front==obj->rear)//只要队头队尾指向同一个位置，那么循环队列就为空
    {
        return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    //rear的下一个位置是front那么就为满，k+1是因为k是有效空间个数，但是空间是多一个的
    if((obj->rear+1)%(obj->k+1)==obj->front)
    {
        return true;
    }
    return false;
}

对于叛空没什么问题，但是大家可能对判满有一个疑问，为什么需要%？
在这里插入图片描述
如果不进行%的话，rear+1就直接超出了我们的循环队列，rear+1是6，k+1是6，进行%，正好和front相等。并且在rear+1在小于6的情况下（不超过循环队列时），并不会受%的影响

6.向循环队列插入一个元素

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
 {
    if(myCircularQueueIsFull(obj))
    {
        //满了就不能放元素了
        return false;
    }
    obj->arr[obj->rear++]=value;//直接在rear位置放入元素，同时位置向后+1
    obj->rear%=(obj->k+1);//保证不会越界，如果超过的最后一个位置，就需要回到第一个位置
    return true;
}

在这里插入图片描述rear始终指向有效元素的下一个位置，每次直接插入即可，不过插入完后要对rear进行++
在这里插入图片描述
在不停地插入和删除中，rear和front都会发生改变，因此对于rear我们也要对它进行调整，保证它不会越界，一旦指向越界，回到开头。

7.从循环队列中删除一个元素

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
    {
        //循环队列为空就无法删除
        return false;
    }
    obj->front++;//直接队头位置+1即可
    obj->front%=(obj->k+1);//保证不会越界
	return true;
}

在这里插入图片描述
和前面插入元素一样，要保证front不能越界

8.获取队头队尾元素

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //保证不为空
        return -1;
    }
    else
    {
        return obj->arr[obj->front];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //保证不为空
        return -1;
    }
    else
    {
		return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用
    }
}

获取队头元素没什么好说的，主要是获取队尾元素，因为rear是指向最后一个元素的下一个位置，当rear为0时就不能直接rear-1来获取
在这里插入图片描述
上图分析了如何找到原位置，但是还要注意这只是一种情况，还有其他比较正常的情况也要适用，因此代码中需要%（k+1）
在这里插入图片描述
如果觉得使用%太复杂，也可以使用下面的方式

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //保证不为空
        return -1;
    }
    else
    {
//return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用
    return obj->arr[obj->rear==0?obj->k:obj->rear-1];
    }
}

obj->k是有效空间的个数，它作为下标正好指向最后一个空间；rear正常情况下只需要-1即可访问队尾元素
在这里插入图片描述

9.释放空间

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->arr);
    free(obj);
}

10.完整代码

这部分完整代码是leetcode答题区的，而不是能直接放在编译器中直接运行的




typedef struct {
    int* arr;//指向开辟的空间
    int k;//有效空间个数
    int front;//队头
    int rear;//队尾

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先在堆上创建一个结构体变量
    obj->arr=(int*)malloc(sizeof(int)*(k+1));//顺序表的开辟；k+1是为了能多一个空间来区别空和满
    obj->k=k;
    obj->front=obj->rear=0;//队头和队尾一开始都指向顺序表的头，此时为空
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear)//只要队头队尾指向同一个位置，那么循环队列就为空
    {
        return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //rear的下一个位置是front那么就为满，k+1是因为k是有效空间个数，但是空间是多一个的
    if((obj->rear+1)%(obj->k+1)==obj->front)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        //满了就不能放元素了
        return false;
    }
    obj->arr[obj->rear++]=value;//直接在rear位置放入元素，同时位置向后+1
    obj->rear%=(obj->k+1);//保证不会越界，如果超过的最后一个位置，就需要回到第一个位置
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //循环队列为空就无法删除
        return false;
    }
    obj->front++;//直接队头位置+1即可
    obj->front%=(obj->k+1);//保证不会越界
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //保证不为空
        return -1;
    }
    else
    {
        return obj->arr[obj->front];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        //保证不为空
        return -1;
    }
    else
    {
//return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用
    return obj->arr[obj->rear==0?obj->k:obj->rear-1];
    }
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

🌸🌸循环队列（C语言版）的知识大概就讲到这里啦，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪


http://www.kler.cn/a/514716.html

相关文章：

  • C#性能优化技巧：利用Lazy＜T＞实现集合元素的延迟加载
  • 25/1/22 算法笔记＜ROS2＞ TF变换
  • 计算机组成原理(计算机系统3)--实验八：处理器结构拓展实验
  • 将UI界面交给第三方库
  • C++入门基础篇：域、C++的输入输出、缺省参数、函数重载、引用、inline、nullptr
  • MATLAB语言的文件操作
  • AGI发展的现实约束与定义困境
  • 学习记录-统计记录场景下的Redis写请求合并优化实践
  • [矩阵扩散]
  • VUE elTree 无子级 隐藏展开图标
  • Java高频面试之SE-16
  • C++----STL（vector）
  • curl简介与libcurl开源库的使用总结
  • 在电商行业中，3D模型的应用有哪些？
  • ECCV 2024，全新激活函数！
  • 【面试题】MQ部分[2025/1/13 ~ 2025/1/19]
  • 【Uniapp-Vue3】StorageSync数据缓存API
  • OGG 19C 集成模式启用DDL复制
  • ORA-15041 ORA-15023
  • Kotlin 2.1.0 入门教程（八）
  • js截取video视频某一帧为图片
  • Kafka 入门与应用实战：吞吐量优化与与 RabbitMQ、RocketMQ 的对比
  • SVM模型实战1
  • RabbitMQ 在实际应用时要注意的问题
  • Qt基础项目篇——Qt版Word字处理软件
  • 代码随想录day15