【数据结构初阶第十节】队列(详解+附源码)

 好久不见。。。别不开心了,听听喜欢的歌吧

必须有为成功付出代价的决心,然后想办法付出这个代价。云边有个稻草人-CSDN博客

目录

一、概念和结构

二、队列的实现

Queue.h

Queue.c

 test.c

Relaxing Time!

————————————《有没有那么一首歌会让你想起我》————————————


这节课我们学习队列的概念和结构以及实现,需要提前具备前面顺序表和链表的相关知识,这样这节课就会变得非常简单!

一、概念和结构

概念: 只允许在⼀端进行插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
入队列: 进行 插⼊操作的⼀端称为队尾。
出队列: 进行 删除操作的⼀端称为队头。
队列底层结构选型 : 队列也可以数组和链表的结构实现,使⽤链表的结构实现更优⼀些,因为如果使⽤数组的结构,出队列在数组头上出数据,效率会⽐较低。
下图解释为什么用链表来实现队列

二、队列的实现

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//创建节点的结构
typedef int QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//创建队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;//队列里面有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QUDatatype x);//出队列
void QueuePop(Queue* pq);//取队头数据
QUDatatype QueueFront(Queue* pq);//取队尾数据
QUDatatype QueueBack(Queue* pq);//取队列有效元素个数
int QueueSize(Queue* pq);//销毁
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq,QUDatatype x)
{assert(pq);//申请一个新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}++pq->size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);//下面这样写也ok,return pq->phead == NULL && pq->ptail == NULL ;return pq->phead == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//若只有一个结点,防止ptail成为野指针if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除对头元素QueueNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;}--pq->size;
}//取队头数据
QUDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//取队列有效元素个数,时间复杂度为O(N),我们可以优化一下
//我们可以增加一个变量size去记录队列里面有效数据的个数然后直接返回
int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}//针对队列里面的结构进行销毁pq->phead = pq->ptail = NULL;pq->size = 0;
}

 test.c

#include"Queue.h"void test()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);/*QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);*/printf("head:%d\n", QueueFront(&pq));printf("back:%d\n", QueueBack(&pq));//两种 取队列里面有效数据的个数 方法printf("队列里面有效数据个数为:%d \n",QueueSize(&pq));printf("size:%d\n", QueueSize(&pq));printf("size:%d\n", pq.size);QueueDestroy(&pq);}int main()
{test();return 0;
}

实现队列需要注意的比较重要的点见下

  1. 取队列里面有效数据的个数,如果用老方法套路实现时间复杂度为O(N),但是我们可以在队列里面重新定义一个结构,size来记录,每次入数据,出数据直接调整size即可,取有效数据个数的时候直接返回 size 就简单了很多。
  2. 在队列销毁的时候,不要忘记最后把队列结构里面的phead和ptail指针置为NULL,size == 0。
  3. 我们定义了ptail指针,指向队尾,可以直接找到队尾入数据。

经过前几节顺序表,单链表,双链表,栈的学习,今天学习队列真是游刃有余呦,下一节是栈和队列的算法题,期待一下啦~~

完——


Relaxing Time!

————————————《 有没有那么一首歌会让你想起我 ————————————

有没有一首歌会让你想起我_HENRY刘宪华_高音质在线试听_有没有一首歌会让你想起我歌词|歌曲下载_酷狗音乐

至此结束!

我是云边有个稻草人

期待与你的下一次相遇。。。

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

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

相关文章

AVL树:高效平衡的二叉搜索树

&#x1f31f; 快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。&#x1f31f; 引言&#x1f914; 在数据结构的奇妙世界里&#xff0c;二叉搜索树&#xff08;BST&#xff09;原本是查找数据的好帮手。想象一下…

Qt Designer菜鸟使用教程(实现一个本地英文翻译软件)

1 安装Qt Designer 安装这个包的时候会自带安装 Qt Designer, 安装目录为python的安装根目录的 Lib/site-packages/qt5_applications/Qt/bin 目录下。 pip install pyqt5-tools2 新建窗体 2.1 新建主窗体 创建之后如下图&#xff1a; 设置主窗口大小&#xff1a; 设置窗…

机械学习基础-5.分类-数据建模与机械智能课程自留

data modeling and machine intelligence - CLASSIFICATION 为什么我们不将回归技术用于分类&#xff1f;贝叶斯分类器&#xff08;The Bayes Classifier&#xff09;逻辑回归&#xff08;Logistic Regression&#xff09;对逻辑回归的更多直观理解逻辑 /sigmoid 函数的导数我们…

C++ 网络编程

1. socket Socket 是一种用于网络通信的编程接口&#xff0c;它提供了一种类似于文件描述符的接口&#xff0c;允许不同计算机之间的进程进行通信。Socket 可以工作在多种协议上&#xff0c;最常用的是 TCP/IP 和 UDP/IP 协议 1.1 UDP 1.1.1 概念 UDP&#xff08;用户数据报协…

C/C++内存管理

目录 前言 1、C/C内存划分 2、C语言中的动态内存管理方式 3、C内存管理方式 3.1操作内置类型 3.2操作自定义类型 3.3为什么对应的new和delete必须搭配使用&#xff08;了解&#xff09; 4、operator new与operator delete函数 5、new和delete的实现原理 5.1内置类型 5…

微软开源GraphRAG的使用教程-使用自定义数据测试GraphRAG

微软在今年4月份的时候提出了GraphRAG的概念&#xff0c;然后在上周开源了GraphRAG,Github链接见https://github.com/microsoft/graphrag,截止当前&#xff0c;已有6900Star。 安装教程 官方推荐使用Python3.10-3.12版本&#xff0c;我使用Python3.10版本安装时&#xff0c;在…

RK3568平台开发系列讲解(调试篇)网卡队列均衡负载

🚀返回专栏总目录 文章目录 一、RPS 的介绍1. RPS 的工作原理2. RPS 配置3. 启用和调优 RPS4. RPS 优势二、下行测试iperf测试沉淀、分享、成长,让自己和他人都能有所收获!😄 RPS(Receive Packet Steering) 是一种用于提高网络接收性能的技术,通常用于多核处理器系统中…

RagFlow + Docker Desktop + Ollama + DeepSeek-R1本地部署自己的本地AI大模型工具

前期准备 首先&#xff0c;我们需要下载 Ollama 以及配置相关环境。 Ollama 的 GitHub仓库 &#xff08;https://github.com/ollama/ollama&#xff09;中提供了详细的说明&#xff0c;简单总结如下: Step1&#xff1a;下载 Ollama 下载&#xff08;https://ollama.com/dow…

变分边界详解

起因 当时看VAE论文时有这么一段&#xff0c;但是看完直接一头雾水&#xff0c;这都那跟哪&#xff0c;第一个公式咋做的变换就变出那么一堆。网上搜了很多博客都语焉不详&#xff0c;只好自己来写一篇&#xff0c;希望能解答后来人的疑惑。 公式1 参考文章&#xff1a;证据…

云消息队列 ApsaraMQ Serverless 演进:高弹性低成本、更稳定更安全、智能化免运维

如今&#xff0c;消息队列已成为分布式架构中不可或缺的关键服务&#xff0c;为电商、物联网、游戏和教育等行业&#xff0c;提供了异步解耦、集成、高性能和高可靠的核心价值。 过去一年&#xff0c;我们发布了云消息队列 ApsaraMQ 全系列产品 Serverless 化&#xff0c;面向…

【蓝桥杯嵌入式】8_IIC通信-eeprom读写

全部代码网盘自取 链接&#xff1a;https://pan.baidu.com/s/1PX2NCQxnADxYBQx5CsOgPA?pwd3ii2 提取码&#xff1a;3ii2 1、电路图 这个电路允许通过I2C总线与EEPROM(M24C02-WMN6TP)和数字电位器(MCP4017T-104ELT)进行通信。EEPROM用于存储数据&#xff0c;而数字电位器可以用…

DeepSeek处理自有业务的案例:让AI给你写一份小众编辑器(EverEdit)的语法着色文件

1 DeepSeek处理自有业务的案例&#xff1a;让AI给你写一份小众编辑器(EverEdit)的语法着色文件 1.1 背景 AI能力再强&#xff0c;如果不能在企业的自有业务上产生助益&#xff0c;那基本也是一无是处。将企业的自有业务上传到线上训练&#xff0c;那是脑子进水的做法&#xff…

Java常用设计模式面试题总结(内容详细,简单易懂)

设计模式的分类 创建型模式&#xff1a;通过隐藏对象创建的细节&#xff0c;避免直接使用 new 关键字实例化对象&#xff0c;从而使程序在判断和创建对象时更具灵活性。常见的模式包括&#xff1a; 工厂模式抽象工厂模式单例模式建造者模式原型模式 结构型模式&#xff1a;通…

使用HX搭建UNI-APP云开发项目(适合新手小白与想学云开发的宝子)

什么是uni-app云开发 uni-app云开发是uni-app提供的一套后端服务,它可以帮助开发者快速搭建起一个完整的后端服务,包括数据库、云函数、存储等。开发者只需要关注前端页面的开发,后端服务由uni-app云开发提供。 uni-app云开发的优势: 快速搭建后端服务:uni-app云开发提供了…

零基础学CocosCreator·第九季-网络游戏同步策略与ESC架构

课程里的版本好像是1.9&#xff0c;目前使用版本为3.8.3 开始~ 目录 状态同步帧同步帧同步客户端帧同步服务端ECS框架概念ECS的解释ECS的特点EntityComponentSystemWorld ECS实现逻辑帧&渲染帧 ECS框架使用帧同步&ECS 状态同步 一般游戏的同步策略有两种&#xff1a;…

最新版Edge浏览器集成ActiveX控件之金山WpsDocFrame控件

背景 WpsDocFrame控件‌是由金山公司开发的ActiveX控件&#xff0c;主要用于OA系统中&#xff0c;支持在浏览器中嵌入WPS文档的查看和编辑功能。 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有…

Win10系统IP地址修改_出现了一个意外的情况不能完成所有你在设置中所要求的更改---Windows工作笔记001

今天在修改win10系统中的ip地址的时候报错了 来看看如何解决吧,挺简单,简单记录一下 这个时候就需要使用cmd命令来修改 一定要使用,管理员权限,运行cmd才可以 然后首先: 输入 netsh 然后输入 ip 然后输入: set address "以太网" 172.19.126.199 255.255.255.0…

算法 ST表

目录 前言 一&#xff0c;暴力法 二&#xff0c;打表法 三&#xff0c;ST表 四&#xff0c;ST表的代码实现 总结 前言 ST表的主要作用是在一个区间里面寻找最大值&#xff0c;具有快速查找的功能&#xff0c;此表有些难&#xff0c;读者可以借助我的文章和网上的课程结…

node.js+兰空图床实现随机图

之前博客一直用的公共的随机图API&#xff0c;虽然图片的质量都挺不错的&#xff0c;但是稳定性都比较一般&#xff0c;遂打算使用之前部署的兰空图床&#xff0c;自己弄一个随机图 本文章服务器操作基于雨云——新一代云服务提供商的云服务器进行操作&#xff0c;有兴趣的话可…

CNN|ResNet-50

导入数据 import matplotlib.pyplot as plt # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 plt.rcParams[axes.unicode_minus] False # 用来正常显示负号import os,PIL,pathlib import numpy as npfrom tensorflow import keras from tensor…