初级数据结构（四）——队列

   文中代码源文件已上传：数据结构源码

<-上一篇 初级数据结构（三）——栈        |        NULL 下一篇->

        本篇是属于上一篇的补充篇，因为队列和栈的属性特别类似，很多细节部分可以查看上一篇或者初级据结构的第二篇。

1、队列特性

         之前已知，栈结构特性为 LIFO ，队列则是与之相反的先入先出，后入后出，也称为 FIFO （ Fist In Fist Out ）。如下图：

         因此，队列与栈的区别只在于弹出顺序，其余完全一致。但是，基于队列的特性，如果选用顺序表实现，则需要不断腾挪数据以填充弹出的头部位置，因此这里最好选用链表来实现以减小计算机资源的开销。

2、文件结构

        仍然是三个文件分模块实现：

        queue.h ：用于创建项目的结构体类型以及声明函数；

        queue.c ：用于创建队列各种操作功能的函数；

        main.c ：仅创建 main 函数，用作测试。

3、队列构建

3.1、代码

        queue.h 中代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define DATAPRT "%d"
typedef int DATATYPE;

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

typedef struct QueueInfo
{
	int size;
	QueueNode* head;
	QueueNode* tail;
}QueueInfo;

//函数定义---------------------------------

//队列初始化
extern void QueueInit(QueueInfo*);
//数据入队
extern void QueuePush(QueueInfo*, DATATYPE);
//数据出队
extern void QueuePop(QueueInfo*);
//销毁队列
extern void QueueDestroy(QueueInfo*);
//获取队列数据
extern DATATYPE QueueGetData(QueueInfo*);
//打印队列数据
extern void QueuePrint(QueueInfo*);

        queue.c 中代码：

#include "queue.h"

//队列初始化
void QueueInit(QueueInfo* info)
{
	//参数有效性验证
	if (!info)
	{
		fprintf(stderr, "Queue Pointer NULL\n");
		return;
	}
	//初始化
	info->size = 0;
	info->head = NULL;
	info->tail = NULL;
}

//数据入队
void QueuePush(QueueInfo* info, DATATYPE data)
{
	//参数有效性验证
	if (!info)
	{
		fprintf(stderr, "Queue Pointer NULL\n");
		return;
	}
	//创建节点
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	//创建成功验证
	if (!newNode)
	{
		fprintf(stderr, "Malloc Fail\n");
		return;
	}
	//新节点初始化
	newNode->data = data;
	newNode->next = NULL;
	//链接
	if (!info->size)
	{
		info->head = newNode;
		info->tail = newNode;
	}
	else
	{
		info->tail->next = newNode;
		info->tail = newNode;
	}
	info->size++;
}

//数据出队
void QueuePop(QueueInfo* info)
{
	//参数有效性验证
	if (!info)
	{
		fprintf(stderr, "Queue Pointer NULL\n");
		return;
	}
	//空表判断
	if (!info->size)
	{
		fprintf(stderr, "Queue Is Empty\n");
	}
	QueueNode* headNode = info->head->next;
	free(info->head);
	info->head = headNode;
	info->size--;
	if (!info->size)
	{
		info->tail = NULL;
	}
}

//销毁队列
void QueueDestroy(QueueInfo* info)
{
	//参数有效性验证
	if (!info)
	{
		fprintf(stderr, "Queue Pointer NULL\n");
		return;
	}
	//逐级释放节点
	if (info->size > 0)
	{
		while (info->head != info->tail)
		{
			QueueNode* currentNode = info->head;
			info->head = info->head->next;
			free(currentNode);
		}
		free(info->head);
	}
	QueueInit(info);
}

//获取队列数据
DATATYPE QueueGetData(QueueInfo* info)
{
	//参数有效性验证
	assert(info);
	assert(info->head);
	DATATYPE data = info->head->data;
	QueuePop(info);
	return data;
}

//打印队列数据
void QueuePrint(QueueInfo* info)
{
	//参数有效性验证
	if (!info)
	{
		fprintf(stderr, "Queue Pointer NULL\n");
		return;
	}
	//空队列打印NULL
	if (info->size == 0)
	{
		printf("NULL ");
		return;
	}
	printf(DATAPRT" ", QueueGetData(info));
}

        main.c 中的测试用例：

#include "queue.h"

int main()
{
	QueueInfo info;
	QueueInit(NULL);
	QueueInit(&info);
	QueuePush(&info, 1);
	QueuePush(&info, 2);
	QueuePush(&info, 3);
	QueuePush(&info, 4);
	QueuePush(&info, 5);
	QueuePush(&info, 6);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePush(&info, 1);
	QueuePush(&info, 2);
	QueuePush(&info, 3);
	QueuePush(&info, 4);
	QueuePush(&info, 5);
	QueuePush(&info, 6);
	QueuePop(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePop(&info);
	QueuePrint(&info);
	QueuePush(&info, 3);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueuePrint(&info);
	QueueDestroy(&info);
	return 0;
}

        以上便是全部代码，可自行测试和参考。构建过程中有一些需要注意的点，接下来作阐述。

3.2、构建要点

        1、与常规单链表不同，队列的构建最好以两种不同的结构体进行操作，除了节点信息的结构体之外，需要另外起一个结构体替代单链表的头节点指针。在此结构体内，储存的除了链表头节点指针之外，由于队列的特性，插入数据都是在尾部进行，因此另行创建一个成员变量用于保存尾节点指针。除此之外，为了方便判断队列中的节点个数（常规只判断是否为空队列），最好定义一个成员变量用于储存队列中节点个数。

        2、对于空队列和非空队列的数据入队需要分开讨论。空队列的数据入队需要同时操作头节点及尾节点指针同时指向第一个入队的元素。至于非空队列，需要操作尾节点指针，虽然不再操作头节点指针，但需要另行操作尾节点内部的 next 指针。

        3、数据出队时，如果操作对象时空队列则结束操作，可根据个人喜好自行选择用 assert 警告或者其他方式判断是否为空队列。

        4、销毁队列与单链表的销毁操作一致，直接参考即可。

4、用顺序表构建队列

        虽然不推荐用顺序表，但不代表顺序表不可行。但是在用顺序表构建队列时最好人为地设置阈值以控制什么时候将数组的数据移动至数组前端。

4.1、代码

        文件结构仍与链表实现队列的文件结构一致。代码如下：

        queue.h ：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define DATAPRT "%d"

typedef int DATATYPE;

typedef struct Queue
{
	//数据记录
	size_t size;
	int head;
	int tail;
	size_t capacity;
	//数据
	DATATYPE data[0];
}Queue;

//函数声明------------------------------------------
//初始化创建队列
extern Queue* QueueCreate(void);
//数据入队
extern void QueuePush(Queue*, DATATYPE);
//数据出队
extern void QueuePop(Queue*);
//销毁队列
extern void QueueDestroy(Queue**);
//获取队列数据
extern DATATYPE QueueGetData(Queue*);
//打印队列数据
extern void QueuePrint(Queue*);

        queue.c ：

#include "queue.h"

//初始化创建队列
Queue* QueueCreate(void)
{
	//创建队列
	Queue* queue = (Queue*)malloc(sizeof(Queue) + 4 * sizeof(DATATYPE));
	//队列创建结果检查
	if (!queue)
	{
		fprintf(stderr, "Malloc Fail");
		return;
	}
	//队列数据初始化
	queue->size = 0;
	queue->head = -1;
	queue->tail = -1;
	queue->capacity = 4;
	return queue;
}

//数据入队
void QueuePush(Queue* queue, DATATYPE data)
{
	//参数有效性检查
	if (!queue)
	{
		fprintf(stderr, "Queue Address NULL\n");
		return;
	}
	queue->tail++;
	if (queue->tail + 1 >= queue->capacity)
	{
		//队列扩容
		size_t tempSize = (sizeof(Queue) + sizeof(DATATYPE) * queue->capacity * 2);
		Queue* tempQueue = (Queue*)realloc(queue, tempSize);
		//队列扩容结果检查
		if (!tempQueue)
		{
			fprintf(stderr, "Realloc Fail\n");
			return;
		}
		queue = tempQueue;
		queue->capacity *= 2;
	}
	//数据入队
	queue->data[queue->tail] = data;
	//空队列判断
	if (0 == queue->size)
	{
		queue->head = queue->tail;
	}
	queue->size++;
}

//数据出队
void QueuePop(Queue* queue)
{
	//参数有效性检查
	if (!queue)
	{
		fprintf(stderr, "Queue Address NULL\n");
		return;
	}
	//空队列检查
	if (!queue->size)
	{
		fprintf(stderr, "Queue Is Empty\n");
		return;
	}
	queue->head++;
	queue->size--;
	//弹出后空队列检查
	if (!queue->size)
	{
		queue->head = -1;
		queue->tail = -1;
	}
	//空间回收
	if ((queue->size < queue->capacity / 2) && queue->capacity > 4)
	{
		//数据迁移
		for (int i = queue->head, j = 0; i <= queue->tail; i++, j++)
		{
			queue->data[j] = queue->data[i];
		}
		//空间收缩
		size_t tempSize = (sizeof(Queue) + sizeof(DATATYPE) * queue->capacity / 2);
		Queue* tempQueue = (Queue*)realloc(queue, tempSize);
		//队列空间收缩结果检查
		if (!tempQueue)
		{
			fprintf(stderr, "Realloc Fail");
			return;
		}
		//记录迁移
		tempQueue->capacity = queue->capacity / 2;
		tempQueue->head = 0;
		tempQueue->tail = queue->size - 1;
		queue = tempQueue;
	}
}

//销毁队列
void QueueDestroy(Queue** queue)
{
	//参数有效性检查
	if (!(*queue) || !queue)
	{
		fprintf(stderr, "Queue Address NULL\n");
		return;
	}
	free(*queue);
	*queue = NULL;
}

//获取队列数据
DATATYPE QueueGetData(Queue* queue)
{
	//参数有效性检查
	assert(queue);
	//空队列检查检查
	assert(queue->size);
	DATATYPE data = queue->data[queue->head];
	QueuePop(queue);
	return data;
}


//打印队列数据
void QueuePrint(Queue* queue)
{
	//参数有效性检查
	assert(queue);
	//空队列检查检查
	if (!queue->size)
	{
		printf("NULL ");
		return;
	}
	printf(DATAPRT" ", QueueGetData(queue));
}

        main.c 的测试用例：

#include "queue.h"

int main()
{
	Queue* queue = QueueCreate();
	QueuePush(NULL, 1);
	QueuePush(queue, 1);
	QueuePush(queue, 2);
	QueuePush(queue, 3);
	QueuePush(queue, 4);
	QueuePush(queue, 5);
	QueuePush(queue, 6);
	QueuePush(queue, 7);
	QueuePush(queue, 8);
	QueuePush(queue, 9);
	QueuePop(NULL);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePush(queue, 70);
	QueuePush(queue, 72);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePop(queue);
	QueuePop(queue);
	QueuePop(queue);
	QueuePop(queue);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePrint(queue);
	QueuePush(queue, 1);
	QueuePush(queue, 2);
	QueuePush(queue, 3);
	QueuePush(queue, 4);
	QueuePush(queue, 5);
	QueuePush(queue, 6);
	QueuePush(queue, 7);
	QueuePush(queue, 8);
	QueuePush(queue, 9);
	QueuePrint(queue);
	QueuePrint(queue);
	QueueDestroy(&queue);
	QueuePrint(queue);

	return 0;
}

4.2、构建要点

        这里采用的是柔性数组顺序表，当然也可以用结构体包含数组指针的顺序表构建。

        1、对于空队列的初始化，头数据的下标与尾数据的下标应该设置为 -1 ，这点与栈的顶部数据下标设置完全一致。

        2、通过头部元素的数组下标及尾部元素的数组下标来进行队列有效部分内容的控制，出队则头部数组下标 +1 ，入队则数组尾部下标 +1。

        3、数据出队必须进行空队列检查。此外，出队之后对队列中剩余有效元素进行判断，最佳方案是，如果剩余数据元素个数小于开辟空间的一半，则从头部至尾部元素依次腾挪到数组 0 下标位置开始的空间。腾挪完毕后再对过大的空间进行回收。

        4、此外，数据腾挪的时候使用 realloc 有个坑。由于 realloc 的原地扩容和异地扩容是不可控的，如果 realloc 是原地扩容，对临时队列的操作也同样会影响到真实的队列。如上述代码的出队函数，如果用 realloc 创建 tempQueue ，有可能 tempQueue 与 queue 指向同一块空间，所以切不可先对空间进行回收后才进行数据腾挪。

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

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

相关文章

DPDK是什么？DPDK网卡更有优势吗？

DPDK是什么？DPDK网卡更有优势吗？

近年来&#xff0c;随着数字化的推进&#xff0c;上云成为企业数字化建设的重要指标&#xff0c;用云程度持续深入。可以说&#xff0c;云时代已经来临。 应云而生的DPDK 云时代的一个典型特征&#xff0c;是数据的高速增长。据华为GIV数据&#xff0c;预计2025年全球数据量将…
阅读更多...
Java毕业设计—vue+SpringBoot图书借阅管理系统

Java毕业设计—vue+SpringBoot图书借阅管理系统

图书管理系统 1. 开发目的 实现图书的智能化、信息化和简单化&#xff1b;实现图书信息的增加、删除、修改、查找、借阅、还书、收藏的显示操作及实时数据库的提交和更改和对普通用户的增、删、改、查&#xff1b;提高图书管理员工作信息报送及反馈的工作效率&#xff0c;减轻…
阅读更多...
Visual Studio调试技巧合集

Visual Studio调试技巧合集

Visual Studio调试技巧合集 1 如何同一个项目运行不同main文件&#xff1f; 1 如何同一个项目运行不同main文件&#xff1f; &#xff08;1&#xff09;移动鼠标到需要关掉调试的文件&#xff0c;点击右键属性–常规–从生成中排除–是–确定&#xff0c;即显示“-”号排除&am…
阅读更多...
电线电缆行业生产管理MES系统解决方案

电线电缆行业生产管理MES系统解决方案

电线电缆行业生产管理mes系统核心功能 基础数据管理&#xff1a;对基础数据进行统一管理&#xff0c;包括组织架构、原材料数据、设备数据、报工数据、检验数据、员工数据等工艺与BOM管理&#xff1a;对工艺标准进行统一管理&#xff0c;包括工艺的版本管理、关联型号管理&…
阅读更多...
Tair（4）：Tair原理架构

Tair（4）：Tair原理架构

一个Tair集群主要包括3个必选模块&#xff1a;ConfigServer、Dataserver和Client 通常情况下&#xff0c;一个 Tair 集群中包含2台 Configserver 及多台 DataServer。其中两台 Configserver 互为主备。通过和 Dataserver 之间的心跳检测获取集群中存活可用的 Dataserver&#…
阅读更多...
Python 从入门到精通 学习笔记 Day04

Python 从入门到精通 学习笔记 Day04

Python 从入门到精通 第四天 今日目标 数据类型-又见str、数据类型-又见list 列表切片&排序&反转&循环、字典 数据类型 - 又见str 字符串定义 字符串是一个有序的字符的集合&#xff0c;用于在计算机里存储和表示文本信息 创建 a "Hello ,my name is Ha…
阅读更多...
AUTOSAR_SWS_LogAndTrace文档中文翻译

AUTOSAR_SWS_LogAndTrace文档中文翻译

** 1 Introduction and functional overview ** 本规范规定了AUTOSAR自适应平台日志和跟踪的功能。 日志和跟踪为AA提供接口&#xff0c;以便将日志信息转发到通信总线、控制台或文件系统。 提供的每个日志记录信息都有自己的严重性级别。对于每个严重级别&#xff0c;都提供…
阅读更多...
【MySQL】触发器trigger / 事件

【MySQL】触发器trigger / 事件

文章目录 1. 触发器 trigger1.1 触发器命名1.2 new和old关键字1.3 案例&#xff1a;insert 触发器1.4 练习&#xff1a;delete 触发器1.5 查看触发器 show triggers1.6 使用触发器记录对表的操作 2 事件2.1 打开 / 关闭事件调度器2.2 创建事件 create event2.3 查看&#xff0c…
阅读更多...
【Linux服务器Java环境搭建】09 在CentOS系统中安装和配置clickhouse数据库

【Linux服务器Java环境搭建】09 在CentOS系统中安装和配置clickhouse数据库

一、安装环境 CentOS7 二、官网安装参考文档 官网安装参考文档 不同系统请参考如下建议 从RPM软件包安装&#xff1a; 建议在CentOS、RedHat和所有其他基于rpm的Linux发行版上使用官方预编译的rpm软件包从DEB软件包安装&#xff1a; 建议在Debian或Ubuntu上使用官方预编译…
阅读更多...
分割均衡字符串 - 华为OD统一考试（C卷）

分割均衡字符串 - 华为OD统一考试（C卷）

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 均衡串定义:字符串只包含两种字符&#xff0c;且两种字符的个数相同。 给定一个均衡字符串&#xff0c;请给出可分割成新的均衡子串的最大个数。 约定字符串中只…
阅读更多...
【数据结构(十二·图)】图的相关知识（包括深度优先遍历和广度优先遍历）

【数据结构(十二·图)】图的相关知识（包括深度优先遍历和广度优先遍历）

文章目录 1. 图的基本介绍1.1. 图的举例说明1.2. 图的常用概念 2. 图的表示方式2.1. 邻接矩阵2.2. 邻接表 3. 应用案例4. 图的遍历4.1. 深度优先遍历4.1.1. 基本思想4.1.2. 算法步骤4.1.3. 代码实现 4.2. 广度优先遍历4.2.1. 基本思想4.2.2. 算法步骤4.2.3. 代码实现 4.3. 图的…
阅读更多...
【Geoserver】将geoserver迁移到jetty的发行包中

【Geoserver】将geoserver迁移到jetty的发行包中

之前讲了在Geosever的二进制发行包中升级jetty的内容&#xff0c;我测试之后发现有些问题&#xff0c;本地运行可能没有问题&#xff0c;但是在linux上运行报错了。 于是我想着换个思路好了&#xff0c;总是想着将Geosever中的jetty包替换掉&#xff0c;干脆反过来&#xff0c;…
阅读更多...
css 实现GTA5 封面

css 实现GTA5 封面

上面的图片如何通过css 完成呢。废话不说&#xff0c;直接上代码 <template><view class"movie_report"><view class"movie_img" v-for"item in 9" :key"item"><image :src"../../static/item.png" &…
阅读更多...
螺旋矩阵算法(leetcode第54题)

螺旋矩阵算法(leetcode第54题)

题目描述&#xff1a; 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。示例 1&#xff1a;输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a;输入&#xff…
阅读更多...
用python打印出菱形图案

用python打印出菱形图案

你可以使用Python编写一个简单的函数来打印菱形图案。下面是一个例子&#xff0c;这个函数接受一个参数n&#xff0c;表示菱形的高度&#xff0c;然后打印出一个菱形图案&#xff1a; def print_diamond(n): # 上半部分 for i in range(n): print(" " …
阅读更多...
接口测试练习步骤

接口测试练习步骤

在接触接口测试过程中补了很多课&#xff0c; 终于有点领悟接口测试的根本&#xff1b; 偶是个实用派&#xff5e;&#xff0c;那么现实中没有用的东西&#xff0c;基本上我都不会有很大的概念&#xff1b; 下面给的是接口测试的统一大步骤&#xff0c;其实就是让我们对接口…
阅读更多...
滑动窗口如人生，回顾往事不复还———力扣刷题

滑动窗口如人生，回顾往事不复还———力扣刷题

第一题&#xff1a;长度最小的子数组 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 思路&#xff1a; 第一想法肯定时暴力枚举&#xff0c;枚举数组任何一个元素&#xff0c;把他当起始位置&#xff0c;然后从起始位置找最短区间&#xff0c;使得…
阅读更多...
接口测试 — 2.Requests库介绍

接口测试 — 2.Requests库介绍

1、接口测试的意义&#xff08;优势&#xff09; &#xff08;1&#xff09;更早的发现问题&#xff1a; 不少的测试资料中强调&#xff0c;测试应该更早的介入到项目开发中&#xff0c;因为越早的发现bug&#xff0c;修复的成本越低。 然而功能测试必须要等到系统提供可测试…
阅读更多...
微搭低代码实现登录注册功能

微搭低代码实现登录注册功能

目录 1 创建用户数据源2 实现登录逻辑3 搭建登录页面4 设置登录框5 实现登录的逻辑6 用户注册总结 原来产品在创建应用的时候可以创建模型应用&#xff0c;模型应用对应我们小程序的后端。最新的更新已经将模型应用的能力下线&#xff0c;那我们不得不自己实现一下后端的逻辑。…
阅读更多...
目前进度记录

目前进度记录

目前已经把之前记录的方法都实现了&#xff0c;目前的主函数可以写的更简单比如 int main(int argc, char* argv[]) {KernelClass::create_kernel();MPI_Init(&argc, &argv);kernel().mpi_manager.init_mpi(argc, argv);//创建种群int group1 kernel().conn_manger.c…
阅读更多...
最新文章

Copyright @ 2022~2023