队列 (Queue)

                                           

今日励志语句:别总听悲伤的歌,别总想从前的事,别让过去拖住脚,别让未来被辜负。

前言:前面写了一篇 栈的实现,接下来学习一下它的"兄弟"

 一、队列的概念:

队列:

        也是数据结构的一种,也属于特殊的线性表,是不是有点栈的味儿呢??它只允许一端插入数据,另一端删除数据,两个操作在两端进行,满足先进先出  FIFO(First In First Out )原则;因此它和它的好兄弟栈又恰恰相反,反目成仇了!

入队(Front):

                      进行插入操作的一端(队尾)

出队(Rear):

                        进行删除操作的一端(队头)

空队列:

                        不含任何数据

一个图就记住了!!!有点像水管,入管道的水,会先流出管道

流完了,数据也就都出去了

走安全出口,是不是先进去的先下去,后面的跟着在走,陆续出去

 队列的两种写法:

①顺序队列:在顺序表的基础上实现的队列结构。

        分配一块连续的存储单元存放队列中的元素,并附设两个指针:头指针 front指向队头元素,尾指针 rear 指向队尾元素的下一个位置(思考方向和栈类似,但是又有所不同)

②链队列:在链表的基础上实现的队列结构。

          分配一块逻辑上连续的存储单元存放列中的元素,并设2个指针:头指针指向队头的节点,尾指针指向队尾的节点(今天来实现它)

 两者的区别是在链表顺序表的区别,在物理空间上,数据集中存储就是顺序队列,数据分散存储就是链队列

二、设计队列和初始化队列:

设计:

从遵循的原则出发,队列是先进先出,那么我们可以写一个单链表

 头删尾插   实现即可

节点创建:变量a就是数据  next存下一个节点的指针

 但是我们发现我们要记录头和尾  ,为何不在建立一个结构体呢???专门保存头和尾

头和尾也是节点 用的类型是上面的Queue*

 这个结构体的成员就是节点的集合:

 头里面放了一个节点的地址,这个节点又会存放指向下一个节点的地址!!!拆开就是如此


头和尾的结构体

 提醒:我是写完了,写的过程发现了应该添加数据,所以给结构体成员再添加了一份子(记录数数)

 初始化:

 根据设计,我们要对Queue结构体操作:无非就是给个空指针,初始化数据个数!!

三、尾插:

和单链表尾插一样的,直接开写,就是得注意不要忘记判断一下,若尾节点是NULL,说明头与尾都还没有存节点,要先存一个

四、 头删:

删除头节点,头的位置就会不断向尾靠近,当到达尾时,需要同时给head和tail赋值NULL,不然会变成野指针  “野狗”

这里q->size的作用就用到了(不止这一个作用);判断数据个数是否为0,若是0,就是2个指针都指向了NULL,千万别忘记了NULL是不能被操作的

五、取头和取尾以及返回数据个数:

我的意思是取这个队列的队头和队尾,你排队的时候,想知道到你自己还有几个人吧?尾-头=还要等待的人数

注意函数返回类型:为存储的数据类型;

顺便加个数据个数:

 六、判空:

栈里面已经实现过了,万变不离其宗

若是数据个数为0,我就是传真,个数不为0,传假

七、销毁:

销毁的话,其实和单链表销毁一样,不论你有几个节点,我从头开始销毁,将所有节点所申请的空间还给操系统

销毁完以后,要注意的就是将头尾置空,毕竟被“野狗”咬一口可不好受啊

其实,在你用删除的时候,若是一个一个节点删完了,走完了 其实可以不要用到销毁这个函数,但是总有情况需要的,比如,你想清楚这个水管,把水闸关了,里面水瞬间没了(例子罢了,理解即可,勿较真)

 八、分装代码实现:

Queue.h头文件

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

typedef int QUDataType;
//节点
typedef struct QueueNode{
	
	QUDataType a;
	//一定要用指针,不然结构体的大小就无法确定了
	struct QueueNode *next;
}QuNode;
//再建立一个保存头和尾的结构体
typedef struct Queue {
	QuNode* head;
	QuNode* tail;
	int size;
}Queue;

//初始化头尾节点
void QuInto(Queue* q);
//尾插
void QuPush(Queue* q,QUDataType x);
//头删
void QuPop(Queue* q);
//判空
bool QuEmpty(Queue* q);
//数据个数
int QuSize(Queue* q);
//取头数据
QUDataType QuFront(Queue* q);
//取尾数据
QUDataType QuBack(Queue* q);
//销毁空间(写进数据,想要一次性释放完就来用)
void QuDestroy(Queue* q);

Queue.c源文件

#define _CRT_SECURE_NO_WARNINGS 3

#include"Queue.h"

//初始化头尾节点
void QuInto(Queue* q)
{
	//不能传空指针  即(q=NULL)
	assert(q);
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
}

//尾插(2种情况:1.头尾都为NUL  2.又数据入队列了)
void QuPush(Queue* q, QUDataType x)
{
	//申请空间
	QuNode* newnode = (QuNode*)malloc(sizeof(QuNode));
	//判空
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->a = x;
	newnode->next = NULL;//节点创建完成
	//判断尾的位置
	if (q->tail == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

//头删(删除到尾以后,就不能再删了)
void QuPop(Queue* q)
{
	assert(q);
	//头的位置也不能为空
	assert(q->size!=0);
	//此时数据个数为1(也就是最后一个节点)
	if (q->head->next==NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else//q->head != q->tail;
	{
		QuNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	
	//数据个数也要减去
	q->size--;
	
}

//判空
bool QuEmpty(Queue* q)
{
	assert(q);
	//头尾都相等时到达同一个位置,此时就为真,其他的情况都为假;
	return q->size==0;
}

//取头数据
QUDataType QuFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->a;
}

//取尾数据
QUDataType QuBack(Queue* q)
{
	assert(q);
	//队尾都为空了,已经没数据了
	assert(q->tail);
	return q->tail->a;
}
//数据个数
int QuSize(Queue* q)
{
	assert(q);
	return q->size;
}

//销毁空间(写进数据,想要一次性释放完就来用)
void QuDestroy(Queue* q)
{
	assert(q);
	QuNode* cur = q->head;
	while (cur)
	{
		QuNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail =NULL;
	q->size = 0;
}

tast.c源文件 

#define _CRT_SECURE_NO_WARNINGS 3

#include"Queue.h"

int main()
{
	Queue p;
	QuInto(&p);
	QuPush(&p,1);
	QuPush(&p, 2);
	QuPush(&p, 3);
	QuPush(&p, 4);
	while (!QuEmpty(&p))
	{
		printf("%d ", QuFront(&p));
		QuPop(&p);
	}
	//可写可不写。因为上面循环的时候会释放掉所有申请的空间
	//QuDestroy(&p);

	return 0;
}

鉄汁们,你们的三连就是对博主最大的支持!!!

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

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

相关文章

C++类和对象(三) 缺省值 | static成员 | 内部类

前言&#xff1a; 这是关于类和对象的最后一篇文章&#xff0c;当然还是基础篇的最后一篇&#xff0c;因为类的三大特性继承&#xff0c;封装和多态都还没有讲&#xff0c;少年&#xff0c;慢慢来。 缺省值&#xff1a; 之前讲过&#xff0c;在C11的新标准中&#xff0c;支持为…

百面算法工程师 | 支持向量机面试相关问题——SVM

本文给大家带来的百面算法工程师是深度学习支持向量机的面试总结&#xff0c;文章内总结了常见的提问问题&#xff0c;旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中&#xff0c;我们还将介绍一些常见的深度学习算法工程师面试问题&#xff0c;并提供参考的回答…

哈夫曼编码python算法实现(图片版)

一、问题&#xff1a; 请使用哈夫曼编码方法对给定的字符串&#xff0c;进行编码&#xff0c;以满足发送的编码总长度最小&#xff0c;且方便译码。“AABBCCDDEEABCDDCDBAEEAAA” 二、过程&#xff1a; 三、结果&#xff1a;

软件1班20240509

文章目录 1.JDBC本质2.增3.改4.删5.查6.JDBC标准写法 1.JDBC本质 重写 接口的 方法 idea 报错 – 不动脑 alt enter 知道没有重写方法 CTRL o 重写 方法 快捷键 package com.yanyu;/*** Author yanyu666_508200729qq.com* Date 2024/5/9 14:42* description:*/ public interf…

网安学习路线终极指南!一步步带你从入门到精通,详尽技能点全解析!

目录 零基础小白&#xff0c;到就业&#xff01;入门到入土的网安学习路线&#xff01; 建议的学习顺序&#xff1a; 一、夯实一下基础&#xff0c;梳理和复习 二、HTML与JAVASCRIPT&#xff08;了解一下语法即可&#xff0c;要求不高&#xff09; 三、PHP入门 四、MYSQL…

(三十七)第 6 章 树和二叉树(二叉树的二叉链表存储表示实现)

1. 背景说明 2. 示例代码 1) errorRecord.h // 记录错误宏定义头文件#ifndef ERROR_RECORD_H #define ERROR_RECORD_H#include <stdio.h> #include <string.h> #include <stdint.h>// 从文件路径中提取文件名 #define FILE_NAME(X) strrchr(X, \\) ? st…

欧洲杯/奥运会-云直播

欧洲杯/奥运会要来了&#xff0c;如何升级自己的网站让你的顾客都能观赏直播已提高用户量呢&#xff1f;&#xff01; 【功能完善、平滑兼容】 云直播支持 RTMP 推流、 HLS 源站等多种直播源接入方式&#xff0c;提供直播 SDK&#xff0c;支持多终端适配&#xff0c;上行码率…

蓝桥杯省三爆改省二,省一到底做错了什么?

到底怎么个事 这届蓝桥杯选的软件测试赛道&#xff0c;都说选择大于努力,软件测试一不卷二不难。省赛结束&#xff0c;自己就感觉稳啦&#xff0c;全部都稳啦。没想到一出结果&#xff0c;省三&#xff0c;g了。说落差&#xff0c;是真的有一点&#xff0c;就感觉和自己预期的…

LeetCode例题讲解:只出现一次的数字

给你一个 非空 整数数组 nums &#xff0c;除了某个元素只出现一次以外&#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题&#xff0c;且该算法只使用常量额外空间。 示例 1 &#xff1a; 输入&#xff…

JavaSwing课程设计-实现一个计算器程序

通过JavaSwing技术来实现计算器小程序&#xff0c;效果如下。 源码下载链接 源码下载 博主承诺真实有效&#xff0c;私信可提供支持

独家新闻:CSCWD 2024会议现场即时报道 天津之眼夜色如梦

会议之眼 快讯 备受瞩目的第27届国际计算机协同计算与设计大会&#xff08;CSCWD 2024&#xff09;于2024年5月8日在中国天津梅江中心皇冠假日酒店盛大开幕&#xff01;来自世界各地的专家学者齐聚一堂&#xff0c;共同探讨和分享在智能设计、制造和协同工作领域的最新研究成果…

【全开源】Java上门洗车小程序源码上门洗车APP 小程序源码支持二次开发6.0

功能特点&#xff1a; 跨界创新&#xff1a;融入科技元素&#xff0c;借助移动互联网快速发展&#xff0c;将科技引入到传统洗车业中。 科技赋能&#xff1a;具有智能化的特点&#xff0c;用户可以根据自身的需求选择不同的洗车项目和服务&#xff0c;包括洗车的时间、地点和服…

MFC实现点击列表头进行排序

MFC实现点击列表头排序 1、添加消息处理函数 在列表窗口右键&#xff0c;类向导。选择 IDC_LIST1&#xff08;我的列表控件的ID&#xff09;&#xff0c;消息选择LVN_COLUMNCLICK。 2、消息映射如下 然后会在 cpp 文件中生成以下函数 void CFLashSearchDlg::OnLvnColumnclic…

IPFoxy:什么是静态住宅IP?静态ISP代理指南

静态住宅代理&#xff08;也称为静态ISP代理&#xff09;是最流行的代理类型之一。它们也是隐藏您的身份并保持在线匿名的最佳方法之一。您为什么要使用住宅代理而不是仅使用常规代理服务&#xff1f;下面我具体分享。 一、什么是静态住宅代理&#xff1f; 首先&#xff0c;我…

Hotcoin Research | 模块化将是大势所趋:拆解模块化区块链的现状和未来

关于模块化区块链叙事的讨论源于Celestia和其代币TIA的亮眼表现。实际上&#xff0c;模块化是未来区块链设计的主要发展方向和大势所趋。模块化区块链就像乐高积木一样&#xff0c;将区块链系统拆分为可重用的模块&#xff0c;通过定制组合可实现不同功能的区块链网络。这种灵活…

Leetcode—2079. 给植物浇水【中等】

2024每日刷题&#xff08;130&#xff09; Leetcode—2079. 给植物浇水 实现代码 class Solution { public:int wateringPlants(vector<int>& plants, int capacity) {int ans 0;int step 0;int cap capacity;bool flag false;for(int i 0; i < plants.siz…

C语言-整体内容简单的认识

目录 一、数据类型的介绍二、数据的变量和常量三、变量的作用域和生命周期四、字符串五、转义字符六、操作符六、常见的关键字6.1 关键字static 七、内存分配八、结构体九、指针 一、数据类型的介绍 sizeof是一个操作符&#xff0c;是计算机类型/变量所占内存空间的大小   sc…

在做题中学习(52): 山脉数组的峰顶索引

852. 山脉数组的峰顶索引 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a;二分查找 思路&#xff1a;O(logn)的时间复杂度&#xff0c;很可能是二分法&#xff0c;再看看有没有二段性&#xff1a; 由题目可以知道&#xff0c;i的左边比i小&#xff0c;右边比i大&am…

【Java基础】设计模式——单例设计模式

单例设计模式&#xff08;Singleton Design Pattern&#xff09;是一种创建型设计模式&#xff0c;它确保⼀个类有且只有⼀个实例&#xff0c;并提供一个全局访问点来访问这个唯一实例。 单例模式主要解决的是&#xff0c;⼀个全局使⽤的类频繁的创建和消费&#xff0c;从⽽提…

2-6 任务 猜数小游戏(单次版)

本任务要求编写一个猜数小游戏&#xff08;单次版&#xff09;&#xff0c;游戏规则是计算机产生一个0到100之间的随机整数&#xff0c;用户通过输入猜测的数字进行猜测&#xff0c;根据猜测情况给出提示&#xff0c;直到猜对为止。编程思路是利用while循环和多分支结构实现永真…