【数据结构】千字深入浅出讲解队列(附原码 | 超详解)

在这里插入图片描述

🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:C语言实现数据结构
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

文章目录

  • 前言
  • 一、队列的概念
  • 二、队列的结构
  • 三、队列的实现
    • 3.1结构体的定义
    • 3.2函数接口
    • 3.3初始化
    • 3.4销毁
    • 3.5入队列
    • 3.6出队列
    • 3.7计算队列大小
    • 3.8判断队列是否为空
    • 3.9取对头元素
    • 3.10取队尾元素
  • 四、队列的总代码
  • 总结


前言

今天打算给大家讲解队列这一个知识点,会把函数接口一一列举出来 并且 依次实现,这样才会更加牢固的掌握队列这一基本数据结构,话不多说,让我们一起来学习吧。


一、队列的概念

队列 链表都是一种线性表结构。

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出

FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头

数据结构图如下:
在这里插入图片描述

二、队列的结构

队列可以使用 数组链表实现,但是二者之间有不同的地方,哪一个更加适合队列呢?

我想:使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数
组头上出数据,效率会比较低

在这里插入图片描述

三、队列的实现

3.1结构体的定义

typedef char QDatatype;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDatatype data;
}QNode;

由于链表的尾插比较麻烦,而队列的入数据为尾插。所以定义队列的结构体时,可以定义两个指针 head tail 分别对应 队头 和 队尾 ,tail 的引入就是方便尾插再在给定一个 size 实时记录队列的大小。


typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

3.2函数接口

void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//销毁
void QueuePush(Queue* pq,QDatatype x);//入队列
void QueuePop(Queue* pq);//出队列
int QueueSize(Queue* pq);//计算队列大小
bool QueueEmpty(Queue* pq);//判断队列是否为空
QDatatype QueueFront(Queue* pq);//取对头元素
QDatatype QueueBack(Queue* pq);//取队尾元素

3.3初始化

要领: 队列对头队尾相等都为NULL,且size=0;

void QueueInit(Queue* pq)
{
    //暴力检查
    assert(pq);

    pq->head=pq->tail=NULL;
    pq->size=0;
}

3.4销毁

要领:cur不断遍历,然后free节点,最后处理headtail即可;

void QueueDestroy(Queue* pq)
{
    assert(pq);

    Queue* cur=pq->head;
    while(cur)
    {
        Queue* tmp=cur->next;
        free(cur);
        cur=tmp;
    }
    pq->head=pq->tail=NULL;
    pq->size=0;
}

3.5入队列

要领: 尾节点(tail)进行插入;

void QueuePush(Queue* pq,QDatatype x)
{
    Queue* newnode=(Queue*)malloc(sizeof(Queue));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data=x;
    newnode->nxet=NULL;
    
    if(pq->head=NULL)
    {
        assert(pq->tail==NULL)
        pq->head=pq->tail=newnode;
    }
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
    pq->size++;
}

3.6出队列

要领: 找到原本头节点的下一个节点 更换一下新的头节点就好了,注意free就行

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head!=NULL);

    Queue* tmp=pq->head->next;
    free(pq->head);
    pq->head=tmp;

    if(pq->head==NULL)
    {
        pq->tail=NULL;
    }
    pq->size--;
}

3.7计算队列大小

要领: 返回size的大小即可;

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

3.8判断队列是否为空

要领: 其实本质就是看size是否为0;

bool QueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->size==0;
}

3.9取对头元素

要领: 队列非空,取 head 出数据

QDatatype QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->head->data;
}

3.10取队尾元素

要领: 队列非空,取 tail 处数据。

QDatatype QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->tail->data;
}

四、队列的总代码

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

typedef char QDatatype;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDatatype data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);

//--------------------------手动分割线---------------------------
//初始化
void QueueInit(Queue* pq)
{
    //暴力检查
    assert(pq);

    pq->head=pq->tail=NULL;
    pq->size=0;
}
//--------------------------手动分割线---------------------------
//销毁
void QueueDestroy(Queue* pq)
{
    assert(pq);

    Queue* cur=pq->head;
    while(cur)
    {
        Queue* tmp=cur->next;
        free(cur);
        cur=tmp;
    }
    pq->head=pq->tail=NULL;
    pq->size=0;
}
//--------------------------手动分割线---------------------------

void QueuePush(Queue* pq,QDatatype x)
{
    Queue* newnode=(Queue*)malloc(sizeof(Queue));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data=x;
    newnode->nxet=NULL;
    
    if(pq->head=NULL)
    {
        assert(pq->tail==NULL)
        pq->head=pq->tail=newnode;
    }
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
    pq->size++;
}
//--------------------------手动分割线---------------------------

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head!=NULL);

    Queue* tmp=pq->head->next;
    free(pq->head);
    pq->head=tmp;

    if(pq->head==NULL)
    {
        pq->tail=NULL;
    }
    pq->size--;
}
//--------------------------手动分割线---------------------------

int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}
//--------------------------手动分割线---------------------------

bool QueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->size==0;
}
//--------------------------手动分割线---------------------------

QDatatype QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->head->data;
}
//--------------------------手动分割线---------------------------

QDatatype QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->tail->data;
}

在这里插入图片描述
在这里插入图片描述

总结

  今天学习了单链表的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将多画图,多敲代码来学习,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。

  我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬能一键三连支持一下博主,hhhh~我们下期见喽
在这里插入图片描述
如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下

👍 点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!

⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!

✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!

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

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

相关文章

javaweb实习实训管理系统mysql

本毕业设计基于JSP的实习实训管理系统&#xff0c;本系统能实现网上的实习实训信息管理&#xff0c;主要功能有&#xff1a;添加用户、查看用户、管理用户、添加实验室、查看实验室、管理实验室、添加课程、查看课程、管理课程、添加教学、查看教学、管理教学、添加实习、查看实…

STM32的推挽输出和开漏输出

文章目录 前言一、推挽输出二、开漏输出三、区别和适应场景总结前言 本篇文章将带大家了解STM32的推挽输出和开漏输出,并且学习这两个的区别,学习分别在什么时候使用这两个不同的输出方式。 在 STM32 微控制器中,GPIO(General Purpose Input/Output)模块是一个通用的输入…

Java 到底是值传递还是引用传递?

C 语言是很多变成语言的母胎&#xff0c;包括 Java。对于 C 语言来说&#xff0c;所有的方法参数都是通过 “值” 传递的&#xff0c;也就是说&#xff0c;传递给被调用方法的参数值存放在临时变量中&#xff0c;而不是存放在原来的变量中。这就意味着&#xff0c;被调用的方法…

项目质量管理工作 不得不重视的4大关键点

1、三大视角确保项目质量 我们需要从客户视角、SOW视角和组织视角三大视角&#xff0c;确保项目的质量。 从客户视角方面出发&#xff0c;满足客户的要求&#xff0c;如项目交付的准时性、项目质量的保证等。我们需要全力保障客户对项目质量的要求。 从SOW视角确保项目质量&…

[ 漏洞复现篇 ] Joomla未授权访问Rest API漏洞(CVE-2023-23752)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…

Java实习生------MySQL10道面试题打卡

今日语录&#xff1a;“没有执行力&#xff0c;就没有竞争力 ”&#x1f339; 参考资料&#xff1a;图解MySQL、MySQL面试题 1、事务有哪些特性&#xff1f; 原子性&#xff1a; 一个事务中的所有操作&#xff0c;要么全部完成&#xff0c;要么全部不完成&#xff0c;不会出现…

Three.js——learn01

Three.js——learn01Three.js——learn01本地搭建文档通过parcel搭建Threejs环境1.初始化2.安装parcel设置打包位置3.设置目录结构QuickStart安装threejsindex.htmlindex.cssindex.js启动Three.js——learn01 本地搭建文档 登录GitHub搜索three.js git clone https://github…

基于数据安全的沙盘推演体系

背景 2022年由IBM和Ponemon研究所联合发布的一份全球性的研究报告&#xff0c;分析了550家遭受数据泄露事件的组织的各种成本和影响因素。根据报告&#xff0c;2022年全球数据泄露规模和平均成本均创下历史新高&#xff0c;数据泄露事件的平均成本高达435万美元&#xff0c;比2…

C语言—文件操作

1.为什么使用文件使用文件可以直接将数据存放到电脑硬盘上&#xff0c;做到数据的持久化2.什么是文件硬盘上的文件是文件但在程序中&#xff0c;我们一般谈的文件有两种&#xff1a;程序文件和数据文件&#xff08;从文件功能角度来分类的&#xff09;2.1程序文件包括源程序文件…

vue3使用vee-validate自定义表单校验,提交实现步骤

1、首先安装vee-validate&#xff08;指定版本&#xff09;&#xff0c;安装命令如下&#xff1a; npm i vee-validate4.0.32、在app.vue中写入如下内容&#xff1a;用vee-validate提供的Form组件代替form标签&#xff0c;用Field组件代替input标签&#xff0c;errors是接收校…

UnixBench----x86架构openEuler操作系统上进行性能测试

【原文链接】UnixBench----x86架构openEuler操作系统上进行性能测试 &#xff08;1&#xff09;打开github上 UnixBench 地址&#xff0c;找到发布的tag &#xff08;2&#xff09;找到tar.gz包&#xff0c;右键复制链接 比如这里是 https://github.com/kdlucas/byte-unix…

1、OSI模型

目录 一、OSI模型 二、TCP / IP 模型 (协议簇&#xff09; 1、TCP/IP简介 2、自下而上了解TCP/IP协议&#xff1a; &#xff08;网络接口和物理层&#xff09; 3、TCP/IP协议其他知识点 三、基本知识点 1、socket——插座 2、为什么需要socket 3、什么是socket 4、IP地…

【数据结构】夯实基础|线性表刷题01

作者&#xff1a;努力学习的大一在校计算机专业学生&#xff0c;热爱学习和创作。目前在学习和分享&#xff1a;算法、数据结构、Java等相关知识。博主主页&#xff1a; 是瑶瑶子啦所属专栏: 【数据结构|刷题专栏】&#xff1a;该专栏专注于数据结构知识&#xff0c;持续更新&a…

【三维几何学习】从零开始网格上的深度学习-3:Transformer篇(Pytorch)

本文参加新星计划人工智能(Pytorch)赛道&#xff1a;https://bbs.csdn.net/topics/613989052 从零开始网格上的深度学习-3:Transformer篇引言一、概述二、核心代码2.1 位置编码2.2 网络框架三、基于Transformer的网格分类3.1 分类结果3.2 全部代码引言 本文主要内容如下&#…

linux中写定时任务

场景&#xff1a;我们生产环境中有大量的日志记录&#xff0c;但是我们的磁盘没有太大&#xff0c;需要定时清理磁盘 文章目录crond 定时任务详解安装定时任务crontab服务启动与关闭crontab操作crontab 命令test.sh查看日志丢弃linux中的执行日志Linux进入nano模式方式一方式二…

Unreal Engine 网络系统(四):UEC++的RPC

目录 行为同步 On Server&#xff1a;服务端的RPC代码 On Client&#xff1a;客户端的RPC代码 NetMulticast&#xff1a;广播的RPC代码 属性同步 行为同步 借助UFUNCTION进行函数标记 UFUNCTION(Server)&#xff1a;声明一个在客户端调用&#xff0c;在服务端执行的函数U…

测试老鸟都在用的接口抓包常用工具以及接口测试工具都有哪些?

目录 接口 接口测试的重要性 常用抓包工具 常用接口测试工具 接口 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换&#xff0c;传递和控制管理过程&#xff0c;以及系统间…

pkg打包node项目到linux中运行

首先看一下pkg的一些基本操作 pkg打包node项目为exe_node静态项目 导出exe_疆~的博客-CSDN博客由于win7最高只支持node13.14.0&#xff0c;而pkg不支持node13&#xff0c;为了既兼容win7&#xff0c;又能使用pkg打包&#xff0c;故使用node12.22.11。新建node_global和node_ca…

这一次,吃了Redis的亏,也败给了GPT

关注【离心计划】&#xff0c;一起离开地球表面 背景 组内有一个系统中有一个延迟任务的需求&#xff0c;关于延迟任务常见的做法有时间轮、延迟MQ还有Redis Zset等方案&#xff0c;关于时间轮&#xff0c;这边小苏有一个大学时候做的demo&#xff1a; https://github.com/JA…

好用的5款国产低代码平台介绍

一、云程低代码平台 云程低代码平台是一款基于springboot、vue.js技术的企业级低代码开发平台&#xff0c;平台采用模型驱动、高低码融合、开放扩展等设计理念&#xff0c;基于业务建模、流程建模、表单建模、报表建模、大屏建模等可视化建模工具&#xff0c;通过拖拉拽零代码方…
最新文章