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

目录

1.概念与结构

2.队列的实现

初始化QueueInit

申请新节点BuyNode

入队QueuePush

判断队为空QueueEmpty

出队QueuePop

读取队头数据QueueFront

读取队尾数据QueueBack

元素个数QueueSize

销毁队列QueueDestroy

3.整体代码

(文章中结点和节点是同一个意思)

1.概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先 出FIFO(First In First Out)

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出列在数组头上出数据，需要将后面所有的元素整体向前移动一位，时间复杂度为o（n），效率会⽐较低，入队操作是单链表需要遍历整个链表找到尾结点，所以这里定义一个头结点和尾结点，来避免入队操作时间复杂度高。

2.队列的实现

创建三个文件，Queue.h,Queue.c,test.c，分别为头文件，函数实现文件，以及测试文件

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int DataType;

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

void QueueInit(Queue*pq);
// 销毁队列
void QueueDestroy(Queue * pq);

//入队列--队尾
void QueuePush(Queue* pq, DataType x);
//出队列--队头
void QueuePop(Queue* pq);

//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

这里很之前的一样，栈里存的元素。可以是各种数据类型，为了方便后续改成其他类型，这里重定义数据类型为SDataType，这里以int为例，定义结构体队列的节点，这里利用结构体的自引用，用来找到下一个结点，即next；以及队列的头结点，和尾结点，队列的元素个数；还有实现各种函数的申明。

初始化QueueInit

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

断言传的指针非空，头结点和尾结点置为空，元素个数为零。

申请新节点BuyNode

QueueNode* BuyNode(DataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

这里返回类型为结构体QueueNode*类型，利用malloc函数申请，申请成功后，再将结构体的data赋值为x，下一个结点，即next置为空。

入队QueuePush

void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QueueNode*newnode= BuyNode(x);
	if (pq->phead ==NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

断言传的指针非空，申请一个节点，判断队是否为空，如果为空直接将新的结点，赋给头结点和尾结点，如果不为空，则在尾结点后面插入，（很前面单链表尾插一样，只是这里已经有尾结点了，不需要遍历单链表），最后元素个数++；

判断队为空QueueEmpty

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead==NULL;
}

这里返回类型为bool型，断言传的指针非空，通过判断头结点是否为NULL，为空则队列中没有元素。

出队QueuePop

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;	
	}
	pq->size--;	
}

断言传的指针非空，以及判断队列非空，出队要考虑两种情况，如果队列中只有一个节点，即头结点和尾结点指向同一个，直接释放掉头结点，然后头结点和尾结点置为空就行了，如果不止一个节点，则删除头结点指向那个结点，头结点指向下一个结点，（和单链表的头插一模一样），最后元素个数——。

读取队头数据QueueFront

DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

断言传的指针非空，以及判断队列非空，直接返回头结点的data。

读取队尾数据QueueBack

DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

断言传的指针非空，以及判断队列非空，直接返回尾结点的data。

元素个数QueueSize

int QueueSize(Queue* pq)
{
    assert（pq）；
	return pq->size;
}

断言传的指针非空，直接返回结构体Queue中的size，即为队列元素个数。

销毁队列QueueDestroy

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

断言传的指针非空，定义一个指针指向头结点，遍历链表，依次删除（这里和前面的单链表销毁的函数也是一模一样），最后将头结点，和尾结点都置为空，元素个数置为0.

3.整体代码

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int DataType;

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

void QueueInit(Queue*pq);
// 销毁队列
void QueueDestroy(Queue * pq);

//入队列--队尾
void QueuePush(Queue* pq, DataType x);
//出队列--队头
void QueuePop(Queue* pq);

//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

QueueNode* BuyNode(DataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QueueNode*newnode= BuyNode(x);
	if (pq->phead ==NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;	
	}
	pq->size--;	
}

DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead==NULL;
}

int QueueSize(Queue* pq)
{
	return pq->size;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

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

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

相关文章

15. 软件接口

15. 软件接口

文章目录 第15章 软件接口15.1接口的概念多个接口操作、事件和属性接口演进 15.2 设计接口接口的范围交互方式交换数据的表示形式和结构可扩展标记语言&#xff08;XML&#xff09;JavaScript 对象表示法&#xff08;JSON&#xff09;Protocol Buffers 错误处理 15.3 接口文档…
阅读更多...
200元运动蓝牙耳机有哪些？爆款测评PK力荐！

200元运动蓝牙耳机有哪些？爆款测评PK力荐！

在运动场景下&#xff0c;传统的入耳式和半入耳式耳机虽然占据了大部分市场&#xff0c;但并不适合所有人&#xff0c;尤其是在长时间运动中佩戴时&#xff0c;耳道的压迫感往往会导致不适。而骨传导耳机虽然通过不塞入耳道的方式改善了佩戴舒适度&#xff0c;但在音质方面与入…
阅读更多...
[openvino]windows上配置C++openvino后测试代码

[openvino]windows上配置C++openvino后测试代码

测试环境&#xff1a; vs2022 w_openvino_toolkit_windows_2024.3.0.16041.1e3b88e4e3f_x86_64.zip 代码&#xff1a; #include <iostream>#include <openvino/openvino.hpp>int main(int, char**){// -------- Get OpenVINO runtime version --------std::cou…
阅读更多...
UG NX12.0建模入门笔记：1.2 鼠标的基本操作

UG NX12.0建模入门笔记：1.2 鼠标的基本操作

文章目录 前言&#xff1a;鼠标的操作1.鼠标左键&#xff1a;单击—>单选&#xff1b;长按并滑动—>框选。2.鼠标右键&#xff1a;在不同的地方单击弹出不同的菜单。3.鼠标中键&#xff1a;滚动中键—>放大缩小【镜头拉近拉远】。4.鼠标中键&#xff1a;摁住鼠标中键&…
阅读更多...
微信小程序考试系统(lw+演示+源码+运行）

微信小程序考试系统(lw+演示+源码+运行）

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了微信小程序考试系统的开发全过程。通过分析微信小程序考试系统管理的不足&#xff0c;创建了一个计算机管理微信小程序考试系统的方案。文章介绍了微信小程序考…
阅读更多...
鸿蒙开发：什么是ArkTS语言

鸿蒙开发：什么是ArkTS语言

ArkTS(也称为Ark TypeScript)是HarmonyOS的主力应用开发语言。面向万物互联时代&#xff0c;华为提出了“一次开发多端部署、可分可合自由流转、统一生态原生智能”三大应用与服务开发理念。针对多设备、多入口、服务可分可合等特性&#xff0c;华为提供了多种能力协助开发者降…
阅读更多...
从0开始Linux(14)——进程（5）进程空间地址（2）

从0开始Linux(14)——进程（5）进程空间地址（2）

欢迎来到博主的专栏&#xff1a;从0开始linux 博主ID:代码小豪 文章目录 关于页表程序权限加载状态 可执行程序分段 关于页表 在前一篇博客中博主提到&#xff0c;页表是链接虚拟地址(mm_struct)和物理地址&#xff08;存储器&#xff09;的中间商&#xff0c;其主要作用是映射…
阅读更多...
Jmeter之GET与POST 请求的参数存放位置

Jmeter之GET与POST 请求的参数存放位置

根据不用的请求方式&#xff0c;参数的设置详细如下&#xff0c;二选一&#xff0c;否则报错 POST请求 GET请求
阅读更多...
VMware中安装配置Ubuntu（2024最新版 超详细）

VMware中安装配置Ubuntu（2024最新版 超详细）

目录 一、安装虚拟机软件 二、VMware虚拟机 三、 Ubuntu 下载 &#xff08;1&#xff09;官网下载 &#xff08;2&#xff09;清华镜像网站下载 四、创建虚拟机 五、Ubuntu 系统安装过程的配置 六、更换国内镜像源 七、环境搭建完毕 全篇较长&#xff0c;请慢慢观看 一…
阅读更多...
ffmpeg视频滤镜:平均模糊

ffmpeg视频滤镜:平均模糊

滤镜简述 avgblur 官网链接> FFmpeg Filters Documentation 平均模糊滤镜会使视频变得模糊&#xff0c;模糊的程度可以通过参数进行控制。 模糊滤镜可以用于保密的场景&#xff0c;视频特效也会用到这个滤镜。 滤镜使用 参数 sizeX <int> .…
阅读更多...
AMS1117 -3.3稳压芯片管脚图以及典型电路

AMS1117 -3.3稳压芯片管脚图以及典型电路

AMS1117 是一个输出电流达到 1A 的三端输出低压差线性稳压器。 上面那个头不要接地&#xff0c;接了会有问题。 还有就是AMS1117不只是3.3V稳压的&#xff0c;还有5v的等&#xff0c;自己注意看左下角的数字。 如果是5就是5V&#xff1b;如果是33就是3.3V。 典型应用电路如下…
阅读更多...
基于springboot的网上服装商城推荐系统的设计与实现

基于springboot的网上服装商城推荐系统的设计与实现

基于springboot的网上服装商城推荐系统的设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;idea 源码获取&#xf…
阅读更多...
【AI大模型】本地部署 Code Llama 大模型

【AI大模型】本地部署 Code Llama 大模型

要在本地部署 Code Llama 大模型并结合 Text Generation Web UI 实现远程运行 LLM&#xff08;大语言模型&#xff09;&#xff0c;你需要完成以下几个步骤&#xff1a; 1. 准备环境 1.1 硬件和软件要求 硬件&#xff1a; GPU&#xff08;如 NVIDIA 及支持 CUDA 的显卡&#…
阅读更多...
内衣迷你洗衣机什么牌子好？内衣洗衣机2024年口碑指数排行榜推荐

内衣迷你洗衣机什么牌子好？内衣洗衣机2024年口碑指数排行榜推荐

内衣专用的洗衣机是一种专门设计用于洗涤内衣和贴身衣物的小型洗衣机。相比于普通的大型洗衣机&#xff0c;这样的小型洗衣机在设计和功能上有很大的区别。内衣专用的迷你洗衣机可以有效地保护内衣和贴身衣物的质量和卫生。在传统的洗衣机中&#xff0c;如果经常将内衣裤、袜子…
阅读更多...
RabbitMQ 中的交换机学习

RabbitMQ 中的交换机学习

RabbitMQ 中的交换机学习 一、直接交换机&#xff08;Direct Exchange&#xff09; 1. 介绍 Direct 交换机将消息路由到绑定了指定 Routing Key 的队列中。每条消息都有一个 Routing Key&#xff0c;当队列绑定到 Direct 交换机时&#xff0c;它需要一个指定的 Routing Key。…
阅读更多...
使用Python实现某易云音乐歌曲下载

使用Python实现某易云音乐歌曲下载

前言 在这篇文章中，我们将探讨如何通过Python结合JavaScript代码来逆向网易云音乐的API接口，以获取并下载指定歌曲。请注意，本文仅用于技术学习与交流目的，实际使用时请遵守相关法律法规及服务条款。 目标网站 1. 准备工作 首先，我们需要安装一些必要的库： execjs：用…
阅读更多...
揭秘灼口综合征：你的舌头痛竟是这些原因在作祟！

揭秘灼口综合征：你的舌头痛竟是这些原因在作祟！

在日常生活中&#xff0c;你是否曾遭遇过舌头像被火烧般的灼痛感&#xff1f;这种让人难以忍受的症状&#xff0c;其实是一种名为“灼口综合征”的疾病表现。今天&#xff0c;我们就来深入探讨这一疾病的背后原因&#xff0c;让你了解这一病症的真相&#xff0c;从而更好地应对…
阅读更多...
随记：有关idea中jdk版本

随记：有关idea中jdk版本

第一个地方&#xff1a;这个可能就是你整个项目的jdk版本的使用&#xff0c;你改了这里大概率可以改了 第二个地方&#xff1a; 就是 有关maven项目的 pom文件 一开始我的第一地方用的是 17 但是这里用的是8 但是运行的时候还是 17 这里可能是 maven的 项目这个地方只是对…
阅读更多...
Unity导入.FBX模型设置

Unity导入.FBX模型设置

** Unity导入.FBX模型设置 ** 第一步、导入.fbx模型 Assets- Import New Asset 第二步、设置 Animation Type 为Legacy 这里导入的是非人形模型设置为Lagacy None&#xff1a;不导入动画Animation Clip Legacy&#xff1a;用于早期动画设置&#xff0c;其不支持状态机A…
阅读更多...
WebSocket状态码及异常报错1006

WebSocket状态码及异常报错1006

文章目录 1.WebSocket协议简介2.WebSocket状态码的作用&#xff1a;3.WebSocket状态码1006详解1.问题原因2.解决方案 1.WebSocket协议简介 WebSocket协议是一种基于TCP的协议&#xff0c;它通过在浏览器和服务器之间建立一条持久的双向通信通道&#xff0c;实现了实时的数据传…
阅读更多...
最新文章

Copyright @ 2022~2023