【算法与数据结构】 C语言实现单链表队列详解

请添加图片描述

文章目录

  • 📝队列
  • 🌠 数据结构设计
    • 🌉初始化队列函数
  • 🌠销毁队列函数
    • 🌉入队函数
  • 🌠出队函数
    • 🌉获取队首元素函数
  • 🌠获取队尾元素函数
    • 🌉 判断队列是否为空函数
    • 🌉获取队列大小函数
  • 🌠测试
    • 🌉 总源代码
  • 🚩总结

📝队列

前面我们学习了队列的顺序表的实现，本节将用单链表实现队列。
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。下面我们先复习一下队列的基本概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
在这里插入图片描述
在这里插入图片描述

🌠 数据结构设计

首先，我们需要定义队列节点的数据结构和队列的数据结构：

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

// 定义队列节点数据结构
typedef int QDataType;//定义了一个新的数据类型 QDataType

typedef struct QueueNode 
{
    QDataType* data;//数据指针
    struct QueueNode* next;//指向下一个节点的指针。
} QNode;

当我们去定义队列的出队和入队时需要用到二级指针，这样传递指针的指针操作起来会有些繁琐，也不能更符合队列的逻辑结构，二级指针代码如下：

//入队列
void QueuePush(QNode** pphead, QNode** pptail);
//出队列
void QueuePop(QNode** pphead, QNode** pptail);

虽然使用指向指针的指针也可以实现队列的功能，但是使用结构体封装的方式更符合常见的数据结构和面向对象编程的思想，能够提高代码的可读性、可维护性和易用性。

// 定义队列数据结构
typedef struct Queue 
{
    QNode* phead;//指向队列的头节点（队首）
    QNode* ptail;//指向队列的尾节点（队尾）。
    int size;//表示队列中元素的数量。
} Queue;

对于队列这种数据结构，使用指向队列头部和尾部的指针以及队列大小的方式进行封装有以下好处：

  1. 封装性更好：

    • 使用 Queue 结构体将队列的头部指针、尾部指针和大小封装在一起，更符合面向对象编程的思想，提高了代码的封装性和可维护性。
    • 将队列的相关信息放在一个结构体中，使得对队列的操作更加直观和清晰，降低了出错的可能性。

  2. 操作更加直观：

    • 在进行队列操作时，使用 Queue 结构体可以直接通过 phead 和 ptail 指针来操作队列的头部和尾部，而无需传递指向指针的指针。这样使得代码更加清晰，不易出错。

  3. 提高代码的可读性和可维护性：

    • 使用 Queue 结构体可以将队列的相关信息集中在一起，使得代码更加清晰易读。
    • 在函数参数中传递 Queue* 类型的指针，比传递指向指针的指针更加直观和易懂，减少了理解代码的难度。

由于队列是先进先出，并且单向的，而头节点是哨兵位，要也可以不要也可以，本文没有用多出使用一个头节点。
在这里插入图片描述

🌉初始化队列函数

先确保传入的队列指针 pq 不为空，将队列的头指针、尾指针置为空，大小置为0。

void QueueInit(Queue* pq)
{
  assert(pq); // 断言队列指针是否为空
  pq->phead = NULL; // 初始化头节点指针为空
  pq->ptail = NULL; // 初始化尾节点指针为空  
  pq->size = 0; // 初始化队列大小为0
}

🌠销毁队列函数

首先断言队列指针是否为空，cur从头节点开始遍历队列，保存cur下一个节点的指针，释放cur节点内存，cur移到下一个节点，遍历完整个队列后,将头尾节点指针和大小都重置为初始状态

void QueueDestroy(Queue* pq) 
{

  assert(pq); // 断言队列指针是否为空
  QNode* cur = pq->phead; // cur指向队列头节点
  while (cur) 
  {  
    QNode* next = pq->phead->next; // 保存cur下一个节点的指针
    free(cur); // 释放cur节点内存
    cur = next; // cur指针移到下一个节点
  }
  pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
  pq->size = 0; // 重置队列大小为0

}

🌉入队函数

将新的数据 x 入队，要分配一个新的节点 newnode，将数据 x 存储在节点中。根据队列是否为空，将新节点连接到队列的尾部，并更新尾指针。如果队列为空，则同时更新头指针。
增加队列的大小。

void QueuePush(Queue* pq, QDataType* x) 
{
  assert(pq); // 断言队列指针是否为空
  QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新节点内存
  if (newnode == NULL) 
  { // 申请失败
    perror("malloc fail"); 
    return;
  }
  newnode->data = x; // 设置新节点数据
  newnode->next = NULL; // 设置新节点next指针为空

  if (pq->ptail)
  { // 如果队列不为空
    pq->ptail->next = newnode; // 尾节点指向新节点
    pq->ptail = newnode; // 更新尾节点指针
  } 
  else 
  { // 队列为空
    pq->phead = pq->ptail = newnode; // 头尾节点同时指向新节点
  }

  pq->size++; // 队列大小增加1

}

在这里插入图片描述

🌠出队函数

出队，即删除队列中的队首元素。首先检查队列是否为空，如果为空则直接返回。如果队列只有一个节点，则直接释放这个节点，同时将头尾指针置为空。如果队列有多个节点，则释放队首节点，并将头指针指向下一个节点。减小队列的大小。

void QueuePop(Queue* pq) 
{

  assert(pq); // 断言队列指针是否为空
  if (pq->phead == NULL) 
  			return; // 队列为空直接返回
  			
  assert(pq->phead != NULL); // 断言头节点不为空
  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--; // 队列大小减1

}

在这里插入图片描述

🌉获取队首元素函数

获取队列的队首元素，得首先确保队列不为空，然后返回队首节点中存储的数据。

QDataType QueueFront(Queue* pq)
 {
    assert(pq);
    assert(pq->phead != NULL);
    return pq->phead->data;
}

🌠获取队尾元素函数

获取队列的队尾元素，得首先确保队列不为空，然后返回队尾节点中存储的数据。

QDataType QueueBack(Queue* pq)
 {
    assert(pq);
    assert(pq->ptail != NULL);
    return pq->ptail->data;
}

🌉 判断队列是否为空函数

判断队列是否为空，通过检查队列的大小是否为0来确定队列是否为空。

bool QueueEmpty(Queue* pq) 
{
    assert(pq);
    return pq->size == 0;
}

🌉获取队列大小函数

获取队列的大小，即队列中元素的数量。

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

🌠测试

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "Queue.h" 

int main() 
{
    Queue queue;
    QueueInit(&queue);

    printf("Queue is empty: %s\n", QueueEmpty(&queue) ? "true" : "false");

    printf("Pushing elements into the queue...\n");
    for (int i = 1; i <= 5; ++i) 
    {
        printf("Pushing %d\n", i);
        QueuePush(&queue, i);
    }

    printf("Queue size: %d\n", QueueSize(&queue));
    printf("Queue front: %d\n", QueueFront(&queue));
    printf("Queue back: %d\n", QueueBack(&queue));

    printf("Popping elements from the queue...\n");
    while (!QueueEmpty(&queue)) 
    {
        printf("Front: %d\n", QueueFront(&queue));
        QueuePop(&queue);
    }

    printf("Queue is empty: %s\n", QueueEmpty(&queue) ? "true" : "false");

    QueueDestroy(&queue);

    return 0;
}

代码效果图：
在这里插入图片描述

🌉 总源代码

Queue.c

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	pq->phead = NULL; // 初始化头节点指针为空
	pq->ptail = NULL; // 初始化尾节点指针为空  
	pq->size = 0; // 初始化队列大小为0
}

void QueueDestroy(Queue* pq)
{

	assert(pq); // 断言队列指针是否为空
	QNode* cur = pq->phead; // cur指向队列头节点
	while (cur)
	{
		QNode* next = pq->phead->next; // 保存cur下一个节点的指针
		free(cur); // 释放cur节点内存
		cur = next; // cur指针移到下一个节点
	}
	pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
	pq->size = 0; // 重置队列大小为0

}



void QueuePush(Queue* pq, QDataType* x)
{
	assert(pq); // 断言队列指针是否为空
	QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新节点内存
	if (newnode == NULL)
	{ // 申请失败
		perror("malloc fail");
		return;
	}
	newnode->data = x; // 设置新节点数据
	newnode->next = NULL; // 设置新节点next指针为空

	if (pq->ptail)
	{ // 如果队列不为空
		pq->ptail->next = newnode; // 尾节点指向新节点
		pq->ptail = newnode; // 更新尾节点指针
	}
	else
	{ // 队列为空
		pq->phead = pq->ptail = newnode; // 头尾节点同时指向新节点
	}

	pq->size++; // 队列大小增加1

}

//出队列
void QueuePop(Queue* pq)
{

	assert(pq); // 断言队列指针是否为空
	if (pq->phead == NULL)
		return; // 队列为空直接返回

	assert(pq->phead != NULL); // 断言头节点不为空
	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--; // 队列大小减1

}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	assert(pq->phead != NULL);

	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	//暴力检查
	assert(pq->ptail != NULL);

	return pq->ptail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

🚩总结

请添加图片描述

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

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

相关文章

HTTPS：原理、使用方法及安全威胁

HTTPS：原理、使用方法及安全威胁

文章目录 一、HTTPS技术原理1.1 主要技术原理1.2 HTTPS的工作过程1.2.1 握手阶段1.2.2 数据传输阶段 1.3 HTTPS的安全性 二、HTTPS使用方法三、HTTPS安全威胁四、总结 HTTPS&#xff08;全称&#xff1a;Hyper Text Transfer Protocol over Secure Socket Layer&#xff09;&am…
阅读更多...
ARM：按键中断

ARM：按键中断

key_inc.c #include"key_inc.h"void key1_it_config(){//使能GPIOF外设时钟RCC->MP_AHB4ENSETR | (0x1<<5);//将PF9设置为输入模式GPIOF->MODER & (~(0x3<<18));//设置由PF9管脚产生EXTI9事件EXTI->EXTICR3 & (~(0XFF<<8));EXTI…
阅读更多...
【HarmonyOS】ArkUI - 页面路由

【HarmonyOS】ArkUI - 页面路由

一、概念 页面路由是指在应用程序中实现不同页面之间的跳转和数据传递。 案例&#xff1a;第一次使用某个购物应用&#xff0c;打开时肯定会是一个登录页&#xff0c;在登录成功以后&#xff0c;会跳转到首页&#xff0c;然后可能会去搜索&#xff0c;就会进入到搜索列表页&am…
阅读更多...
掌握Python中re模块的正则表达式应用与技巧【第155篇—正则表达式】

掌握Python中re模块的正则表达式应用与技巧【第155篇—正则表达式】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 掌握Python中re模块的正则表达式应用与技巧 Python 中的 re 模块是用于处理正则表达式的强…
阅读更多...
[SAP MM] 名词专业术语解释

[SAP MM] 名词专业术语解释

采购凭证 采购凭证通常是一种证明文件&#xff0c;用于记录和跟踪特定时间点的采购活动 采购凭证是指企业在采购物品或服务时所开立的一种凭证&#xff0c;用于记录采购的信息和流程 采购凭证通常包括采购申请、采购订单、采购合同等&#xff0c;其中采购订单是最常用的采购…
阅读更多...
PCB中常用电子器件封装学习——【一网打尽】

PCB中常用电子器件封装学习——【一网打尽】

‘ 上图是这个世界上大概所有的封装种类&#xff0c;当然我们日常硬件电路设计肯定用不到这么多&#xff0c;接下来我将介绍几种工程上常用的封装&#xff0c;配以图片方便大家理解学习。在电子器件选型的时候&#xff0c;避免选择到一些非常难以焊接的封装电子器件。
阅读更多...
Acrobat Pro DC ----专业PDF编辑与管理

Acrobat Pro DC ----专业PDF编辑与管理

Acrobat Pro DC 2023是一款功能强大的PDF处理软件&#xff0c;它提供了丰富的编辑工具&#xff0c;支持创建、编辑、合并、分割PDF文件&#xff0c;以及高质量的PDF到其他格式的转换功能。同时&#xff0c;该软件集成了最新的OCR技术&#xff0c;可将扫描文档或图片转换成可编辑…
阅读更多...
Godot 学习笔记(5)：彻底的项目工程化，解决GodotProjectDir is null+工程化范例

Godot 学习笔记(5)：彻底的项目工程化，解决GodotProjectDir is null+工程化范例

文章目录 前言GodotProjectDir is null解决方法解决警告问题根本解决代码问题测试引用其实其它库的输出路径无所谓。 工程化范例环境命名规范Nuget项目结构架构代码ISceneModelIOC服务 测试GD_Extension 通用扩展TestUtils GD_ProgramTestServiceMainSceneModel Godot对应的脚本…
阅读更多...
mac 解决随机出现的蓝色框

mac 解决随机出现的蓝色框

macbookair为什么打字的时候按空格键会出现蓝色框? - 知乎
阅读更多...
t-rex2开放集目标检测

t-rex2开放集目标检测

论文链接&#xff1a;http://arxiv.org/abs/2403.14610v1 项目链接&#xff1a;https://github.com/IDEA-Research/T-Rex 这篇文章的工作是基于t-rex1的工作继续做的&#xff0c;核心亮点&#xff1a; 是支持图片/文本两种模态的prompt进行输入&#xff0c;甚至进一步利用两…
阅读更多...
配置git公钥

配置git公钥

电脑重置重新配置公钥记录一下供自己观看 打开git bash 输入生成ssh公钥命令 ssh-keygen -t rsa -C your-email 一直回车直到出现 输入查看公钥命令 cat ~/.ssh/id_rsa.pub 复制公钥&#xff0c;打开git设置&#xff0c;找到ssh公钥添加(标题随便命名) 配置完后就可以正常使…
阅读更多...
【DataWhale学习】灵境Agent开发——Agent介绍

【DataWhale学习】灵境Agent开发——Agent介绍

【DataWhale学习】灵境Agent开发——Agent介绍 ​ 这次我参加了 DataWhale 的灵境Agent开发者训练营&#xff0c;第一次开发了一款属于自己的Agent&#xff0c;整体体验下来&#xff0c;操作还是非常方便的。灵境Agent和Coze上面创建的bot差不多&#xff0c;零代码开发可以仅仅…
阅读更多...
QT常见布局器使用

QT常见布局器使用

布局简介 为什么要布局&#xff1f;通过布局拖动不影响鼠标拖动窗口的效果等优点.QT设计器布局比较固定&#xff0c;不方便后期修改和维护&#xff1b;在Qt里面布局分为四个大类 &#xff1a; 盒子布局&#xff1a;QBoxLayout 网格布局&#xff1a;QGridLayout 表单布局&am…
阅读更多...
双指针（滑动窗口）-算法刷题

双指针（滑动窗口）-算法刷题

一.移动零&#xff08;. - 力扣&#xff08;LeetCode&#xff09;&#xff09; 算法思想 &#xff1a; 设置两个指针left,right&#xff0c;将数组分为三块[0,left]为不为0的元素&#xff0c;[left1,right-1]为0元素&#xff0c;[right,num.size()-1]为未扫描的区域&#xff0c…
阅读更多...
Notepad++ 如何调整显示字面大小

Notepad++ 如何调整显示字面大小

在 Notepad 上&#xff0c;可以使用 ctrl 加上鼠标的左键来滚动来进行调整。 如何恢复默 可以使用 Ctrl 加数字键盘上的 / 键 来恢复默认设置。 当然也可以通过菜单栏上 view 菜单下的 Zoom 选项。 上面的界面中可以看到我们的在 Notepad 中使用的选项。 Notepad 如何调整显示…
阅读更多...
stm32知识总结--简单复习各部件

stm32知识总结--简单复习各部件

目录 内部结构 部件介绍 配置步骤 之前学了很多部件&#xff0c;配置了很多参数&#xff0c;但是没有很系统地把他们连接在一起&#xff0c;今天这个图里简洁描述了资源与资源之间的关系。 内部结构 部件介绍 黑框部分为CPU、内部有一个内核专门处理事件&#xff0c;所有的…
阅读更多...
Android Studio 无法下载 gradle-7.3.3-bin.zip

Android Studio 无法下载 gradle-7.3.3-bin.zip

下载新的Android Studio&#xff0c;然后创建新的工程时&#xff0c;出现报错&#xff1a;Could not install Gradle distribution from https://services.gradle.org/distributions/gradle-7.3.3-bin.zip 或者超时&#xff0c;我们可以复制&#xff1a;https://services.grad…
阅读更多...
基于Google云原生工程师的kubernetes最佳实践（二）

基于Google云原生工程师的kubernetes最佳实践（二）

目录 二、应用部署篇 为deployment打上丰富的label,以便selecting 使用sidecar容器部署agent、proxy等组件 使用init container处理依赖关系,而不要用sidecar 镜像tag使用版本号,不要用latest或空tag 为pod设置readiness和liveness探针 不要给所有服务都使用LoadBalance…
阅读更多...
C++实现FFmpeg音视频实时拉流并播放

C++实现FFmpeg音视频实时拉流并播放

1.准备工作: 下载rtsp流媒体服务器rtsp-simple-server,安装go开发环境并编译 编译好后启动流媒体服务器 准备一个要推流的mp4视频文件,如db.mp4 使用ffmpeg开始推流 推流命令: ffmpeg -re -stream_loop -1 -i db.mp4 -c copy -rtsp_transport tcp -f rtsp rtsp://192.168.16…
阅读更多...
笔记本和台式机主板内部结构分析

笔记本和台式机主板内部结构分析

笔记本和态势机主板内存接口以及配件安装位置 笔记本主板 1 以thinkpad L-490为例,使用拆机小工具拆机&#xff0c;打开后面板&#xff0c;内部结构示意图如下 台式机主板 以技嘉-B660M-AORUS-PRO-AX型号主板为例 笔记本电脑和台式机电脑的相同之处 CPU&#xff1a;笔记本…
阅读更多...
最新文章

Copyright @ 2022~2023