首页 > 其他分享 >队列的深度解析:链式队列的实现

队列的深度解析:链式队列的实现

时间:2024-09-27 20:48:43浏览次数:7  
标签:Node ptail QU 队列 assert phead 链式 解析

引言

队列是一种广泛应用于计算机科学的数据结构,具有先进先出FIFO)的特性。在许多实际应用中,例如任务调度、缓冲区管理等,队列扮演着重要角色。本文将详细介绍队列的基本概念,并通过链表实现一个简单的队列。

一、基本概念

1.1定义

队列是一种线性数据结构,遵循先进先出(FIFO,First In First Out)的原则。这意味着第一个被插入的元素是第一个被移除的元素。队列模拟了排队现象,新来的人不断加入队列尾部,而位于队列头部的人逐个离开。 如下图所示,我们将队列头部称为“队首”,尾部称为“队尾”,将把元素加入队尾的操作称为“入队”,删除队首元素的操作称为“出队”。

8b8b5dd4ce9f49949af453a853779ae7.png

1.2基本操作

969bd4e7009949c28a541dc7e974f9b5.gif

队列的主要操作包括:

  • 入队(Push):将一个元素添加到队列的尾部。
  • 出队(Pop):移从队列的头部移除并返回一个元素。
  • 取队首元素(Front):返回队首的元素,但不删除它。
  • 取队尾元素(Back):返回队尾的元素,但不删除它。
  • 队列判空(isEmpty):判断队列中是否有元素。
  • 获取队列长度(Size):获取队列中有效元素个数。

1.3队列的特点 

队列的特点包括:

先进先出(FIFO):最先进入的元素最先被移除。

操作限制:只能在队列的头部出队,在尾部入队。

队首元素:队首是当前可以访问和移除的元素。

空队列:队列为空时无法进行出队操作。

动态大小:可以根据需要扩展或收缩。

三、链式队列的实现 

1.链表节点的定义

首先,我们定义一个链表节点结构:

typedef int DataType;
//定义节点结构体
typedef struct Node
{
	DataType data;//数据域
	struct Node* next;//指针域
}Node;

2ee3104913264cee96fc3905bb1a931b.png

2.队列结构的定义

然后,我们定义队列结构,包含队头、队尾指针以及队列长度:

//定义队列结构体
typedef struct Queue
{
	Node* phead;//队头
	Node* ptail;//队尾
	int size;//队列长度
}QU;

3.基本操作 

(1).初始化队列

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

(2).入队

ae0d63fd2cfd4242b89160852ba0966d.png

//创建节点
//Node* CreateNode(DataType x)
//{
//	Node* newnode = (Node*)malloc(sizeof(Node));
//	if (newnode == NULL) {
//		perror("malloc fail");
//		exit(1);
//	}
//	newnode->data = x;
//	newnode->next = NULL;
//	return newnode;
//}

//入队列,队尾
void QueuePush(QU* p, DataType x)
{
	assert(p);
	Node* newnode = CreateNode(x);
	if (p->phead == NULL)//队列为空
	{
		p->phead = p->ptail = newnode;
	}
	else//队列不为空
	{
		p->ptail->next = newnode;
		p->ptail = newnode;
	}
	++p->size;
}

(3).队列判空

//队列判空 
bool QueueEmpty(QU* p)
{
	assert(p);
	return p->phead == NULL;
}

(4).出队 

0615740d529a4d07935513913a9bb66d.png

//出队列,队头 
void QueuePop(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列为空不能出队
	if (p->phead == p->ptail)//只有一个元素时
	{
		free(p->phead);
		p->phead = p->ptail = NULL;
	}
	else
	{
		Node* del = p->phead;
		p->phead = p->phead->next;
		free(del);
	}
	--p->size;
}

(5).取队首元素

//取队头数据 
DataType QueueFront(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	return p->phead->data;
}

(6).取队尾元素 

//取队尾数据 
DataType QueueBack(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	return p->ptail->data;
}

(7).获取队列长度

//队列长度
int QueueSize(QU* p)
{
	assert(p);
	return p->size;
}

(8).销毁队列 

//销毁队列 
void QueueDestroy(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	Node* pcur = p->phead;
	while (pcur)
	{
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL;
	p->size = 0;
}

四、完整代码 

Queue.h

该部分主要包括函数的声明、以及头文件的引用

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int DataType;
//定义节点结构体
typedef struct Node
{
	DataType data;//数据域
	struct Node* next;//指针域
}Node;
//定义队列结构体
typedef struct Queue
{
	Node* phead;//队头
	Node* ptail;//队尾
	int size;//队列长度
}QU;
//初始化队列 
void QueueInit(QU* p); 
//入队列,队尾
void QueuePush(QU* p, DataType x);
//队列判空 
bool QueueEmpty(QU* p);
//出队列,队头 
void QueuePop(QU* p);
//取队头数据 
DataType QueueFront(QU* p);
//取队尾数据 
DataType QueueBack(QU* p);
//队列长度
int QueueSize(QU* p);
//销毁队列 
void QueueDestroy(QU* p);

Queue.c

该部分主要包括函数的定义 

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
//初始化队列 
void QueueInit(QU* p)
{
	assert(p);
	p->phead = p->ptail = NULL;
	p->size = 0;
}

//创建节点
Node* CreateNode(DataType x)
{
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//入队列,队尾
void QueuePush(QU* p, DataType x)
{
	assert(p);
	Node* newnode = CreateNode(x);
	if (p->phead == NULL)//队列为空
	{
		p->phead = p->ptail = newnode;
	}
	else//队列不为空
	{
		p->ptail->next = newnode;
		p->ptail = newnode;
	}
	++p->size;
}
//队列判空 
bool QueueEmpty(QU* p)
{
	assert(p);
	return p->phead == NULL;
}
//出队列,队头 
void QueuePop(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列为空不能出队
	if (p->phead == p->ptail)//只有一个元素时
	{
		free(p->phead);
		p->phead = p->ptail = NULL;
	}
	else
	{
		Node* del = p->phead;
		p->phead = p->phead->next;
		free(del);
	}
	--p->size;
}
//取队头数据 
DataType QueueFront(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	return p->phead->data;
}
//取队尾数据 
DataType QueueBack(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	return p->ptail->data;
}
//队列长度
int QueueSize(QU* p)
{
	assert(p);
	return p->size;
}
//销毁队列 
void QueueDestroy(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列不能为空
	Node* pcur = p->phead;
	while (pcur)
	{
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL;
	p->size = 0;
}

 main.c

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void test()
{
	QU qu;
	QueueInit(&qu);
	QueuePush(&qu, 1);
	QueuePush(&qu, 2);
	QueuePush(&qu, 3);
	QueuePush(&qu, 4);
	QueuePop(&qu);
	printf("head:%d\n", QueueFront(&qu));
	printf("back:%d\n", QueueBack(&qu));
	printf("size:%d\n", QueueSize(&qu));
}
int main()
{
	test();
	return 0;
}

五、总结

在本次博客中,我们实现了一个基本的队列数据结构,涵盖了以下几个关键功能:

  1. 初始化队列:创建一个空队列,准备进行后续操作。

  2. 入队:实现了在队尾添加新元素的功能,确保队列能够动态扩展。

  3. 队列判空:提供了检查队列是否为空的方法,便于在操作前判断队列状态。

  4. 出队:实现了从队首移除元素的功能,遵循先进先出的原则。

  5. 取队首元素:能够访问当前队首元素,但不移除它,方便查看下一个处理的元素。

  6. 取队尾元素:允许访问队尾元素,虽然不常见,但在某些场景中有其用途。

  7. 获取队列长度:实现了获取当前队列中元素数量的功能,便于管理和监控队列状态。

  8. 销毁队列:提供了清理队列资源的方法,防止内存泄漏。

通过实现这些基本操作,我们展示了队列的基本特性和使用方法,为理解队列在实际应用中的重要性奠定了基础。队列作为一种重要的数据结构,在任务调度、资源管理等多个领域都有广泛应用。希望这篇博客能帮助你更好地理解和使用队列。

 

标签:Node,ptail,QU,队列,assert,phead,链式,解析
From: https://blog.csdn.net/2302_81410974/article/details/142529879

相关文章

  • 《破晓传说》d3dcompiler_43.dll缺失启动遇阻?d3dcompiler_43.dll丢失问题全解析与解决
    《破晓传说》在启动过程中遇到d3dcompiler_43.dll缺失的问题,确实会导致游戏无法正常运行。这个问题通常与DirectX组件的完整性或兼容性有关。以下是对d3dcompiler_43.dll丢失问题的全解析与解决方案:问题解析d3dcompiler_43.dll是什么?d3dcompiler_43.dll是DirectX的一部分,它......
  • 蓝牙定位导航系统深度解析:技术原理、实现步骤与实战应用
    随着物联网(IoT)技术的飞速发展,蓝牙低功耗(BLE)技术凭借其低功耗、高兼容性及短距离通信的优势,在各类定位系统中占据了重要地位。其中,蓝牙定位导航系统作为室内定位解决方案的佼佼者,正逐步改变着我们的生活方式。本文将深入探讨蓝牙定位导航系统的技术原理、关键技术、实现步骤,并通......
  • AI驱动的智能运维:行业案例与挑战解析
    华为、蚂蚁、字节跳动如何引领智能运维?©作者|潇潇来源|神州问学引言OpenAI发布的ChatGPT就像是打开了潘多拉的魔盒,释放出了生产环境中的大语言模型(LLMs)。一些新的概念:“大语言模型运维(LLMOps)”、“智能运维平台(AIOps)”也随之迸发和迭代。与传统运维方法相比,这......
  • 解析 Llama-Factory:从微调到推理的架构
    轻松搞定大模型微调与推理的开源神器©作者|DWT来源|神州问学一、前言:Llama-Factory的背景与重要性在人工智能(AI)领域,尤其是自然语言处理(NLP)技术迅速发展的今天,如何高效地微调和部署大型语言模型(LLM)成为了研究和应用的热点。Llama-Factory作为一个开源的微调框架,正是在......
  • 基于递归下降解析器的四则运算题生成器
    结对项目本次项目的GitHub位置:https://github.com/EIiasK/Eliask/tree/main/3122004566/Exercise_Generator项目成员及github地址郭人诵github地址:https://github.com/EIiasK/Eliask何其浚github地址:https://github.com/hugh143/hugh143这个作业属于哪个课程......
  • 9.27今日错题解析(软考)
    目录前言信息安全——网络攻击算法基础——二分查找数据库系统——数据库设计过程前言这是用来记录我每天备考软考设计师的错题的,今天知识点为网络攻击、二分查找和数据库设计过程,大部分错题摘自希赛中的题目,但相关解析是原创,有自己的思考,为了复习:),最后希望各位报考......
  • 循环队列入队出队
    队列队列特性:先进先出限定插入操作只能在队尾进行,而删除操作只能在队头进行。循环队列:一种线性数据结构,其操作表现基于先进先出,队尾被连接在队首之后以形成一个循环。循环队列的操作与普通队列类似,但又有独特的优点下面给出一些循环队列的操作函数:队列创建、入队、......
  • Qt解析十六进制串
      QByteArrayarr1=QByteArray::fromHex("000000A1000000B2000005DC00000000000000900000000000000000000000000000000100000020000000210000000100000000001748C8000000000000046C00000000000000A100000000000000000000006000000000000061E400000000");for......
  • Spring Cloud全解析:服务调用之OpenFeign日志打印
    OpenFeign日志打印OpenFeign提供了日志打印功能,可以配置不同级别的日志级别publicenumLevel{//默认,不显示任何日志NONE,//仅记录请求方法、url、响应状态码及执行时间BASIC,//除记录BASIC信息外,还记录请求头和响应头HEADERS,//除了HEADERS信息外,还有请......
  • 强化学习详解:理论基础与核心算法解析
    本文详细介绍了强化学习的基础知识和基本算法,包括动态规划、蒙特卡洛方法和时序差分学习,解析了其核心概念、算法步骤及实现细节。关注作者,复旦AI博士,分享AI领域全维度知识与研究。拥有10+年AI领域研究经验、复旦机器人智能实验室成员,国家级大学生赛事评审专家,发表多篇SCI核心......