【C语言】链式队列的实现

队列基本概念

首先我们要了解什么是队列,队列里面包含什么。

队列是线性表的一种是一种先进先出(First In Fi Out)的数据结构。在需要排队的场景下有很强的应用性。有数组队列也有链式队列,数组实现的队列时间复杂度太大,一般链式队列应用更为广泛。

队列里面包括队头和队尾。出队列只能在队头出(头删),入队列只能在队尾入(尾插)。

本篇要实现是单向,不带哨兵位,不循环的用链表实现的队列(此种队列应用较为广泛)

队列的定义

包括一个数据和指向下一个节点的指针

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;

对队列的操作

入队列与出队列

如果只有头指针那我们还是需要遍历队列才能找到队列的队尾进行入队列,而且还需要传二级指针。但是如果还有尾指针那就不需要遍历找尾,效率更高,多个指针用结构体封装,只传一级指针即可

当然在执行出入队列前我们应该先把队列初始化,但是由于说清楚为什么不用二级指针和应该有头尾指针,初始化放在后面了。

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

考虑到需要计算队列长度,所以在Queue结构中还加了size成员。

具体实现如下

入队列

void QueuePush(Queue* pq, QDataType x)
{assert(pq);//在队尾入,尾插//创建新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;//空链表if (QueueEmpty(pq)){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

此处要考虑队列为空和队列不为空两种情况,队列为空则新插入的节点即为队列的队头和队尾;

队列不为空,则队尾的next指针指向新节点,新节点成为新的队尾。

判空

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

出队列

void QueuePop(Queue* pq)
{assert(pq);//零个节点assert(pq->phead);//一个节点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--;
}

出队列要保证队头不能为空,所以要加assert(pq->phead)语句来暴力检查,队列中如果只有一个节点那么释放掉头队头节点后,把队头和队尾都置为空即可;若有多个节点,先要把队头指向的下一个节点存起来,以防释放掉队头后找不到他的下一个节点,然后让原本队头的下一个节点成为新的队头。

初始化

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

取队头数据

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

取队尾数据

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

队列长度

size_t QueueLength(Queue* pq)
{assert(pq);return pq->size;
}

销毁

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;
}

完整总代码

头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//取队头
QDataType QueueFront(Queue* pq);
//取队尾
QDataType QueueBack(Queue* pq);
//队列长度
size_t QueueLength(Queue* pq);

函数定义

#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = 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;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//在队尾入,尾插//创建新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;//空链表if (QueueEmpty(pq)){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//出队列
void QueuePop(Queue* pq)
{assert(pq);//零个节点assert(pq->phead);//一个节点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--;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//取队头
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//取队尾
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
//队列长度
size_t QueueLength(Queue* pq)
{assert(pq);return pq->size;
}

测试

#include"Queue.h"
void test()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);while (!QueueEmpty(&pq)){printf("%d ", QueueFront(&pq));QueuePop(&pq);}QueueDestroy(&pq);
}
int main()
{test();return 0;
}

欢迎各位大佬一起学习交流~

有不当之处欢迎指正~

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】链式二叉树的实现和思路分析及二叉树OJ

【数据结构】链式二叉树的实现和思路分析及二叉树OJ &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;数据结构 文章目录 【数据结构】链式二叉树的实现和思路分析及二叉树OJ前言一.链式二叉树的定义及结构二.链式二叉树的遍历2.1前序遍历2.2中…

Typora 【最新1.8.6】版本安装下载教程 (轻量级 Markdown 编辑器),图文步骤详解,免费领取(软件可激活使用)

文章目录 软件介绍软件下载安装步骤激活步骤 软件介绍 Typora 是一款专为 Markdown 爱好者设计的文本编辑器&#xff0c;它结合了简洁的界面设计与强大的 Markdown 渲染能力&#xff0c;为用户提供了一个流畅、高效的写作环境。以下是对 Typora 更详细的介绍&#xff1a; 核心特…

课程学习前提约束(拓扑排序练习)

很显然的拓扑排序 class Solution { public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int n numCourses;vector<int> record(n1,0);queue<int> q;vector<vector<int>> graph(n 1);for (int i 0; i &l…

nfs和web服务器的搭建

&#xff08;一&#xff09;web服务器的搭建 1.配置基本环境 要点有&#xff0c;yum源&#xff0c;包含nginx和阿里云&#xff08;或者腾讯云或者华为云&#xff09;&#xff0c;这里的相关知识可以参考之前的yum配置笔记 2.安装nginx yum -y install nginx 3.验证并且开启服…

源码编译安装,及nginx服务控制、监控块

1.源码编译安装&#xff1a; [root17dns ~]# wget https://nginx.org/download/nginx-1.27.0.tar.gz 2.解压&#xff1a; [root17dns ~]# tar -zxvf nginx-1.27.0.tar.gz 3.安装gcc等工具 [root17dns ~]# yum -y install gcc gcc-c [root17dns ~]# yum -y install make lrzsz …

24年第三届钉钉杯大学生大数据挑战赛浅析

需要完整资料&#xff0c;请关注WX&#xff1a;“小何数模”&#xff01; 本次钉钉杯大数据挑战赛的赛题已正式出炉&#xff0c;无论是赛题难度还是认可度&#xff0c;该比赛都是仅次于数模国赛的独一档&#xff0c;可以用于国赛前的练手训练。考虑到大家解题实属不易&#xf…

如何学习Doris:糙快猛的大数据之路(从入门到专家)

引言:大数据世界的新玩家 还记得我第一次听说"Doris"这个名字时的情景吗?那是在一个炎热的夏日午后,我正在办公室里为接下来的大数据项目发愁。作为一个刚刚跨行到大数据领域的新手,我感觉自己就像是被丢进了深海的小鱼—周围全是陌生的概念和技术。 就在这时,我的…

Django实战:开启数字化任务管理的新纪元

&#x1f680; Django实战&#xff1a;开启数字化任务管理的新纪元 &#x1f310; &#x1f4d6; 引言 在数字化转型的浪潮中&#xff0c;任务管理的智能化成为提升组织效能的关键。今天&#xff0c;我将带领大家深入了解我们最新开发的OFTS系统——一款创新的组织任务管理软…

双指针-【3,4,5,6,7,8】

第三题&#xff1a;快乐数 . - 力扣&#xff08;LeetCode&#xff09;. - 备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/happy-number/算法思想&#xff1a; 1.每个…

SpringBoot上传超大文件导致OOM,完美解决办法

问题描述 上传大文件报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] …

调用百度的大模型API接口实现AI对话!手把手教程!

本文介绍如何使用百度的大模型API接口实现一个AI对话项目 1 注册百度云 2 获取API接口 3 配置环境 4 代码编写与运行 5 chat models 1 注册百度云 搜索百度云&#xff0c;打开官网注册&#xff0c;充值一点点大米&#xff08;收费很低&#xff0c;大概生成几个句子花费一毛…

FRP配置内网穿透52版本以上适用

简述 适用frp配置内网穿透来说我们需要进行简单的区分&#xff0c;具有公网IP的服务器我们简称为服务端&#xff0c;内网的服务器我们可以简称为客户端&#xff0c;frp需要针对不同的服务器配置不同的文件 下载安装包 Linux下载地址 https://github.com/fatedier/frp/relea…

好的STEM编程语言有哪些?

STEM是科学&#xff08;Science&#xff09;&#xff0c;技术&#xff08;Technology&#xff09;&#xff0c;工程&#xff08;Engineering&#xff09;&#xff0c;数学&#xff08;Mathematics&#xff09;四门学科英文首字母的缩写&#xff0c;STEM教育简单来说就是在通过在…

如何通过✅ IPIDEA代理IP,轻松实现数据采集和市场拓展工作(下)

如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作 如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作前言IPIDEA爬虫实战实战Demo演示总结 如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作 前言 在当今全球化市场的…

微信小游戏之三消(三)道具相关方法

设计一个 game class。负责了游戏的核心控制逻辑&#xff0c;包括游戏状态管理、方块和道具的生成与效果处理&#xff0c;以及游戏的重新开始和复活流程。通过这些方法&#xff0c;脚本实现了游戏的基本玩法和用户交互。 主要游戏控制方法 gameStart()&#xff1a;开始游戏&am…

MySQL常见指令

MySQL中的数据类型 大致分为五种&#xff1a;数值&#xff0c;日期和时间&#xff0c;字符串&#xff0c;json&#xff0c;空间类型 每种类型也包括也一些不同的子类型&#xff0c;根据需要来选择。 如数值类型包括整数类型和浮点数类型 整数类型根据占用的存储空间的不同 又…

Cocos Creator2D游戏开发(7)-飞机大战(5)-让子弹飞

飞机大战(5)-碰撞及积分 参考敌机的生成 子弹由飞机生成,放在player_node节点子弹重复使用,要使用预制体;子弹新增了动画 ①创建一个预制体 命名为playerBullet_prefab ② 双击预制体将bullet1图片拖入预制体 保存,关闭(场景编辑器里面的) ③ 发射子弹 player加入代码 prop…

听说它可以让代码更优雅

一提到静态代码检查工具这个词应该比较好理解&#xff0c;所谓静态代码检查工具就是检查静态代码的工具&#xff0c;完美~ 言归正传&#xff0c;相信很多程序员朋友都听说过静态代码检查工具这个概念&#xff0c;它可能是我们IDE里的某一个插件&#xff0c;可能是计算机中的一…

RK3588+MIPI+GMSL+AI摄像机:自动车载4/8通道GMSL采集/边缘计算盒解决方案

RK3588作为目前市面能买到的最强国产SOC&#xff0c;有强大的硬件配置。在智能汽车飞速发展&#xff0c;对图像数据矿场要求越来越多的环境下&#xff0c;如何高效采集数据&#xff0c;或者运行AI应用&#xff0c;成为刚需。 推出的4/8通道GMSL采集/边缘计算盒产品满足这些需求…