数据结构：7、队列

一、队列的概念与结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头，如下图。

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

二、队列的实现

1、队列的初始化与销毁

这个思路是，先创建一个节点用来存储数据，也就是一个单链表，而这里需要头和尾，也就是尾进头出，如1 2 3 4 5 6 7 这样进去，出去也是1 2  3 4 5 6 7，顺序不会改变，所以这里又定义了一个结构用来存储头和尾以及有效的数据，方便后续操作，初始化这里就是把头和尾指向空，当有数据进来时才指向新的节点，销毁就是把单链表释放销毁，而刚开始使用存储链表的头和尾的结构体，因为是局部变量，只需要把头和尾的指针置空，当函数销毁时，这个结构体也会销毁，代码如下。

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
	
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
// 初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2、队列的入队与出队

这个队列是尾进头出，也就相当于尾插头删，但是需要考虑到链表中没有数据时的情况，也就是尾插时没有数据，会插入一个数据，第二个就是正常的尾插，而头删就需要考虑没有数据时，就直接释放了，代码如下。

// 队尾入队列 
void QueuePush(Queue* pq, QDataType data)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		assert(pq->phead==NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

3、判断与获取首尾元素与队列内有效元素

这个就是利用之前创建的结构体可以判断下链表里有没有数据，如果有可以直接返回，之前定义的数据个数也就是可以直接看出链表有多少数据，判断也就可以直接判断有多少数据，但是不能在删除时不能忘记把数据个数减减。

// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size==0;
}

4、测试与测试结果

这个就是测试各个函数，也就是插入1 2 3 4 5 6 7然后读取下有几个数据，然后把尾部数据打印，利用之前写的判断函数也就可以直接用while函数去进行出队数据并且打印，然后队里数据全部出完后，再去取数据打印和删除，会直接报错，代码和测试结果如图。

#define _CRT_SECURE_NO_WARNINGS 1
#include "QL.h"

void TestQueue()
{
	Queue q;
	
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	printf("size:%d\n", QueueSize(&q));
	printf("%d\n", QueueBack(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueueDestroy(&q);
}

int main()
{
	TestQueue();
	return 0;
}

三、代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "QL.h"

void TestQueue()
{
	Queue q;
	
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	printf("size:%d\n", QueueSize(&q));
	printf("%d\n", QueueBack(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueueDestroy(&q);
}

int main()
{
	TestQueue();
	return 0;
}

QL.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "QL.h"

// 初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* pq, QDataType data)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		assert(pq->phead==NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size==0;
}

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

QL.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
	
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* pq);
// 队尾入队列 
void QueuePush(Queue* pq, QDataType data);
// 队头出队列 
void QueuePop(Queue* pq);
// 获取队列头部元素 
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数 
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
// 销毁队列 
void QueueDestroy(Queue* pq);

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

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

相关文章

功能测试--APP性能测试

功能测试--APP性能测试

功能测试--APP性能测试 内存数据查看内存测试 CPU数据查看CPU测试 流量和电量的消耗流量测试流量优化方法电量测试电量测试场景&#xff08;大&#xff09; 获取启动时间启动测试--安卓 流畅度流畅度测试 稳定性稳定性测试 内存数据查看 内存泄露:内存的曲线持续增长(增的远比减…
阅读更多...
码头船只出行和货柜管理系统的设计与实现

码头船只出行和货柜管理系统的设计与实现

针对于码头船只货柜信息管理方面的不规范&#xff0c;容错率低&#xff0c;管理人员处理数据费工费时&#xff0c;采用新开发的码头船只货柜管理系统可以从根源上规范整个数据处理流程。 码头船只货柜管理系统能够实现货柜管理&#xff0c;路线管理&#xff0c;新闻管理&#…
阅读更多...
【MMDetection3D实战(3)】: KITTI 数据集介绍

【MMDetection3D实战(3)】: KITTI 数据集介绍

文章目录 1. 数据集介绍2 数据下载及准备2.1 下载并整理数据集2.2 传感器及坐标定义2.3 数据的标注3 MMDet3D 中的坐标系规范4 数据的处理及可视化4.1 数据处理4.2 点云读取和可视化4.2.1 点云的读取4.2.2 点云的可视化1. 数据集介绍 KITTI数据集是3D目标检测中比较基础和常用…
阅读更多...
【LeetCode】升级打怪之路 Day 17：二叉树题型 —— 二叉树的序列化与反序列化

【LeetCode】升级打怪之路 Day 17：二叉树题型 —— 二叉树的序列化与反序列化

今日题目&#xff1a; 297. 二叉树的序列化与反序列化652. 寻找重复的子树 目录 LC 297. 二叉树的序列化与反序列化 【classic】 ⭐⭐⭐⭐⭐1&#xff09;序列化逻辑2&#xff09;反序列化逻辑 LC 652. 寻找重复的子树 【稍有难度】 今天主要学习了二叉树的序列化和反序列化相关…
阅读更多...
数字逻辑-时序逻辑电路一

数字逻辑-时序逻辑电路一

一、实验目的 &#xff08;1&#xff09;熟悉触发器的逻辑功能及特性。 &#xff08;2&#xff09;掌握集成D和JK触发器的应用。 &#xff08;3&#xff09;掌握时序逻辑电路的分析和设计方法。 二、实验仪器及材料 三、实验内容及步骤 1、用D触发器&#xff08;74LS74&am…
阅读更多...
使用Docker在windows上安装IBM MQ

使用Docker在windows上安装IBM MQ

第一步、安装wsl 详见我另一篇安装wsl文章。 第二步、安装centos 这里推荐两种方式&#xff0c;一种是从微软商城安装&#xff0c;一种是使用提前准备好的镜像安装&#xff0c;详见我另一篇windos下安装centos教程。 第三步、安装windows下的Docker desktop 详见我另一篇wind…
阅读更多...
TQ15EG开发板教程：运行MPSOC+AD9361

TQ15EG开发板教程：运行MPSOC+AD9361

目录 1&#xff0c;下载工程需要使用的文件 2&#xff0c;编译以及修改工程 3&#xff0c;获取生成BOOT.BIN所需要的3个文件 3.1生成bit文件 3.2生成elf文件 3.3生成fsbl文件 4&#xff0c;生成boot.bin文件 5&#xff0c;上板测试 6&#xff0c;切换FMC接口 7&#…
阅读更多...
自适应窗口图片轮播HTML代码

自适应窗口图片轮播HTML代码

自适应窗口图片轮播HTML代码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c;重定向这个界面 代码下载地址 自适应窗口图片轮播HTML代码
阅读更多...
分享 | 计算机组成与设计学习资料+CPU设计源码+实验报告

分享 | 计算机组成与设计学习资料+CPU设计源码+实验报告

1.引言 百度网盘资源链接&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1Ww6u_l1L6DMXofC2HxfETw?pwdyqd6 提取码&#xff1a;yqd6 2.学习资源预览 2.1 包含学习手册四本&#xff1a; - 计算机原理与设计&#xff1a;Verilog HDL版 - 计算机组成与设…
阅读更多...
开源分子对接程序rDock使用方法(2)-高通量虚拟筛选HTVS

开源分子对接程序rDock使用方法(2)-高通量虚拟筛选HTVS

欢迎浏览我的CSND博客&#xff01; Blockbuater_drug …点击进入 文章目录 前言一、rDock用于高通量虚拟筛选HTVSMulti-Step Protocol HTVS步骤及注意事项 二、rDock中Multi-Step Protocol用于HTVS的用法Step 1. Exhaustive dockingStep 2. sdreport summaryStep 3. 运行rbhtfi…
阅读更多...
Linux之NFS网络文件系统详解

Linux之NFS网络文件系统详解

华子目录 简介NFS背景介绍注意 生产应用场景NFS工作原理示例图流程 NFS的使用安装配置文件主配置文件分析权限参数/etc/exports文件内容示例 实验1nfs账户映射实验2实验3 autofs自动挂载服务产生原因安装配置文件分析挂载参数 实验4实验5&#xff1a;本机自动挂载光驱 简介 NF…
阅读更多...
专升本 C语言笔记-08 goto语句

专升本 C语言笔记-08 goto语句

goto语句 无条件跳转运算符(凡是执行到goto语句会直接跳转到 定义的标签) 缺点&#xff1a;滥用goto语句将会导致逻辑混乱&#xff0c;导致系统崩溃等问题! ! ! 代码演示 int i 0; //定义标签 jump(名字随便起哦) jump:printf("%d ",i); i; if(i < 10)goto j…
阅读更多...
如何处理Android悬浮弹窗双击返回事件？

如何处理Android悬浮弹窗双击返回事件？

目录 1 前言 1.1 准备知识 1.2 问题概述 2 解决方案 3 代码部分 3.1 动态更新窗口焦点 3.2 窗口监听返回事件 3.3 判断焦点是否在窗口内部 3.4 窗口监听焦点移入/移出 1 前言 1.1 准备知识 1&#xff09;开发环境&#xff1a; 2D开发环境&#xff1a;所有界面或弹窗…
阅读更多...
Burp Suite Professional Error No response received from remote server.

Burp Suite Professional Error No response received from remote server.

记录burp suite 抓到包-改包-放包之后出现的问题&#xff1a; Burp Suite Professional Error No response received from remote server. 重新下载软件&#xff0c;没有进行汉化&#xff0c;好用了。汉化真坑。
阅读更多...
buuctf warmup 超详细

buuctf warmup 超详细

目录 1.代码审计&#xff1a; 2.逻辑分析 3.总结分析 4.分析记录 5.疑点解答 1.代码审计&#xff1a; <?phphighlight_file(__FILE__);class emmm //定义了一个类{public static function checkFile(&$page) 类里面又申明创建…
阅读更多...
论文阅读——RemoteCLIP

论文阅读——RemoteCLIP

RemoteCLIP: A Vision Language Foundation Model for Remote Sensing 摘要——通用基础模型在人工智能领域变得越来越重要。虽然自监督学习&#xff08;SSL&#xff09;和掩蔽图像建模&#xff08;MIM&#xff09;在构建此类遥感基础模型方面取得了有希望的结果&#xff0c;但…
阅读更多...
【JavaScript】面试手撕柯里化函数

【JavaScript】面试手撕柯里化函数

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 引入柯里化定义实现快速使用柯里化的作用提高自由度bind函数 参考资料 引入 上周…
阅读更多...
目标跟踪SORT算法原理浅析

目标跟踪SORT算法原理浅析

SORT算法 Simple Online and Realtime Tracking(SORT)是一个非常简单、有效、实用的多目标跟踪算法。在SORT中&#xff0c;仅仅通过IOU来进行匹配虽然速度非常快&#xff0c;但是ID switch依然非常严重。 SORT最大特点是基于Faster RCNN的目标检测方法&#xff0c;并利用卡尔…
阅读更多...
跟着GPT学设计模式之桥接模式

跟着GPT学设计模式之桥接模式

说明 桥接模式&#xff0c;也叫作桥梁模式&#xff0c;英文是 Bridge Design Pattern。在 GoF 的《设计模式》一书中&#xff0c;桥接模式是这么定义的&#xff1a;“Decouple an abstraction from its implementation so that the two can vary independently。”翻译成中文就…
阅读更多...
【Ubuntu-20.04】OpenCV-3.4.16的安装并对图片与视频处理

【Ubuntu-20.04】OpenCV-3.4.16的安装并对图片与视频处理

【Ubuntu-20.04】OpenCV-3.4.16的安装并对图片与视频处理 一、安装OpenCV-3.4.161.下载OpenCV-3.4.16安装包2.将安装包放到/home&#xff0c;并解压3.使用 cmake 安装 opencv4.配置环境5.查看 opencv 的版本信息 二、处理图片&#xff08;一&#xff09;创建文件夹 code &#…
阅读更多...
最新文章

Copyright @ 2022~2023