数据结构:循环队列的实现(leetcode622.设计循环队列)

news/2024/4/24 20:12:32/文章来源:https://blog.csdn.net/weixin_73470348/article/details/129167702

 

目录

一.循环队列简单介绍

二.用静态数组实现循环队列

1.数组循环队列结构设计

2.数组循环队列的堆区内存申请接口 

3.数据出队和入队的接口实现

4.其他操作接口

5.数组循环队列的实现代码总览 

三.静态单向循环链表实现循环队列 

1.链表循环队列的结构设计

2.创建静态单向循环链表的接口

3.数据的出队和入队接口

4.其他队列操作接口

5.静态链表循环队列总体代码

问题来源:622. 设计循环队列 - 力扣（Leetcode）

一.循环队列简单介绍

  • 循环队列一般是一种静态的线性数据结构,其中的数据符合先进先出的原则.
  • 循环队列的容器首地址和容器尾地址通过特定操作(比如指针链接,数组下标取余等方式)相连通,从而实现了容器空间的重复利用(在一个非循环静态队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间)

 

二.用静态数组实现循环队列

维护队列的结构体:

typedef struct 
{int * arry;  //指向堆区数组的指针int head;    //队头指针int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)int capacity;//静态队列的容量
} MyCircularQueue;

1.数组循环队列结构设计

我们假定静态数组的容量为k(可存储k个数据)：

  • 根据队列的基本数据结构:有两个指针用于维护数组中的有效数据空间,分别为head指针和tail指针,head指针用于指向队头数据,tail用于指向队尾数据的下一个位置(即tail指针不指向有效数据)
  •  如图所示,head指针和tail指针之间就是有效数据的内存空间
  • 通过head指针和tail指针的关系来实现队列的判满(判断队列空间是否已被占满)与判空(判断队列是否为空队列)；为了达到这个目的,我们需要将静态数组的容量大小设置为k+1(即多设置一个元素空间) 
  1. 队列的判空条件: tail == head;
  2. 队列的判满条件: (tail+1)%(k+1) == head; 另外一种情形:
  • 由此我们可以先设计出队列的判满和判空接口： 
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空
{assert(obj);return (obj->tail == obj->head);
}bool myCircularQueueIsFull(MyCircularQueue* obj)  //判断队列是否为满
{assert(obj);return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}

2.数组循环队列的堆区内存申请接口 

  • 在堆区上创建MyCircularQueue结构体,同时为队列申请一个空间大小为(k+1)*sizeof(DataType)字节的数组： 
    MyCircularQueue* myCircularQueueCreate(int k)  //k个容量大小的循环队列的初始化接口
{MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));//开辟维护循环队列的结构体if(NULL == tem){perror("malloc failed");exit(-1);}tem->arry = NULL;tem->capacity = k;   //队列的数据容量为ktem->arry = (int*)malloc((k+1)*sizeof(int));//开辟堆区数组if(NULL == tem->arry){perror("malloc failed");exit(-1);}//将head,tail下标初始化为0tem->head = 0; tem->tail = 0;return tem;
}

3.数据出队和入队的接口实现

数据出队和入队的图解:

 

  •  根据图解我们可以设计出数据入队和出队的接口: 
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口
{assert(obj);if(myCircularQueueIsFull(obj)){return false;}//确保队列没满obj->arry[obj->tail]=value;obj->tail = (obj->tail + 1)%(obj->capacity +1);return true;
}
    bool myCircularQueueDeQueue(MyCircularQueue* obj)    //数据出队接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//确保队列不为空obj->head = (obj->head +1)%(obj->capacity +1);return true;
}

4.其他操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)   //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arry[obj->head];
}

 返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;//注意tail如果指向数组首地址,则尾数据位于数组最后一个位置return obj->arry[labelret];
}

队列的销毁接口:

void myCircularQueueFree(MyCircularQueue* obj)     //销毁队列的接口
{assert(obj);free(obj->arry);obj->arry = NULL;free(obj);obj = NULL;
}

5.数组循环队列的实现代码总览 

 数组循环队列总体代码:

typedef struct 
{int * arry;  //指向堆区数组的指针int head;    //队头指针int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)int capacity;//静态队列容量
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明MyCircularQueue* myCircularQueueCreate(int k)          //循环队列初始化接口
{MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));//开辟维护循环队列的结构体if(NULL == tem){perror("malloc failed");exit(-1);}tem->arry = NULL;tem->capacity = k;   //队列的数据容量为ktem->arry = (int*)malloc((k+1)*sizeof(int));//开辟堆区数组if(NULL == tem->arry){perror("malloc failed");exit(-1);}tem->head = 0;tem->tail = 0;return tem;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口
{assert(obj);if(myCircularQueueIsFull(obj)){return false;}//确保队列没满obj->arry[obj->tail]=value;obj->tail = (obj->tail + 1)%(obj->capacity +1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)           //数据出队接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//确保队列不为空obj->head = (obj->head +1)%(obj->capacity +1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)               //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arry[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj)                 //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;//注意tail如果指向数组首地址,则尾数据位于数组最后一个位置return obj->arry[labelret];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)              //判断队列是否为空
{assert(obj);return (obj->tail == obj->head);
}bool myCircularQueueIsFull(MyCircularQueue* obj)               //判断队列是否为满
{assert(obj);return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}void myCircularQueueFree(MyCircularQueue* obj)                 //销毁队列的接口
{assert(obj);free(obj->arry);obj->arry = NULL;free(obj);obj = NULL;
}

力扣题解测试:

三.静态单向循环链表实现循环队列 

链表节点结构体定义:

typedef struct listnode
{int data;struct listnode * next;
}ListNode;

维护链表循环队列的结构体:

typedef struct 
{int capacity;     //记录队列容量大小ListNode * head;  //指向队头节点ListNode * tail;  //指向队尾节点
} MyCircularQueue;

1.链表循环队列的结构设计

静态单向循环链表的容量大小为k:

  • 与数组循环队列类似,我们同样需要开辟一个节点个数为k+1的静态循环链表
  • 链表循环队列的总体结构图示:另外一种队列判满的情形:
  1.  链表循环队列的判满条件(判断队列空间是否被占满的关系式):tail->next == head;
  2.  链表循环队列的判空条件(判断队列是否为空队列的关系式): tail == head;

链表循环队列的判满和判空的接口:

bool myCircularQueueIsEmpty(MyCircularQueue* obj)    //判断队列是否为空
{assert(obj);return(obj->head == obj->tail);
}bool myCircularQueueIsFull(MyCircularQueue* obj)     //判断队列是否为满
{assert(obj);return (obj->tail->next == obj->head);
}

2.创建静态单向循环链表的接口

实现一个接口,创建一个维护链表循环队列的结构体同时创建容量大小为k+1的静态单向循环链表:

MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{int NodeNum =k+1;                          //创建k+1个链表节点MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object);                            //申请维护循环队列的结构体object->capacity = k;ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum == k+1){   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode = tem;object->tail = object->head=tem;    //让tail和head指向同一个初始节点}else{ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode->next = tem;                //链接链表节点preNode = tem;}NodeNum--;}preNode->next = object->head;               //将表尾与表头相接return object;
}

3.数据的出队和入队接口

数据出入队图解:

根据图解实现数据出入队接口:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//数据入队接口(从队尾入队)
{assert(obj);if(!obj || myCircularQueueIsFull(obj))  //确定队列没满{return false;}           obj->tail->data = value;                //数据入队obj->tail = obj->tail->next;return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)  //数据出队接口
{assert(obj);if(!obj || myCircularQueueIsEmpty(obj)){return false;}//数据出队obj->head = obj->head->next;return true;
}

4.其他队列操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->head->data; //返回队头元素
}

返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}ListNode * tem = obj->head;while(tem->next != obj->tail)               //寻找队尾元素{tem=tem->next;}return tem->data;  //返回队尾元素
}

队列销毁接口:

队列销毁过程图解:

void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{assert(obj);//利用头指针来完成链表节点的释放ListNode * endpoint = obj->head;           //记录一个节点释放的终点obj->head = obj->head->next;while(obj->head!=endpoint){ListNode * tem = obj->head->next;free(obj->head);obj->head = tem;}free(endpoint);                            //释放掉终点节点free(obj);                                 //释放掉维护环形队列的结构体
}

5.静态链表循环队列总体代码

总体代码:

typedef struct listnode
{int data;struct listnode * next;
}ListNode;typedef struct 
{int capacity;ListNode * head;ListNode * tail;int taildata;   //单向链表找尾复杂度为O(N),因此我们用一个变量来记录队尾数据
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{int NodeNum =k+1;                          //创建k+1个链表节点MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object);                            //申请维护循环队列的结构体object->capacity = k;ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum == k+1){   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode = tem;object->tail = object->head=tem;    //让tail和head指向同一个初始节点}else{ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode->next = tem;                //链接链表节点preNode = tem;}NodeNum--;}preNode->next = object->head;               //将表尾与表头相接return object;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口(从队尾入队)
{assert(obj);if(!obj || myCircularQueueIsFull(obj))  //确定队列没满{return false;}           obj->tail->data = value;                //数据入队obj->tail = obj->tail->next;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)               //数据出队接口
{assert(obj);if(!obj || myCircularQueueIsEmpty(obj)){return false;}obj->head = obj->head->next;return true;
}int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}ListNode * tem = obj->head;while(tem->next != obj->tail)               //寻找队尾元素{tem=tem->next;}return tem->data;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)                  //判断队列是否为空
{assert(obj);return(obj->head == obj->tail);
}bool myCircularQueueIsFull(MyCircularQueue* obj)                    //判断队列是否为满
{assert(obj);return (obj->tail->next == obj->head);
}void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{assert(obj);//利用头指针来完成链表节点的释放ListNode * endpoint = obj->head;           //记录一个节点释放的终点obj->head = obj->head->next;while(obj->head!=endpoint){ListNode * tem = obj->head->next;free(obj->head);obj->head = tem;}free(endpoint);                            //释放掉终点节点free(obj);                                 //释放掉维护环形队列的结构体
}

leetcode题解测试:

 

 

 

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

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Linux服务：Nginx服务配置及相关模块

Linux服务：Nginx服务配置及相关模块

目录 一、Nginx配置文件 1、主配置文件解析 2、子配置文件启用 二、子配置文件使用 1、创建虚拟主机实验 2、基于端口虚拟主机实验 三、Nginx模块 1、access模块 2、自定义错误页面 3、状态页开启 一、Nginx配置文件 1、主配置文件解析 ①yum安装主配置文件位置&…
阅读更多...
攻击者失手，自己杀死了僵尸网络 KmsdBot

攻击者失手，自己杀死了僵尸网络 KmsdBot

此前，Akamai 的安全研究员披露了 KmsdBot 僵尸网络，该僵尸网络主要通过 SSH 爆破与弱口令进行传播。在对该僵尸网络的持续跟踪中，研究人员发现了一些有趣的事情。 C&C 控制 对恶意活动来说，最致命的就是夺取对 C&C 服务…
阅读更多...
Anaconda环境配置

Anaconda环境配置

1.进入清华大学镜像网站Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror，下载稳定版Anaconda3-5.2.0，如下图。2.放到整理好的文件夹中，双击安装包进行安装。3.安装过程中需要改变的默认值如下&#xff…
阅读更多...
【数据库】redis数据持久化

【数据库】redis数据持久化

目录 数据持久化 一， RDB 1， 什么是RDB 2，持久化流程 3， 相关配置 案例演示： 4， 备份和恢复 1、备份 2、恢复 3，优势 4， 劣势 二，AOF 1，什么是A…
阅读更多...
说说 React 中 fiber、DOM、ReactElement、实例对象之间的引用关系

说说 React 中 fiber、DOM、ReactElement、实例对象之间的引用关系

原生组件 fiber 原生组件 fiber，指的就是 type 为 “span”、“div” 的 fiber。 1.fiber.stateNode 指向真实 DOM 节点；2.node["__reactFiber$" randomKey] 指向对应 fiber，使用随机数是防止和业务代码的属性名冲突，…
阅读更多...
Scala模式匹配详解(第八章:基本语法、模式守卫、模式匹配类型)(尚硅谷笔记)

Scala模式匹配详解(第八章:基本语法、模式守卫、模式匹配类型)(尚硅谷笔记)

模式匹配第 8 章 模式匹配8.1 基本语法8.2 模式守卫8.3 模式匹配类型8.3.1 匹配常量8.3.2 匹配类型8.3.3 匹配数组8.3.4 匹配列表8.3.5 匹配元组8.3.6 匹配对象及样例类8.4 变量声明中的模式匹配8.5 for 表达式中的模式匹配8.6 偏函数中的模式匹配(了解)第 8 章 模式匹配 Scal…
阅读更多...
论文解读 | [AAAI2020] 你所需要的是边界:走向任意形状的文本定位

论文解读 | [AAAI2020] 你所需要的是边界:走向任意形状的文本定位

目录 1、研究背景 2、研究的目的 3、方法论 3.1 Boundary Point Detection Network(BPDN) 3.2 Recognition Network 3.3 Loss Functions 4、实验及结果 论文连接：https://ojs.aaai.org/index.php/AAAI/article/view/6896 1、研究背景 最近，旨在…
阅读更多...
深度解读 ｜ 数据资产管理面临诸多挑战，做好这5个措施是关键

深度解读 ｜ 数据资产管理面临诸多挑战，做好这5个措施是关键

日前，大数据技术标准推进委员会（中国通信标准化协会下（CCSA）的专业技术委员会，简称TC601）发布《数据资产管理实践白皮书》（6.0 版）（以下简称：报告&#xff09…
阅读更多...
浏览器跨域问题

浏览器跨域问题

跨域问题什么是跨域问题如何解决跨域问题JSONPCORS方式解决跨域使用 Nginx 反向代理使用 WebSocket跨源请求是否能携带Cookie什么是跨域问题 跨域问题指的是不同站点之间，使用 ajax 无法相互调用的问题。跨域问题本质是浏览器的一种保护机制，它的初衷是为…
阅读更多...
LQB01位操作说明

LQB01位操作说明

一个字节，包括了8位，可以对其中的8位的某一位进行读或者写； 比如char num12,如果用十六进制表示，就是0x0C，如果二进制表示，就是0000 1010 位操作函数，主要这里介绍，位读和位写0&am…
阅读更多...
【消费战略方法论】认识消费者的恒常原理（一）：消费者稳态平衡原理

【消费战略方法论】认识消费者的恒常原理（一）：消费者稳态平衡原理

“消费战略”是塔望咨询基于大量的战略与营销实践经验结合心理学、经济学、传播学等相关专业学科的知识应用进行提炼与创造形成的战略方法体系。消费战略强调以消费者为导向，进行企业、品牌战略、品牌营销的制订和落地，企业经营的每个环节和输出的每个动…
阅读更多...
轻松搭建Redis缓存高可用集群

轻松搭建Redis缓存高可用集群

1. 安装单机Redis 安装步骤： 1.1 下载redis 官网下载3.0.0版本，之前几的版本不支持集群模式 下载地址：http://download.redis.io/releases/redis-3.0.0.tar.gz 1.2 首先需要安装gcc yum install gcc 1.3 创建目录 cd /usr/mkdir soft1.…
阅读更多...
GitHub标星30K+的Java面试八股文长啥样？

GitHub标星30K+的Java面试八股文长啥样？

2023年的互联网行业竞争越来越严峻，面试也是越来越难，一直以来我都想整理一套完美的面试宝典，奈何难抽出时间，这套1000道的Java面试手册我整理了整整1个月，上传到Git上目前star数达到了30K 一、32 道 MySQL 面试题 1&…
阅读更多...
DACS: Domain Adaptation via Cross-domain Mixed Sampling 学习笔记

DACS: Domain Adaptation via Cross-domain Mixed Sampling 学习笔记

DACS介绍方法Naive MixingDACSClassMix![在这里插入图片描述](https://img-blog.csdnimg.cn/ca4f83a2711e49f3b754ca90d774cd50.png)算法流程实验结果反思介绍 近年来，基于卷积神经网络的语义分割模型在众多应用中表现出了显著的性能。然而当应用于新的领域时&…
阅读更多...
乐友商城学习笔记（一）

乐友商城学习笔记（一）

SpringCloud 什么是SpringCloud 在SpringBoot基础上构建的微服务框架固定步骤 1.引入组件的启动器2.覆盖默认配置3.在引导类上添加相应的注解 eureka 注册中心，服务的注册与发现服务端 1.引入服务器启动器：eureka-server2.添加了配置 spring.applicati…
阅读更多...
leetcode 21~30 学习经历

leetcode 21~30 学习经历

leetcode 21~30 学习经历21. 合并两个有序链表22. 括号生成23. 合并K个升序链表24. 两两交换链表中的节点25. K 个一组翻转链表26. 删除有序数组中的重复项27. 移除元素28. 找出字符串中第一个匹配项的下标29. 两数相除30. 串联所有单词的子串小结21. 合并两个有序链表 将两个升…
阅读更多...
opencv-StereoBM算法流程（二）

opencv-StereoBM算法流程（二）

OpenCV BM对于处理非畸变的立体图像, 主要有以下 3 个步骤:1. 预处理滤波: 使图像亮度归一化并加强图像纹理2. 立体匹配: 沿着水平极线用 SAD 窗口进行匹配搜索3. 再滤波: 去除坏的匹配点.匹配之后, 如果左右视差检查使能了 disp12MaxDiff > 0, 还有使用cv::validateDispari…
阅读更多...
复习知识点三:做人不能半途而废,就算躺平也要躺最舒服的那张床

复习知识点三:做人不能半途而废,就算躺平也要躺最舒服的那张床

目录 运算符​编辑 键盘录入: 练习:键盘输入数字并求和 练习: 算术运算符 隐式转换(自动类型提升) 强制转换 练习1: 字符串的 "" 操作 ​编辑 练习 1: 练习2: 练习3: 自增自减运算符 赋值运算符 关系运算符(比较运算符)的分类 练习: 逻辑运算符 短路逻辑运…
阅读更多...
qt qchart学习

qt qchart学习

Qt Charts主要由QChartView、QChart、QLegend图例、坐标轴(由QAbstractAxis子类实现)、**数据源(由QAbstractSeries子类实现)**等组成使用QChart的前期准备1. Qt5.9及以上版本；2. .pro文件中添加QT charts3. 在使用QChart的各个控件之前，引用头文件并必…
阅读更多...
Vulnhub靶场----4、DC-4

Vulnhub靶场----4、DC-4

文章目录一、环境搭建二、渗透流程三、思路总结一、环境搭建 DC-4下载地址：https://download.vulnhub.com/dc/DC-4.zip kali：192.168.144.148 DC-4：192.168.144.152 二、渗透流程 端口扫描：nmap -T5 -p- -sV -sT -A 192.168.144.1…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站