循环队列详解!!c 语言版本(两种方法)双向链表和数组法!!

目录

1.什么是循环队列

2.循环队列的实现(两种方法)

第一种方法 数组法

1.源代码

2.源代码详解!!

1.创造队列空间和struct变量

2.队列判空

3.队列判满(重点)

4.队列的元素插入

5.队列的元素删除

6.队列的头元素

7.队列的尾元素(重点)

8.队列空间的释放

第二种方法 双向循环链表法

1.源代码

2.源代码详解!!

 1.创造哨兵位 和 struct 变量

2. 队列判空和队列判满

3.元素插入

4.元素删除

5.头元素

6.尾元素

7.空间的释放

三关于这两种方法的差距 

3.循环队列有什么用


1.什么是循环队列

首先关于循环队列,你得先知道什么是队列,详情可以去看看我的另一篇博客

数据结构 栈与队列详解!!-CSDN博客

这里简单的说一下,队列就是字面意思,你在银行排队,你不是什么VIP只是普通人,那你先排队那你就先得服务,队列就是 你先插入的数字(入队),就得先放出(出队)。大致就是这个意思。

而循环队列呢?他的原理也是队列,但和队列不同的地方在于,他的空间是固定的。在一个空间里进行重复的入队出队。

这是一张循环队列的大致图。

其中和队列一样有两个指针指向头和尾。添加实在尾针处加,而删除就是将队首的元素删除。为什么循环呢?就是在你的尾指针走到最后一格的时候(就是总共有5个空间,你的尾指针已经走到5并且已经插入数据)你的队列就满了,这时候循环队列已经不能插入数据,只能删除数据。

删除数据就是把你的头指针的元素删除,如果删除走到尾指针,头和尾在一个位置了。

所以综上可以抽象出,当你的头和尾指针走到一起的时候,这时候队列是空。

但你的尾走到底 头元素的上一个,那就说明你的队列已充满。

当队尾追到了队头那就是满,当队头追到了队尾那就是空

2.循环队列的实现(两种方法)

第一种方法 数组法

数组法采用的是 多开辟一个空间,用来做假溢出,判断队列是否充满,当然还有一种定size法,大家可以讨论一下!!

1.源代码

typedef struct {
	int* a;
	int front;
	int rear;
	int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->k = k;
	obj->front = 0;
	obj->rear = 0;
	return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	obj->rear %= obj->k + 1;
	obj->a[obj->rear] = value;

	obj->rear++;
	return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	obj->front %= obj->k + 1;
	obj->front++;
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->a[obj->rear - 1];
}



void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	obj->a = NULL;
	free(obj);
	obj = NULL;
}

2.源代码详解!!

1.创造队列空间和struct变量
typedef struct {
	int* a;
	int front;
	int rear;
	int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->k = k;
	obj->front = 0;
	obj->rear = 0;
	return obj;
}

 关于 匿名typedef struc 就是定义了一个类型名就叫做MyCircularQueue。

里面的元素第一个用来开辟空间,第二个定义头指针,第三个定义尾指针,第4个就是空间的大小。(这里的指针并不是真的指针,而是对于一个数组来说的下标)

关于 创造队列的空间,首先既然他是一个结构体变量,那得先给他开辟一个空间用来给里面的元素地址存储

第二因为你是要在一个数组里进行循环队列,那你就得开辟一块数组的空间。(k+1是因为这里采用的是多开辟一格进行判满)。

第三给结构体里的变量赋初始值。 

2.队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}

 关于队列的判空,就是两个队头和队尾指针如果重叠时,两者应该是满了或者空了的关系,所以两者的判断表达式不能相同,所以下面的判满得想到另一个表达式才能保证队列不报错(当队尾追到了队头那就是满,当队头追到了队尾那就是空)

3.队列判满(重点)
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

 这里关于队列的判满,采用的是这一串表达式的原因是,假设这时你开辟的有元素的空间是3,那现在的K就是3,但由于采用的是多开辟一格来判满的方法,那就是代表了开辟了4个空间。

4个空间对应的下标为0 1 2 3.那为什么要改两个指针rear和k加一呢?假设这时你的rear和front 都还在下标为 0 的位置,如果你不给 rear 加一 ,那你得出的结果就是 0 % 4 == 0.

这样导致的后果就是和 上面判空的条件 是一样的 0 == 0.会导致插入操作错误,会一直判满从而不能进行插入。

而如果你给 rear 和 k 都加一 就变成了 1 % 4 == 1.而这时 front 是 = 0的

就不会出现误判的情况。只有当你的 rear 走到你多开辟的那一块空间后才会出现判满的情况。(这只是当 front 没变的情况下的讨论,关于 front改变后的讨论,你可以构思一下大致相同。)

4.队列的元素插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	obj->rear %= obj->k + 1;
	obj->a[obj->rear] = value;

	obj->rear++;
	return true;
}

 队列的插入就是在rear的 下标初进行插入。首先你要进行判满,是因为循环队列如果满了以后就不会在追加新的元素,就很像游戏里的背包,满了以后就不能获得物品。为什么要让rear % k+1呢?因为当你的元素走到最后一格的下一格,这时候是越界访问的。因为是循环队列,所以可以把他重新变到下标为 0 的位置。

我们的rear 的位置,每次都会加1 所以每次是在rear 的位置插入数据。

5.队列的元素删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	
	obj->front++;
    obj->front %= obj->k + 1;
	return true;
}

 元素删除,首先如果你的队列为空那就删除不了了,返回false。

如果不为空,那front++ 即可,并且和 rear 一样要 % k+1,是为了使队列变成循环。如果不这样就会越界访问并且与题意不符(循环)。

要先++ 的原因是,如果你后++ 就会导致,如果此时你的front已经处于最后一个位置,

后++就会导致取头元素时 越界。如果先++ ,然后在%k+1 这样在出了最后一格以后可以及时,变回0 下标,不会越界。

6.队列的头元素
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->a[obj->front];
}

 返回头元素相较简单,只要返回此时front 位置的元素即可。

7.队列的尾元素(重点)
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	//if (obj->rear == 0)
	//{
	//	return obj->a[obj->k];
	//}
	//else
	//{
	//	return obj->a[obj->rear - 1];
	//}
	return obj->a[((obj->rear - 1) + (obj->k + 1)) % (obj->k + 1)];
}

 

 和头元素的不同点在于,队尾元素不能直接取队尾的下标。

因为由前面的插入操作我们可以知道,在rear位置插入数据后,rear是要进行++的,此时在rear下标里是没有元素的,队尾实际上是在rear 的前一个下标的位置。

但如果你只用 obj->a[obj->rear - 1] 来访问的话(如果你的rear是先%k +1,再++是可以的),但如果是先++,再%就不可以了,你可以思考一下当rear == 0,的时候,那你访问的就是obj->[-1] 那就是未知访问,错误。有两种方法。

第一种,判断当rear == 0的时候,你可以直接选择返回 最后一格 obj->k 的元素,

rear != 0时就返回 obj->rear - 1的下标的元素。

第二种,直接判断不用 if else,obj->a[((obj->rear - 1) + (obj->k + 1)) % (obj->k + 1)]。

这串表达式的意思就是,因为我们是要返回 rear - 1下标位置的元素,所以我们 rear - 1;

而 加上 k +1的原因是 在 rear -1 的位置下,你加+ 上这个循环队列的大小,那你还是在原地的,这里是为了防止特殊情况 rear = -1 时,rear = -1 原本是想访问 队列最后一个空间的元素,但等于 - 1访问不到,所以 rear = -1 加上 一个 k+1,其实就是等于 k ,k % k +1 = k。所以访问最后一个位置的元素。

8.队列空间的释放
void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	obj->a = NULL;
	free(obj);
	obj = NULL;
}

 将开辟的空间释放即可,但要先释放obj->a 处的空间。

第二种方法 双向循环链表法

1.源代码

typedef struct MyCircularQueue {
    struct MyCircularQueue* prev;
    struct MyCircularQueue* next;
    int val;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* phead = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    phead->next = phead;
    phead->prev = phead;
    phead->val = -1;
    phead->k = k;
    return phead;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if (obj->next == obj)
    {
        return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    MyCircularQueue* cur = obj->next;
    int size = 1;
    while (cur != obj)
    {
        cur = cur->next;
        size++;
    }
    return size == obj->k;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (newnode == NULL)
    {
        perror("malloc failed");
        exit(-1);
    }
    newnode->val = value;
    MyCircularQueue* prev = obj->prev;
    newnode->prev = prev;
    newnode->next = obj;
    prev->next = newnode;
    obj->prev = newnode;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    MyCircularQueue* Next = obj->next;
    obj->next = Next->next;
    Next->next->prev = obj;
    free(Next);
    Next = NULL;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->next->val;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->prev->val;
}



void myCircularQueueFree(MyCircularQueue* obj) {
    MyCircularQueue* cur = obj->next;
    while (cur != obj)
    {
        MyCircularQueue* del = cur;
        cur = cur->next;
        free(del);
        del = NULL;
    }
    free(obj);
    obj = NULL;
}

2.源代码详解!!

 1.创造哨兵位 和 struct 变量
typedef struct MyCircularQueue {
    struct MyCircularQueue* prev;
    struct MyCircularQueue* next;
    int val;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* phead = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    phead->next = phead;
    phead->prev = phead;
    phead->val = -1;
    phead->k = k;
    return phead;
}

 我们定义一个双链表的struct 结构。

然后再定义一个头结点,并且将 变量赋值。

2. 队列判空和队列判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if (obj->next == obj)
    {
        return true;
    }
    return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    MyCircularQueue* cur = obj->next;
    int size = 0;
    while (cur != obj)
    {
        cur = cur->next;
        size++;
    }
    return size == obj->k;
}

 相较于 数组的循环队列,双链表的判空判满就比较简单。空就是 只有一个哨兵位就是空。

满就是用一个size ++ 遍历链表,后如果size == obj->k 就是满。size 必须从 0 开始。

因为不从0 开始 ,总体队列会少一个空间。

3.元素插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (newnode == NULL)
    {
        perror("malloc failed");
        exit(-1);
    }
    newnode->val = value;
    MyCircularQueue* prev = obj->prev;
    newnode->prev = prev;
    newnode->next = obj;
    prev->next = newnode;
    obj->prev = newnode;
    return true;
}

元素的插入就是双链表的尾插。 

4.元素删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    MyCircularQueue* Next = obj->next;
    obj->next = Next->next;
    Next->next->prev = obj;
    free(Next);
    Next = NULL;
    return true;
}

元素删除就是双链表的头删。 

5.头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->next->val;
}

返回 头元素 

6.尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->prev->val;
}

返回尾元素 

7.空间的释放
void myCircularQueueFree(MyCircularQueue* obj) {
    MyCircularQueue* cur = obj->next;
    while (cur != obj)
    {
        MyCircularQueue* del = cur;
        cur = cur->next;
        free(del);
        del = NULL;
    }
    free(obj);
    obj = NULL;
}

双链表的销毁。 

三关于这两种方法的差距 

首先在数组 方法中,我们并没有采用循环来执行,这样的时间复杂度是0(1),而双向链表中有多处我们采用了while 循环所以时间复杂度是 o(n)。

数组写法中 坑很多需要很多思考,但是总体代码量是偏少的。

而链表虽然简单明了,但代码量是稍微多一点。需要细心检查。

3.循环队列有什么用

应用场景广泛:由于其高效的插入和删除操作、空间利用率高以及能够动态调整队列大小的特性,循环队列在许多领域都有广泛的应用,如操作系统中的任务调度、通信协议中的数据包处理、线程池中的线程管理等。所以循环队列是比较重要的

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/177258.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

网络工程师-HCIA网课视频学习(更换策略,这个网课质量不行)

这里是速成的,只积累下,自己未曾学习到的东西。通过书本补充知识点。 视频:hcia17-链路聚合_哔哩哔哩_bilibili hcia16-路由高级特性: hcia17-链路聚合: 由于如果根据视频来学习的话,感觉视频的总结并不…

MySQL数据库常见错误及解决方案

“时记数据安全,共享优质资源”,数据库安全是指数据库数据的完整、真实、可靠和可用性。数据库也是一种软件系统,与其他软件系统一样也需要保护,需要采取一定的技术和一定的安全管理策略,保证数据库中的数据不被泄漏、不被破坏、不被修改或删除。本文列举MySQL数据库常见错…

VulnHub DC-9

🍬 博主介绍👨‍🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏…

如何做好性能压测?压测环境设计和搭建的7个步骤你知道吗?

简介:一般来说,保证执行性能压测的环境和生产环境高度一致是执行一次有效性能压测的首要原则。有时候,即便是压测环境和生产环境有很细微的差别,都有可能导致整个压测活动评测出来的结果不准确。 1. 性能环境要考虑的要素 1.1 系…

HCIA-Datacom跟官方路线学习

通过两次更换策略。最后找到最终的学习方案,华为ICT官网有对这个路线的学习,hcia基础有这个学习路线,hcip也有目录路线。所以,最后制定学习路线,是根据这个认证的路线进行学习了: 官网课程:课程…

掌握 AI 和 NLP:深入研究 Python — 情感分析、NER 等

一、说明 我们见证了 BERT 等预训练模型在情感分析方面的强大功能,使我们能够破译隐藏在文本数据中的情感。通过 SpaCy,我们探索了命名实体识别的迷人世界,揭开了隐藏在非结构化文本中的秘密。 二、问题陈述 命名实体识别(NER)是自然语言处理中的一项关键…

2024贵州大学计算机考研分析

24计算机考研|上岸指南 贵州大学 贵州大学计算机科学与技术学院(贵州大学省级示范性软件学院)位于贵州省贵阳市花溪区贵州大学东校区。 计算机科学与技术学院(软件学院)自1972年创办计算机软件本科专业开始,至今已有…

灵活运用Vue 3中的setup函数—深入解析Composition API

新建项目,项目主入口为App.vue(主组件),新建child.vue(子组件)。 1.1 setup 执行 时机问题 1.在主组件里引入子组件和ref: import {ref} from vue import child from ./components/child.vue2…

12英寸双轴半自动划片机:颠覆传统划切工艺的五大优势

随着科技的飞速发展,半导体行业对精密划切设备的需求日益增长。在这篇文章中,我们将深入探讨12英寸双轴半自动划片机的优势,这种划片机在半导体制造过程中扮演着至关重要的角色。以下是这种划片机的五大优势。 一、高精度划切 12英寸双轴半自…

二十二、数组(4)

本章概要 随机生成泛型和基本数组 随机生成 我们可以按照 Count.java 的结构创建一个生成随机值的工具: Rand.java import java.util.*; import java.util.function.*;import static com.example.test.ConvertTo.primitive;public interface Rand {int MOD 10_0…

89. 格雷编码

89. 格雷编码 Java代码&#xff1a;2DFS class Solution {List<Integer> res new ArrayList<>();public List<Integer> grayCode(int n) {dfs(n, new StringBuffer(), new int[]{0, 1});return res;}public void dfs(int n, StringBuffer sb, int[] nums){i…

如何用【测试思维】做“支付功能”测试?

前言 跳槽高峰期&#xff0c;作为测试&#xff0c;不管是面试还是笔试&#xff0c;必然要被考验到的就是”测试思维“。在面试中就是体现在如下面试题中&#xff1a; “说说你项目中的 xx 模块你是如何测试的&#xff1f;” “给你一个购物车&#xff0c;你要怎么测试&#…

马斯克震撼演讲:我想创立一个新世界

目录 1拼多多杀入大模型领域&#xff1a;年薪百万招聘人才 2马斯克震撼演讲&#xff1a;我想创立一个新世界 3文心4.0上线首交答卷&#xff1a;百度2023Q3成色如何 1拼多多杀入大模型领域&#xff1a;年薪百万招聘人才 快科技11月22日消息&#xff0c;据国内媒体报道&#x…

解决ESP32内部RAM内存不足的问题

一&#xff0c;为什么需要外部RAM ESP32有520kB的内部RAM空间可以使用&#xff0c;这对于一般的情况是够用的&#xff0c;但是如果设备需要涉及音频或者显示图像等处理时&#xff0c;需要更大的内存空间来处理这些数据。ESP32支持扩展外部RAM&#xff0c;其实乐鑫已经在其ESP32…

2020年计网408

第33题 下图描述的协议要素是&#xff08; &#xff09;。I. 语法 II. 语义 III. 时序 A. 仅 I B. 仅 II C. 仅 III D. I、II 和 III 本题考察网络协议三要素的相关知识。 网络协议的三要素分别是语法、语义、同步&#xff08;时序&#xff09;。语法&#xff1a;定义收发双…

【PyGIS】使用阿里AIEarth快速下载指定区域指定年份的土地利用数据

说明 中国逐年土地覆盖数据集(CLCD) 由武汉大学的杨杰和黄昕教授团队基于Landsat影像制作了中国逐年土地覆盖数据集(annual China Land Cover Dataset, CLCD),数据包含1985—2021年中国逐年土地覆盖信息。研究团队基于Landsat长时序卫星观测数据,构建时空特征,结合随机森…

lombok 引入

lombok 依赖--><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId></dependency>

智能车入门补充篇——电感值处理、转向控制与巡线

冒泡法 冒泡法是一种简单的排序算法&#xff0c;它重复地遍历要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换&#xff0c;也就是说该数列已经排序完成。冒泡排序的时间复杂度为O(n^…

国内怎么投资黄金,炒黄金有哪些好方法?

随着我国综合实力的不断强大&#xff0c;投资市场的发展也日臻完善&#xff0c;现已成为了国际黄金市场的重要组成部分&#xff0c;人们想要精准判断金市走向&#xff0c;就离不开对我国经济等信息的仔细分析。而想要有效提升盈利概率&#xff0c;人们还需要掌握国内黄金投资的…

centos无法进入系统之原因解决办法集合

前言 可爱的小伙伴们&#xff0c;由于精力有限&#xff0c;暂时整理了两类。如果没有你遇到的问题也没有关系&#xff0c;欢迎底下留言评论或私信&#xff0c;小编看到后第一时间帮助解决 一. Centos 7 LVM xfs文件系统修复 情况1&#xff1a; [sda] Assuming drive cache:…