4.C_数据结构_队列

概述

什么是队列：

队列是限定在两端进行插入操作和删除操作的线性表。具有先入先出(FIFO)的特点

相关名词：

  • 队尾：写入数据的一段
  • 队头：读取数据的一段
  • 空队：队列中没有数据，队头指针 = 队尾指针
  • 满队：队列中存满了数据，队尾指针 + 1 = 队头指针

循环队列

1、基本内容

循环队列是以数组形式构成的队列数据结构。

循环队列的结构体如下：

typedef int data_t; //队列数据类型
#define N 64        //队列容量
typedef struct{data_t data[N]; //数据int front;      //队头位置,代表将要出队的位置int rear;       //队尾位置,代表将要入队的位置
}sequeue_t;

入队与出队示意图： 

 在循环队列中，fornt代表将要出队的位置，rear代表将要入队的位置。

  • 空队：当fornt = rear时，代表将要出队的地方还没有入队数据，因此整个队列为空。
  • 入队：当想要入队时，只需要向rear的位置填入数据即可入队，入队之后应该rear++，让rear指向下一个入队的位置。
  • 出队：当想要出队时，只需要从fornt的位置获取数据即可出队，出队之后应该fornt++，让fornt指向下一个要出队的位置。
  • 满队：当rear+1 = front时，代表已经满队(这里省略了%限定范围)
  • fornt与rear指向空间问题：在循环队列中，满队时会有一个冗余空间不能使用。

循环队列代码的文件构成：

  • sequeue.h：数据结构的定义、运算函数接口
  • sequeue.c：运算函数接口的实现
  • test.c：使用数据结构实现的应用功能代码

循环队列相关函数： 

  • 创建：sequeue* queue_create(void);
  • 删除：int queue_del(sequeue** pQueue); 
  • 入队列：int enter_queue(sequeue* pQueue,data_t value);
  • 出队列：int out_queue(sequeue* pQueue,data_t* value);

2、功能实现 

2.1 创建

创建循环队列就是申请空间，并让入队位置与出队位置相等，这代表队列为空。

具体代码实现如下：

/** queue_create:创建队列* @ret  NULL--err  other--空队列指针* */
sequeue* queue_create(void){sequeue* pQueue = NULL;//1.申请空间pQueue = (sequeue*)malloc(sizeof(sequeue));if(pQueue == NULL){printf("malloc err\n");return NULL;}//2.初始化,front = rear代表空队列memset(pQueue->data,0,N*sizeof(data_t));pQueue->front = 0;pQueue->rear = 0;return pQueue;
}

2.2 删除

删除就是释放申请的空间即可。

具体代码实现如下：

/** queue_del:销毁队列* param pQueue:要销毁的队列* @ret  -1--err  0--success* */
int queue_del(sequeue** pQueue){//1.判断参数有效性if(*pQueue == NULL){printf("pQueue is NULL\n");return -1;}free(*pQueue);*pQueue = NULL;return 0;
}

2.3 入队列

入队列的示意图如 "1、基本内容" 中所示，只需要在rear处填入数据并把rear进行偏移即可。

注意：入队列时，需要判断队列是否已满

具体代码实现如下：

/** enter_queue:入队列* param pQueue:要入哪一个队列* param value:要入队的数据* @ret  -1--err  0--success* */
int enter_queue(sequeue* pQueue,data_t value){//1.判断参数有效性if(pQueue == NULL){printf("pQueue is NULL\n");return -1;}//2.判断队列是否已满if( ((pQueue->rear+1)%N) == pQueue->front ){printf("queue is full\n");return -1;}//3.入队列,就是在rear出写入数据pQueue->data[pQueue->rear] = value;pQueue->rear = (pQueue->rear+1)%N;return 0;
}

2.4 出队列

出队列的示意图如 "1、基本内容" 中所示，只需要在front处取出数据并把front进行偏移即可。

注意：出队列时，需要判断队列是否为空

具体代码实现如下：

/** out_queue:出队列* param pQueue:要出哪一个队列的数据* param value:要出队的数据存放的位置* @ret  -1--err  0--success* */
int out_queue(sequeue* pQueue,data_t* value){//1.判断参数有效性if(pQueue == NULL){printf("pQueue is NULL\n");return -1;}//2.判断队列是否为空if(pQueue->front == pQueue->rear){printf("queue is empty\n");return -1;}//3.出队列,就是从front处读数据*value = pQueue->data[pQueue->front];pQueue->front = (pQueue->front+1)%N;return 0;
}

链式队列

1、基本内容

链式队列是以链表形式构成的队列数据结构。

链式队列的结构体如下：

typedef int data_t;
//链表
typedef struct node{data_t data;struct node* pNext;
}listnode,*linklist;
//队列
typedef struct{linklist front;//始终指向冗余的头linklist reat; //始终指向入队的位置,新数据接在rear后
}linkqueue;

入队与出队示意图： 

在链式队列中，fornt代表冗余的头，rear代表将要入队的位置。

  • 空队：当fornt、rear都指向冗余节点时，代表没有数据，即为空队
  • 入队：当想要入队时，只需要将数据链接到rear的位置之后即可。
  • 出队：当想要出队时，只需要把front后一个数据释放即可，当释放后为空时，需要将rear指向冗余的头。

链式队列代码的文件构成：

  • linkqueue.h：数据结构的定义、运算函数接口
  • linkqueue.c：运算函数接口的实现
  • test.c：使用数据结构实现的应用功能代码

链式队列相关函数： 

  • 创建：linkqueue* queue_create(void);
  • 删除：int queue_delete(linkqueue** pQueue);
  • 入队列：int enter_queue(linkqueue* pQueue,data_t value);
  • 出队列：int out_queue(linkqueue* pQueue,data_t* value)

2、功能实现

2.1 创建

创建链式队列，需要申请两个空间：冗余的头和队列。初始化时需要把front、rear指向冗余的头，代表这个队列为空队。

具体代码实现如下：

/** queue_create:创建一个空队列* @ret  NULL--err  other--空队列指针* */
linkqueue* queue_create(void){linkqueue* pQueue = NULL;linklist pLink = NULL;//1.申请空间//1.1 队列空间pQueue = (linkqueue*)malloc(sizeof(linkqueue));if(pQueue == NULL){printf("pQueue malloc err\n");return NULL;}//1.2 单链表空间pLink = (linklist)malloc(sizeof(listnode));if(pLink == NULL){printf("pLink malloc err\n");free(pQueue);//释放前面申请的空间return NULL;}//2.初始化pLink->data = 0;pLink->pNext = NULL;pQueue->front = pLink;pQueue->rear = pLink;return pQueue;
}

2.2 删除

删除链式队列，首先需要释放单链表的空间，之后再释放队列的空间。

具体代码实现如下：

/** queue_delete:删除整个队列* param pQueue:队列地址* @ret  -1--err  0--success* */
int queue_delete(linkqueue** pQueue){linklist pTmp = NULL;//1.判断参数有效性if(*pQueue == NULL){printf("pQueue is NULL\n");return -1;}//2.开始释放链表while((*pQueue)->front != NULL){pTmp = (*pQueue)->front;(*pQueue)->front = (*pQueue)->front->pNext;free(pTmp);}//3.释放队列free(*pQueue);*pQueue = NULL;return 0;
}

2.3 入队列

入队列的示意图如 "1、基本内容" 中所示，只需要将新数据链接到rear后即可，之后rear需要指向新数据。

具体代码实现如下：

/** enter_queue:入队列* param pQueue:队列地址* param value:入队数据* @ret  -1--err  0--success* */
int enter_queue(linkqueue* pQueue,data_t value){linklist pLink = NULL;//1.判断参数有效性if(pQueue == NULL){printf("pQueue is NULL\n");return -1;}//2.创建链表结点pLink = (linklist)malloc(sizeof(listnode));if(pLink == NULL){printf("malloc err\n");return -1;}pLink->data = value;pLink->pNext = NULL;//3.入队列//rear后链接新结点pQueue->rear->pNext = pLink;//队列指针偏移pQueue->rear = pLink;return 0;
}

2.4 出队列

出队列的示意图如 "1、基本内容" 中所示，需要将front后一个数据进行释放，并连接上剩余的数据。

注意点1：当出队列后，队列为空队，这时需要将rear指向冗余的头

注意点2：出队列之前需要先判断队列是否为空

注意点3：出队之后，需要释放出队元素的空间

具体的代码实现如下：

/** out_queue:出队列* param pQueue:队列地址* param value:出队数据存放的地址* @ret  -1--err  0--success* */
int out_queue(linkqueue* pQueue,data_t* value){linklist pTmp = NULL;//1.判断参数有效性if(pQueue == NULL){printf("pQueue is NULL\n");return -1;}//2.判断是否为空队列if(pQueue->front == pQueue->rear){printf("queue is empty\n");return -1;}//3.保存剩余数据pTmp = pQueue->front->pNext->pNext;//4.出队后队列为空时，需将rear指向冗余头部代表空队列if(pQueue->front->pNext == pQueue->rear){pQueue->rear = pQueue->front;}//5.开始出队列*value = pQueue->front->pNext->data;free(pQueue->front->pNext);pQueue->front->pNext = pTmp;return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

劳特巴赫ICD调试器CMM调用烧录框架固件研究之C语言版本

劳特巴赫ICD调试器CMM调用烧录框架固件研究之C语言版本

接到客户一个项目是基本GD32F301C8XX的，尝试用手上的劳特巴赫仿真器对它进行开发操作，发现总是提示“FLASH algorithm did not execute completely” 怀疑是底层调用用烧录固件“~~/demo/arm/flash/word/stm32f300.bin”与芯片不兼容造成的，于是有了这编研究文档，多的不说直…
阅读更多...
Spring4-IoC2-基于注解管理bean

Spring4-IoC2-基于注解管理bean

目录 开启组件扫描 使用注解定义bean Autowired注入 场景一：属性注入 场景二：set注入 场景三：构造方法注入 场景四：形参注入 场景五：只有一个构造函数，无注解 场景六：Autowired和Quali…
阅读更多...
Tcl lnit error: Can’t find a usable init.tcl in the following directories 问题解决

Tcl lnit error: Can’t find a usable init.tcl in the following directories 问题解决

这个问题出现在我用py2exe打包了一个包含tkinter的图形化界面，在当前电脑上运行无问题，在移动到新电脑上后提示报错、 这里吐槽一下，新电脑上报错信息一闪而过，我用的土法子解决的，就是录视频然后0.25倍速度暂定找到报…
阅读更多...
Acrobat 9 安装教程

Acrobat 9 安装教程

软件介绍 Adobe Acrobat 是由Adobe公司开发的一款PDF（Portable Document Format，便携式文档格式）编辑软件。借助它，可以以PDF格式制作和保存文档，以便于浏览和打印，同时还可以使用一些高级工具来创建、编辑…
阅读更多...
Qt 菜单栏、工具栏、状态栏、标签、铆接部件(浮动窗口) 设置窗口核心部件(文本编辑控件)的基本使用

Qt 菜单栏、工具栏、状态栏、标签、铆接部件(浮动窗口) 设置窗口核心部件(文本编辑控件)的基本使用

效果 代码 #include "mainwindow.h" #include "ui_mainwindow.h" #include<QToolBar> #include<QDebug> #include<QPushButton> #include<QStatusBar> #include<QLabel> #include<QDockWidget> #include<QTextEdi…
阅读更多...
将事物分为三教九流？不妨通过logistic回归

将事物分为三教九流？不妨通过logistic回归

和多元线性回归一样&#xff0c;逻辑回归也是建立“多对一”型变量之间的线性关系——也即找出线性方程的近似解。有所不同的是&#xff0c;逻辑回归的解只能出现0~1之间&#xff08;亦或就是0/1两种结果&#xff09;&#xff0c;这倒是有点像bool型和int型之间的区别了。实际上…
阅读更多...
S32K3 工具篇7：如何使用VScode编译EB MCAL工程

S32K3 工具篇7：如何使用VScode编译EB MCAL工程

S32K3 工具篇7&#xff1a;如何使用VScode编译EB MCAL工程 1. VScode工具与配置2. 使用VScode编译RTD MCAL工程2.1 使用EB tresos生成配置2.2 VScode 打开工程2.3 修改mk文件2.4 编译文件2.5 debug生成好的elf文件 对于EB配置的MCAL代码&#xff0c;通常是基于RTD去做&#xff…
阅读更多...
GEO IGEO MEO介绍 和 北斗导航系统使用三轨道原因

GEO IGEO MEO介绍 和 北斗导航系统使用三轨道原因

GEO IGSO MEO基本轨道知识 中地球轨道&#xff08;MEO&#xff1a;Middle Earth Orbit&#xff09; 轨道高度2000-36000kmGPS、GLONASS都属于此类轨道 地球同步轨道&#xff08;或称对地静止轨道&#xff09;[同步转动] 轨道高度约为36000 km&#xff1b;此轨道上卫星运行方…
阅读更多...
情感识别系统源码分享

情感识别系统源码分享

情感识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vision …
阅读更多...
发工资-python

发工资-python

题目要求&#xff1a; 代码&#xff1a; import random from random import randintmoney 10000 for i in range(1, 21):performance randint(1, 10)if performance < 5:print(f"员工{i},绩效分{performance},低于5,不发工资&#xff0c;下一位")continueif m…
阅读更多...
每日学习一个数据结构-倒排表

每日学习一个数据结构-倒排表

文章目录 示意图倒排表的基本概念倒排表的数据结构示例 倒排表的优点应用场景 倒排表&#xff08;Inverted Index&#xff09;&#xff0c;也称为反向索引或倒排文件&#xff0c;在信息检索系统中是一种重要的数据结构。它主要用于快速搜索文档中的关键词&#xff0c;并找到包含…
阅读更多...
字典+泛型的栈与队列+委托

字典+泛型的栈与队列+委托

字典 在System.Collections.Generic下&#xff0c;对应HashTable,添加了泛型的特性&#xff0c;性能更高更安全&#xff0c;在内存中散列排布&#xff0c;存储也是键值对。 Dictionary<键的数据类型&#xff0c;值的数据类型> 字典名new Dictionary<键的数据类型&am…
阅读更多...
异常冲突行为和危险识别系统源码分享

异常冲突行为和危险识别系统源码分享

异常冲突行为和危险识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Co…
阅读更多...
教你搭建一个wifi贴系统

教你搭建一个wifi贴系统

大家好&#xff0c;我是鲸天科技千千&#xff0c;大家都知道我是做小程序开发的&#xff0c;平时会给大家分享一些互联网相关的创业项目&#xff0c;感兴趣的可以跟我关注一下。 搭建一个首先就是要搭建一个自己的wifi贴小程序&#xff0c;我们自己的工作就是把这个小程序推广…
阅读更多...
CAN BUS

CAN BUS

CAN BUS 原理 网上资料非常丰富&#xff0c;是车载系统主要BUS之一。 我们关注如下方面 can bus 是什么网络结构CAN BUS 协议ECU node实现其他 What is CAN Bus? Control Area Network (CAN) bus is a serial communication protocol that allows devices to exchange dat…
阅读更多...
JavaScript web API part3

JavaScript web API part3

web API DOM 日期对象 > 得到当前系统的时间 new这个操作就是实例化 语法 const date new Date() or const date new Date(2004-11-3 08:00:00) 可以指定时间 > 可应用于通过系统时间和指定时间实现倒计时的操作 //得到当前时间const date new Date()console.lo…
阅读更多...
HTML贪吃蛇游戏

HTML贪吃蛇游戏

文章目录 贪吃蛇游戏 运行效果代码 贪吃蛇游戏 贪吃蛇是一款经典的休闲益智游戏。本文将通过HTML5和JavaScript详细解析如何实现一个简易版的贪吃蛇游戏。游戏的主要逻辑包括蛇的移动、碰撞检测、食物生成等功能。以下是游戏的完整代码及注释解析。&#xff08;纯属好玩&#…
阅读更多...
【PyQt6 应用程序】应用程序携带数据源文件一并打包

【PyQt6 应用程序】应用程序携带数据源文件一并打包

在开发好应用程序打包之后给到其他用户会发现数据文件比如封面图片不见了。 例如这样，很影响用户使用。 这里介绍一个非常简单的打包方法，不光要在打包命令的时候添加对应数据文件，在源码中也要进行一些简单的修改。 修改需要添加打包文件的地方。首先需要添加一个绝对路径…
阅读更多...
九九乘法表-while-python

九九乘法表-while-python

i 1 while i < 9:#j 1&#xff0c;条件为j < ij 1while j < i:print(f"{j}*{i}{i*j}\t",end)#先输出jj 1print()i 1运行结果截图&#xff1a;
阅读更多...
超分辨率技术之插值算法

超分辨率技术之插值算法

&#x1f31e;欢迎莅临我的个人主页&#x1f448;&#x1f3fb;这里是我专注于深度学习领域、用心分享知识精粹与智慧火花的独特角落&#xff01;&#x1f349; &#x1f308;如果大家喜欢文章&#xff0c;欢迎&#xff1a;关注&#x1f377;点赞&#x1f44d;&#x1f3fb;评论…
阅读更多...
最新文章

Copyright @ 2022~2023