数据结构—队列（C语言实现）

文章目录

  • 前言
  • 一、队列的概念
  • 二、队列的实现
    • Queue.h
    • Queue.c
  • 三、设计循环队列问题
    • 数组实现
    • 链表实现
  • 总结

前言

嗨喽喽！！小伙伴们，大家好哇，欢迎来到我的博客！
在这里插入图片描述

今天将要分享的是另一种数据结构—队列，以及与队列具有相通之处的一种结构，循环队列的实现。

一、队列的概念

队列（Queue）：只能在一端进行插入数据操作，在另一端进行删除数据的特殊线性表。与栈相反的是，队列遵循先进先出 FIFO(First In First Out)的原则，进行插入数据的一端称之为队尾（入队），进行删除数据的一端则为队头（出队）。
在这里插入图片描述
看到队列这一数据结构的名字与以上对于队列的概念的说明，相信小伙伴们脑海中早已浮现日常生活中与此结构相类似的场景。就是我们平时购买物品或办理业务时，通常会采取排队的方式确保秩序与公平，先入队的人先出队。
在这里插入图片描述

二、队列的实现

讲述完了队列的相关概念，接下来便可以着手实现队列及其有关的基本操作了！！
队列既可以使用数组也可以使用链表来实现。但是总体来说，使用链表实现更优，因为使用数组在队头出数据，其效率会低很多。

所以我们使用链表来实现一个队列：

Queue.h

首先时队列头文件的头文件包含与链表和队列的声明：

typedef int QDataType;

typedef struct QListNode
{
	struct QListNode* _pNext;//指向队列的下一个
	QDataType _data;
}QNode;

typedef struct Queue
{
	QNode* _front;//指向队头
	QNode* _rear;//指向队尾
	int _size;
}Queue;

然后是，队列中的一些相关的方法的声明：

//初始化队列
void QueueInit(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);

//入队(队尾)
void QueuePush(Queue* q, QDataType x);
//出队(队头)
void QueuePop(Queue* q);

//获取队头元素
QDataType QueueFront(Queue* q);
//获取队尾元素
QDataType QueueBack(Queue* q);

//队列判空
bool QueueEmpty(Queue* q);
//获取队列元素个数
int QueueSize(Queue* q);

Queue.c

接下来便是队列中的一些方法的实现：
首先是队列的初始化与销毁，销毁操作类似于链表，通过遍历对节点逐个释放：

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
	q->_size = 0;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* pcur, * next;
	pcur = q->_front;
	while (pcur)
	{
		next = pcur->_pNext;
		free(pcur);
		pcur = next;
	}
	q->_front = q->_rear = NULL;
	q->_size = 0;
}

然后是队列的入队操作，在入队之前需要先检查队列是否为空：

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* node = (QNode*)malloc(sizeof(QNode));
	if (node == NULL)
	{
		perror("malloc fail！");
		exit(1);
	}
	node->_data = x;
	node->_pNext = NULL;
	if (q->_rear)//队列不为空
	{
		q->_rear->_pNext = node;
	}
	else//队列为空
	{
		q->_front = node;
	}
	q->_rear = node;
	q->_size++;
}

使用动画解释入队操作：
在这里插入图片描述
然后是出队操作，此处则存在队列为一个元素与多个元素的情况：

void QueuePop(Queue* q)
{
	assert(q && q->_size);
	if (q->_front->_pNext)//队列不仅一个元素
	{
		QNode* next = q->_front->_pNext;
		free(q->_front);
		q->_front = NULL;
		q->_front = next;
	}
	else//队列仅一个元素
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	q->_size--;
}

使用动画解释出队操作：
在这里插入图片描述
然后是获取队头与队尾元素：

QDataType QueueFront(Queue* q)
{
	assert(q && q->_front);
	return q->_front->_data;
}

QDataType QueueBack(Queue* q)
{
	assert(q && q->_rear);
	return q->_rear->_data;
}

最后则是队列的判空与获取当前队列的大小的操作：

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->_size == 0;
}

int QueueSize(Queue* q)
{
	assert(q);
	return q->_size;
}

三、设计循环队列问题

分享完了队列的相关内容，接下来让我们看一个与队列有一定相通之处的设计循环队列的问题。
首先给出力扣上的相关题目的链接：【设计循环队列】。
在这里插入图片描述
当然，这个循环队列既可以使用数组也可以使用链表来实现，由于难度基本相差不大。这边主要使用数组来讲解实现过程，同时在最后也会给出使用链表实现的相关代码。

数组实现

首先通过题目我们可以知道循环队列的逻辑结构大致类似于下图：
在这里插入图片描述
但是他的物理结构上确实一个数组，不可能将首尾相接。那么这里我们便可以通过对tail用size取模。当tail在数组末尾时再加一，那么肯定会造成数组越界，此时我们就可以使用size对tail进行取模，tail便成了0，指向了数组首位，如此便形成了循环，当然队头也可以使用相类似的操作。如下图所示，tail开始为5，size为6，此时队列入数据，对tail加1，我们对tail取模，tail就等于了0：
在这里插入图片描述
但此时，我们会存在两种特殊情况，那便是数组的空与满。数组为空还可以放入元素，为满那肯定不可以再存入元素。这时，可能部分小伙伴会说，判断此时队头与队尾指向的位置是否相同，来区分空与满。但要知道的是空与满时队头与队尾指向的位置其实都是相同的。

其实此时我们可以采取两种方法来解决上述的问题：
1、使用一个size来记录当前的数组元素的个数，当元素的个数与循环队列的长度k相等时，不就为满了，size==0不就为空了。

2、我们可以实际上创建k+1个长度循环队列，然后让tail一直指向末尾元素的下一个下标的位置，即让数组中始终有一个位置不存放数据。此时队头与队尾指向同一个位置时，即为空；队尾的下一个为队头就为满:
在这里插入图片描述

那我们就使用第一种方法来手撕一个循环队列吧！！
首先是循环队列的声明：

typedef struct {
    int* a;
    int head;
    int tail;
    int size;//判断满与空的特殊情况
    int k;
} MyCircularQueue;

然后是循环队列的初始化，一开始头与尾都指向数组的开始位置：

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pcq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pcq->a = (int*)malloc(k * sizeof(int));
    pcq->size = pcq->head = pcq->tail = 0;
    pcq->k = k;
    return pcq;
}

循环队列的入队操作，入队之前需要先判断队列是否为满，即size与k相等时即为满，然后在对tial加加了之后，则需要使用k对tail取模，形成循环：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->size == obj->k)//循环队列为满
    {
        return false;
    }
    obj->a[obj->tail] = value;
    obj->tail++;
    obj->tail %= obj->k;
    obj->size++;
    return true;
}

循环队列的出队操作，出队之前则需要判断队列是否为空（即size==0），不为空，就直接让head++。同样的，在对head++后也需要使用k对head进行取模操作：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->size == 0)//循环队列为空
    {
        return false;
    }
    obj->head++;
    obj->head %= obj->k;
    obj->size--;
    return true;
}

然后是循环队列的取队头数据的操作，直接返回head指向的数据即可：

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->size == 0)
        return -1;
    return obj->a[obj->head];
}

取循环队列的尾数据就相对复杂了，因为tail的前一个元素为尾元素。那么，当tail==0时，尾元素在数组的末尾位置。当然，有一种简单的解决方法：使用三目运算符，即判断tail是否指向0，是就返回数组末尾元素（即k - 1的位置），否就只返回tail - 1指向的元素即可。
此处同时还有一种更为🐂🍺（NB）的写法，就是返回使用k对tail取模位置的元素。即让tail - 1 + k在使用k对结果进行取模操作，此时的值便指向了循环队列的末尾元素。比如tail为0时，减1加k再用k取模，值为k - 1：

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->size == 0)
        return -1;
    return obj->tail == 0 ? obj->a[obj->k - 1] : obj->a[obj->tail - 1];
    //return obj->a[(obj->tail - 1 + obj->k) % obj->k];//更装逼的写法
}

接下来就是循环队列的判空与判满操作，非常简单，就不加赘述：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size == obj->k;
}

最后则是循环队列的销毁操作：

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a = NULL;
    obj->size = obj->k = obj->head = obj->tail = 0;
    free(obj);
}

代码写完，直接提交完事：
在这里插入图片描述

链表实现

最后再给出使用链表实现循环队列，并采用对循环队列多创建一个位置的方法进行判断循环队列的空与满的代码。

使用链表是实现就不需要取模来让队列循环了，只需要让链表的首节点与尾节点相连接形成循环链表即可。基本实现逻辑大致相同，就是判空与判满操作存在不同，这里直接上代码：

typedef struct LTNode
{
    int x;
    struct LTNode* next;
}LTNode;

//用链表实现
typedef struct {
    LTNode* phead;
    LTNode* ptail;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->phead = (LTNode*)malloc(sizeof(LTNode));
    obj->ptail = obj->phead;
    for (int i = 0; i < k; i++)//多创建一个节点判断空与满的情况
    {
        obj->ptail->next = (LTNode*)malloc(sizeof(LTNode));
        obj->ptail = obj->ptail->next;
    }
    obj->ptail->next = obj->phead;
    obj->ptail = obj->phead;
    obj->k = k + 1;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	//循环队列头节点与尾节点相同时，队列为空
    return obj->phead == obj->ptail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	//循环队列尾节点的下一个节点为头节点时，队列为满
    return obj->ptail->next == obj->phead;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;
    obj->ptail->x = value;
    obj->ptail = obj->ptail->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->phead = obj->phead->next;
    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    LTNode* tail = obj->phead;
    while (tail->next != obj->ptail)
        tail = tail->next;
    return tail->x;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    LTNode* pcur = obj->phead;
    for (int i = 0; i < obj->k; i++)
    {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = NULL;
        pcur = next;
    }
    free(obj);
}

最后提交走人：
在这里插入图片描述

总结

以上便是有关队列的相关知识的分享。如果，小伙伴们觉得有帮助的话，点个赞是最好的！ο(=•ω＜=)ρ⌒☆

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

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

相关文章

迈向F5G-A，开启全光万兆新时代——南通移动完成全市首个50G-PON技术验证

迈向F5G-A，开启全光万兆新时代——南通移动完成全市首个50G-PON技术验证

近日&#xff0c;南通移动在崇川区完成全市首个50G-PON万兆技术现网验证&#xff0c;标志着南通成为首批具备F5G-A(The 5th GenerationFixed Network-advanced)的万兆光网城市&#xff0c;使其成为网速最快、覆盖最全、时延最低的城市之一。 作为全光万兆的关键技术&#xff0c…
阅读更多...
1天搞定SpringBoot+Vue全栈开发 (9)JWT跨域认证

1天搞定SpringBoot+Vue全栈开发 (9)JWT跨域认证

1.Session认证 2.Token认证 3.JWT的使用
阅读更多...
计算机图形学入门01：概述

计算机图形学入门01：概述

1.什么是图形学? The use of computers to synthesize and manipulate visual information. 图形学是合成和操纵视觉信息的计算机应用。 百度百科&#xff1a;计算机图形学(Computer Graphics&#xff0c;简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格…
阅读更多...
深入解析MySQL 8中的角色与用户管理

深入解析MySQL 8中的角色与用户管理

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 &#x1f38f;&#xff1a;你只管努力&#xff0c;剩下的交给时间 &#x1f3e0; &#xff1a;小破站 深入解析MySQL 8中的角色与用户管理 前言角色和用户的基础概念用户&#xff08;User&#xff09;…
阅读更多...
一个基于预训练的DenseNet121模型的人脸年龄分类系统

一个基于预训练的DenseNet121模型的人脸年龄分类系统

这篇文章采用预训练的DenseNet121模型并使用自定义的数据集类和自定义的类似正态分布的标签平滑策略来训练了一个人脸年龄分类模型&#xff0c;最后基于这个模型用tk实现了一个娱乐向的小系统。 数据集展示&#xff1a; 两个文件夹&#xff0c;分别是训练集和测试集&#xff0…
阅读更多...
光伏组件积灰检测系统

光伏组件积灰检测系统

光伏组件积灰检测系统是一种专门用于监测光伏组件表面灰尘积累情况的设备。以下是关于该系统的详细信息和特点&#xff1a; 系统概述 光伏组件积灰检测系统安装在光伏板的框架上&#xff0c;通过实时监测光伏组件表面的灰尘厚度、分布情况和清洁度&#xff0c;为运维人员提供…
阅读更多...
深入分析 Android Activity (五)

深入分析 Android Activity (五)

文章目录 深入分析 Android Activity (五)1. Activity 的进程和线程模型1.1 主线程与 UI 操作1.2 使用 AsyncTask1.3 使用 Handler 和 Looper 2. Activity 的内存优化2.1 避免内存泄漏2.2 使用内存分析工具2.3 优化 Bitmap 使用 3. Activity 的跨进程通信&#xff08;IPC&#…
阅读更多...
如何修改WordPress网站的域名

如何修改WordPress网站的域名

我的网站用的是Hostease的虚拟主机&#xff0c;但是域名是之前在其他平台买的&#xff0c;而且已经快到期了&#xff0c;因为主机和域名在不同的平台上&#xff0c;管理不太方便&#xff0c;所以我又在Hostease重新注册了一个域名&#xff0c;然后把网站换成了新的域名&#xf…
阅读更多...
配置环境变量

配置环境变量

配置环境变量$(xxxx)&#xff0c;代表宏 32位操作系统&#xff0c;请自觉将文中路径中所有的x64换成x86。 %符号表示引用系统环境变量或用户自定义的环境变量 如果你想将某个文件夹添加到Visual Studio的路径中&#xff0c;你可以在环境变量中添加%FolderName%&#xff0c;其…
阅读更多...
java项目之高校教师科研管理系统源码(springboot+vue+mysql)

java项目之高校教师科研管理系统源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的高校教师科研管理系统源码。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 高校教师科研管…
阅读更多...
关于python中屏蔽输出

关于python中屏蔽输出

python中屏蔽输出包含屏蔽标准输出&#xff08;比如打印出来的内容&#xff09;、屏蔽标准错误&#xff08;错误信息&#xff09;还有屏蔽logging信息等。 屏蔽标准输出 import contextlib import oswith open(os.devnull, "w") as devnull:with contextlib.redire…
阅读更多...
100个 Unity小游戏系列四 -Unity 抽奖游戏专题二 水果机游戏

100个 Unity小游戏系列四 -Unity 抽奖游戏专题二 水果机游戏

一、演示效果 二、知识点 2.1 布局 private void CreateItems(){for (int i 0; i < rewardDatas.Length; i){var reward_data rewardDatas[i];GameObject fruitOjb;if (i < itemRoot.childCount){fruitOjb itemRoot.GetChild(i).gameObject;}else{fruitOjb Instant…
阅读更多...
大屏表格实现无限滚动效果

大屏表格实现无限滚动效果

实现效果 实现思路 首先固定最外层的高度&#xff0c;并且设置超出高度后隐藏设置每一行的高度为固定35PX&#xff0c;默认显示10行&#xff0c;所以最外层高度就是 35 * 10 表头的高度遍历时克隆一份表格数据&#xff0c;用于视差效果显示设置滚动动画&#xff0c;让表格行所…
阅读更多...
VMware vSphere Distributed Services Engine 和利用 DPU 实现网络加速

VMware vSphere Distributed Services Engine 和利用 DPU 实现网络加速

VMware相关学习专栏&#xff1a;虚拟化技术 vSphere 8.0 通过加速数据处理单元 (DPU) 上的网络功能实现了突破性的工作负载性能。 vSphere 8.0 通过加速 DPU 上的网络功能实现了突破性工作负载性能&#xff0c;从而满足现代分布式工作负载的吞吐量和延迟需求。借助 vSphere Dis…
阅读更多...
GIGE 协议摘录

GIGE 协议摘录

系列文章目录 GIGE 学习笔记 GIGE 协议摘录 文章目录 系列文章目录引言第 1 章 设备发现1.1 链路选择1.1.1 单链路配置1.1.2 多链路配置1.1.3 链路聚合组配置 LAG 1.2 IP配置1.2.1 协议选择1.2.2 静态IP1.2.3 DHCP1.2.4 链接本地地址 LLA 1.3 设备枚举1.3.1 GVCP设备发现 引言 …
阅读更多...
4个月赚20万！一张图赚7500！多种变现方式，一个被忽视的暴力项目

4个月赚20万！一张图赚7500！多种变现方式，一个被忽视的暴力项目

大家好&#xff0c;今天给大家带来一个被很多人忽视&#xff0c;不起眼确很暴力的项目。 大胆放心干 课程获取&#xff1a; https://hsgww.com/https://hsgww.com/
阅读更多...
停车场变综合楼，结构分析助力低碳设计

停车场变综合楼，结构分析助力低碳设计

PLAXIS 和 RAM 助力确定更有效的结构设计并大幅降低施工成本 总部和周边区域 桑坦德银行位于英国的新总部将现有的四个英国办事处合并到米尔顿凯恩斯的一个中心枢纽&#xff0c;位于伦敦以北 50 英里。 Unity Place 将作为桑坦德银行约 5,000 名员工的办公场所。该项目总投资 …
阅读更多...
SpringBoot——整合RabbitMQ收发消息

SpringBoot——整合RabbitMQ收发消息

目录 RabbitMQ消息队列 项目总结 新建一个SpringBoot项目 pom.xml application.properties配置文件 index.html前端页面 RabbitMQConfig配置类 RabbitMQProducer生产者 RabbitMQConsumer消费者 IndexController控制器 SpringbootRabbitmqApplication启动类 测试 Ra…
阅读更多...
Linux 删除SSH密钥(id_ed25519)，重新生成

Linux 删除SSH密钥(id_ed25519)，重新生成

在Linux系统中&#xff0c;重新生成SSH密钥&#xff08;比如id_ed25519&#xff09;的过程包括删除现有的密钥文件并生成一个新的。 以下是具体的步骤&#xff1a; 0. 查看下是否有密钥 1. 删除原有的id_ed25519密钥 默认情况下&#xff0c;SSH密钥存储在用户的主目录下的 .…
阅读更多...
【Pandas】深入解析`pd.read_sql()`函数

【Pandas】深入解析`pd.read_sql()`函数

【Pandas】深入解析pd.read_sql()函数 &#x1f308; 欢迎莅临我的个人主页&#x1f448;这里是我深耕Python编程、机器学习和自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;并乐于分享知识与经验的小天地&#xff01;&#x1f387; &#x1f393; 博主简介&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023