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

4.C_数据结构_队列

news 来源：原创 2024/9/19 17:10:54

概述

什么是队列：

队列是限定在两端进行插入操作和删除操作的线性表。具有先入先出(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;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 用Java实现人工智能
  • Selenium实现滑动滑块验证码验证！
  • 龙蜥8.9系统hadoop3.3.6上spark3.5.2安装(伪分布)
  • 在RabbitMQ中四种常见的消息路由模式
  • Red Hat 和 Debian Linux 对比
  • 小程序体验版无法正常请求接口，开启 调试可以正常请求
  • 本地不能訪問linux的kafka服務
  • 大模型教程：使用 Milvus、vLLM 和 Llama 3.1 搭建 RAG 应用
  • this 指向
  • vmware中的ubuntu系统扩容分区
  • uniapp如何实现图片轮播特效？
  • 全面掌握 Jest：从零开始的测试指南（下篇）
  • 【python】OpenCV—Mask RCNN for Object Detection and Instance Segmentation
  • 移动音乐厅：灵活与高效的音乐盛宴空间—轻空间
  • 十七，Spring Boot 整合 MyBatis 的详细步骤(两种方式)
  • AzureCon上微软宣布了哪些容器相关的重磅消息
  • cookie和session
  • Essential Studio for ASP.NET Web Forms 2017 v2，新增自定义树形网格工具栏
  • JAVA 学习IO流
  • Object.assign方法不能实现深复制
  • passportjs 源码分析
  • React as a UI Runtime(五、列表)
  • spring security oauth2 password授权模式
  • vue-router的history模式发布配置
  • 搭建gitbook 和 访问权限认证
  • 订阅Forge Viewer所有的事件
  • 基于axios的vue插件，让http请求更简单
  • 理解 C# 泛型接口中的协变与逆变（抗变）
  • 前端之React实战：创建跨平台的项目架构
  • 前端自动化解决方案
  • 日剧·日综资源集合（建议收藏）
  • 扫描识别控件Dynamic Web TWAIN v12.2发布，改进SSL证书
  • 手写双向链表LinkedList的几个常用功能
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 小程序滚动组件，左边导航栏与右边内容联动效果实现
  • 写代码的正确姿势
  • 新手搭建网站的主要流程
  • 在GitHub多个账号上使用不同的SSH的配置方法
  • Hibernate主键生成策略及选择
  • 选择阿里云数据库HBase版十大理由
  • ​二进制运算符：（与运算）、|（或运算）、~（取反运算）、^（异或运算）、位移运算符​
  • ###51单片机学习（2）-----如何通过C语言运用延时函数设计LED流水灯
  • $(document).ready(function(){}), $().ready(function(){})和$(function(){})三者区别
  • $nextTick的使用场景介绍
  • ( 10 )MySQL中的外键
  • （~_~)
  • （+4）2.2UML建模图
  • （06）金属布线——为半导体注入生命的连接
  • （2）STL算法之元素计数
  • (el-Transfer)操作(不使用 ts)：Element-plus 中 Select 组件动态设置 options 值需求的解决过程
  • （JSP）EL——优化登录界面，获取对象，获取数据
  • （react踩过的坑）Antd Select（设置了labelInValue）在FormItem中initialValue的问题
  • (读书笔记)Javascript高级程序设计---ECMAScript基础
  • （推荐）叮当——中文语音对话机器人
  • （转）3D模板阴影原理