当前位置: 首页 > news >正文

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

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

必须有为成功付出代价的决心,然后想办法付出这个代价。云边有个稻草人-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刘宪华_高音质在线试听_有没有一首歌会让你想起我歌词|歌曲下载_酷狗音乐

至此结束!

我是云边有个稻草人

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

相关文章:

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

好久不见。。。别不开心了&#xff0c;听听喜欢的歌吧 必须有为成功付出代价的决心&#xff0c;然后想办法付出这个代价。云边有个稻草人-CSDN博客 目录 一、概念和结构 二、队列的实现 Queue.h Queue.c test.c Relaxing Time&#xff01; ————————————《有没…...

沪深300股指期权能对股指期货进行完全套保吗?

锦鲤三三每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 沪深300股指期权能对股指期货进行完全套保吗&#xff1f; 沪深300股指期权是以沪深300指数为标的物的期权&#xff0c;而沪深300股指期货则是以该指数作为标的的期货合约。 理…...

JAVA学习第三天

继承关系变量访问的特点 01.方法中找 02.子类变量定义中找 03.父类中找 this和super关键字的使用区别&#xff1a; super父类构造函数的使用&#xff1a; 使用子类构造函数时&#xff0c;都会初始化父类的数据&#xff0c;自动调用父类的无参构造函数 super内存图——007 继…...

win11电脑其他WiFi可以连,只有一个WiFi连不上

这个问题卡了一小会&#xff0c;查了一些资料 后面发现 点击“诊断网络问题” 显示没有响应 第一步 重启wlan网络适配器 解决&#xff01;&#xff01;&#xff01; 重新连接那个有问题的wifi&#xff0c;丝滑连接&#xff01;...

leetcode_1760 袋子里最少数目的球

1. 题意 给定一个数组&#xff0c;和一个最多次操作次数。每次操作可以将数组中的一个数 x x x分成两个数 t x − t t\quad x-t tx−t。问 m a x O p e r a t i o n C n t maxOperationCnt maxOperationCnt次操作后&#xff0c;数组中最大的数最小的值是多少。 2. 题解 这个…...

Python 面向对象的三大特征

前言&#xff1a;本篇讲解面向对象的三大特征&#xff08;封装&#xff0c;继承&#xff0c;多态&#xff09;&#xff0c;还有比较细致的&#xff08;类属性类方法&#xff0c;静态方法&#xff09;&#xff0c;分步骤讲解&#xff0c;比较适合理清楚三大特征的思路 面向对象的…...

Linux下的进程切换与调度

目录 1.进程的优先级 优先级是什么 Linux下优先级的具体做法 优先级的调整为什么要受限 2.Linux下的进程切换 3.Linux下进程的调度 1.进程的优先级 我们在使用计算机的时候&#xff0c;通常会启动多个程序&#xff0c;这些程序最后都会变成进程&#xff0c;但是我们的硬…...

面向对象程序设计-实验六

7-1 函数重载&#xff08;数据类型不同&#xff09; 代码清单&#xff1a; #include<iostream> using namespace std; class axxx { public: void px(int n,int a[]) { for(int i0;i<n;i) { for(int j0;j<n-i-1;j) { int t; if(a[j]>a[j1]) { ta[j]; a[j…...

MongoDB 7 分片副本集升级方案详解(上)

#作者&#xff1a;任少近 文章目录 前言&#xff1a;Mongodb版本升级升级步骤环境1.1环境准备1.2standalone升级1.3分片、副本集升级 前言&#xff1a;Mongodb版本升级 在开始升级之前&#xff0c;请参阅 MongoDB下个版本中的兼容性变更文档&#xff0c;以确保您的应用程序和…...

【工业安全】-CVE-2022-35555- Tenda W6路由器 命令注入漏洞

文章目录 1.漏洞描述 2.环境搭建 3.漏洞复现 4.漏洞分析 4.1&#xff1a;代码分析  4.2&#xff1a;流量分析 5.poc代码&#xff1a; 1.漏洞描述 漏洞编号&#xff1a;CVE-2022-35555 漏洞名称&#xff1a;Tenda W6 命令注入 威胁等级&#xff1a;高危 漏洞详情&#xff1…...

算法分析 ——《模拟》

文章目录 《替换所有的问号》题目描述&#xff1a;代码演示&#xff1a;代码解析&#xff1a; 《提莫攻击》题目描述&#xff1a;代码演示&#xff1a;代码解析&#xff1a; [《Z 字形变换》](https://leetcode.cn/problems/zigzag-conversion/)题目描述&#xff1a;代码演示&a…...

将Sqlite3数据库挂在内存上处理

创作灵感&#xff1a;最近把小学生的口算题从2位数改到3位数&#xff0c;100以内四则运算练习&#xff08;千纬数学&#xff09;再次更新&#xff0c;选取难题-CSDN博客要不断刷题目&#xff0c;以前100以内的加减乘除也是这样刷出来的&#xff0c;代码如下&#xff1a; impor…...

前端大屏适配方案:从设计到实现的全流程指南

引言 随着数据可视化需求的增长&#xff0c;大屏展示项目在前端开发中越来越常见。然而&#xff0c;大屏开发面临独特的挑战&#xff1a; 屏幕分辨率多样&#xff1a;从1080P到4K甚至8K&#xff0c;如何保证清晰度&#xff1f;布局复杂&#xff1a;多图表、多组件如何合理排列…...

学习总结三十二

map #include<iostream> #include<map> using namespace std;int main() {//首先创建一个map对象map<int, char>oneMap;//插入数据oneMap.insert(pair<int, char>(1, A));oneMap.insert(make_pair(2,B));oneMap.insert(map<int,char>::value_ty…...

飞书专栏-TEE文档

CSDN学院课程连接&#xff1a;https://edu.csdn.net/course/detail/39573...

linux 查看设备中的摄像头迅速验证设备号

​ 通常&#xff0c;摄像头在系统中会被识别为/dev/video*设备文件&#xff0c;比如/dev/video0、/dev/video1等。用户可能有多个摄像头&#xff0c;比如内置摄像头和外接USB摄像头&#xff0c;这时候每个摄像头会被分配不同的设备号。 1. 列出所有摄像头设备 方法 1&#xf…...

2.8 企业级训练数据构造革命:从人工标注到GPT智能标注的工业级实践指南

企业级训练数据构造革命:从人工标注到GPT智能标注的工业级实践指南 引言:数据标注——AI模型的基石与瓶颈 据2024年AI行业报告显示,高质量标注数据的获取成本占模型开发总成本的62%,且标注错误导致的模型性能下降可达40%。本文将揭示如何结合大模型能力,构建支持千万级数…...

DeepSeek的蒸馏技术:让模型推理更快

DeepSeek系列模型&#xff0c;如DeepSeek-R1-Distill-Qwen-7B&#xff0c;采用了知识蒸馏&#xff08;Knowledge Distillation&#xff09;技术&#xff0c;这是一种强大的模型压缩和优化方法。通过蒸馏&#xff0c;DeepSeek模型在保持甚至提升性能的同时&#xff0c;实现了更快…...

19.4.6 读写数据库中的二进制数据

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 需要北风数据库的请留言自己的信箱。 北风数据库中&#xff0c;类别表的图片字段在【数据表视图】中显示为Bitmap Image&#xff1…...

如何在 Elasticsearch 中设置向量搜索 - 第二部分

作者&#xff1a;来自 Elastic Valentin Crettaz 了解如何在 Elasticsearch 中设置向量搜索并执行 k-NN 搜索。 本文是三篇系列文章中的第二篇&#xff0c;深入探讨了向量搜索&#xff08;也称为语义搜索&#xff09;的复杂性以及它在 Elasticsearch 中的实现方式。 第一部分重…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...