队列的讲解

队列的概念

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头

一端进另一端出

也就是可以做到，先进先出

队列的使用场景

队列的经典应用就是保持公平性

比如：抽号机

生产者消费者模型，先来先出去，多线程的话就可能涉及到一个锁的概念

广度优先遍历（概念）

直接好友：好友

间接好友：好友的好友

可以采取队列的方式推荐

队列如何实现

数组的无法实现的因为需要一边进一边出，所以一般是单链表实现队列

同时单链表也会更加省空间

队列的实现 

创建文件

首先我们需要知道单链表实现队列的时候，我们需要有头节点和尾结点，以及链表的实际的个数，所以我们不能在结构体里面创建那麽多结构体，所以我们采取结构体的嵌套

创建栈的结构

// 链式结构：表示队列 
typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;
// 队列的结构 （因为队列是先进先出，后进后出，也就是和栈是相反的，此时会尾进头出，所以我们需要更新尾部和头部节点）
// (把头结点，尾结点，链表的实际的大小放里面，这样不需要每次使用的时候进行循环找尾，我们只需要每次更新尾结点就可以)
typedef struct Queue
{
	QNode* _phead;//头节点
	QNode* _ptail;//尾结点
	int size;
}Queue;

这段代码定义了两个结构体，QNode 和 Queue，分别用于表示队列中的节点和整个队列。下面是对每个部分的详细解释：

  1. QNode 结构体：这个结构体表示队列中的单个节点。

    • _data：这是 QNode 结构体中的一个成员变量，用来存储节点中的数据。QDataType 是数据类型的别名，它应该在相关的头文件中定义，代表节点存储的数据类型。
    • _next：这是一个指向 QNode 类型的指针，用来指向同一队列中的下一个节点。如果 _next 为 NULL，表示这是队列中的最后一个节点。

  2. Queue 结构体：这个结构体表示整个队列。

    • _phead：这是一个指向 QNode 类型的指针，用来指向队列的头节点。队列的头节点是最早被加入的节点，也是下一个将要被移除的节点。
    • _ptail：这是一个指向 QNode 类型的指针，用来指向队列的尾节点。队列的尾节点是最后被加入的节点，它用于在添加新元素时更新队列。
    • size：这是一个整数类型的变量，用来存储队列中当前的元素数量。

在队列的链式表示中，不需要像顺序表示（使用数组）那样进行动态内存分配和缩容。链式结构自然地允许队列的动态增长和缩减，因为每个节点独立维护其后继节点的指针。

队列的基本操作包括：

  • 入队（Enqueue）：在队尾添加一个新节点。
  • 出队（Dequeue）：移除队头的节点，并返回其数据。
  • 查看队头（Peek/Front）：返回队头节点的数据但不移除它。
  • 检查队列是否为空（IsEmpty）：检查队列的头节点是否为 NULL。

初始化与销毁队列

// 初始化队列 
void QueueInit(Queue* ps)
{
	ps->_phead = NULL;
	ps->_ptail = NULL;
	ps->size = 0;
}
// 销毁队列 
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->_phead;
	while (cur)
	{
		//存下下一个节点的地址，不会出现找空的情况
		QNode* next = cur->_next;
		free(cur);
		cur =next;
	}
}

  1. QueueInit 函数：

    • 这个函数接收一个指向 Queue 结构体的指针 ps。
    • ps->_phead = NULL;：将队列的头节点指针设置为 NULL。这表示队列初始化时是空的，没有任何元素。
    • ps->_ptail = NULL;：将队列的尾节点指针也设置为 NULL。由于队列是空的，头尾节点都不存在。
    • ps->size = 0;：设置队列中元素的数量为0。

  2. QueueDestroy 函数：

    • 这个函数同样接收一个指向 Queue 结构体的指针 ps。
    • assert(ps);：使用 assert 宏来确保传入的 ps 不是 NULL。如果 ps 是 NULL，assert 将触发断言失败，这有助于避免对空指针的无效操作。
    • QNode* cur = ps->_phead;：声明一个 QNode 类型的指针 cur 并初始化为队列的头节点。
    • while (cur)：使用 while 循环来遍历队列，直到 cur 为 NULL，即队列中的所有节点都被处理完毕。
    • QNode* next = cur->_next;：在释放当前节点之前，先保存下一个节点的地址，以便在释放当前节点后能够继续遍历队列。
    • free(cur);：使用 free 函数释放当前节点 cur 所占用的内存。
    • cur = next;：将 cur 更新为下一个节点，继续循环直到所有节点都被释放。
    • 循环结束后，队列中的所有节点都被释放，此时队列被销毁。

队尾入队列 

// 队尾入队列 
void QueuePush(Queue* ps, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush:newnode:error:");
		exit(1);
	}
	//把需要插入的数值插入到节点里面
	newnode->_next = NULL;
	newnode->_data = x;
	
	// ps->_phead == ps->_ptail 的结果确实是 true，这表明队列中只有一个元素（头尾相接）。
	// 但是，通常情况下，我们不会使用 ps->_phead == ps->_ptail 
	// 来检查队列中是否只有一个元素。相反，我们通常会使用 ps->size == 1 或者 ps->_phead != NULL && ps->_ptail != NULL 
	// 来检查队列中是否只有一个元素。

	//插入节点 第一个节点,这里的判断是不能写成ps->_phead ==ps->_ptail；因为都是空指针不能进行比较
	//ps->_phead == NULL
	if (ps->size == 0)
	{
		ps->_phead = ps->_ptail = newnode;
	}
	else
	{
		//尾插节点
		ps->_ptail->_next = newnode;
		ps->_ptail= newnode;
	}
	ps->size++;
}

这段代码定义了一个名为 QueuePush 的函数，用于在队列的尾部添加一个新的元素。

  1. void QueuePush(Queue* ps, QDataType x)：函数定义开始，QueuePush 接收一个指向 Queue 结构体的指针 ps 和一个要入队的新数据 x。

  2. QNode* newnode = (QNode*)malloc(sizeof(QNode));：使用 malloc 函数为新节点分配内存。newnode 是指向新分配内存的指针。

  3. if (newnode == NULL)：检查 malloc 是否成功分配了内存。如果 newnode 是 NULL，表示内存分配失败。

  4. perror("QueuePush:newnode:error:");：如果内存分配失败，使用 perror 函数输出错误信息。

  5. exit(1);：如果内存分配失败，调用 exit 函数以非零状态码退出程序。

  6. newnode->_next = NULL;：将新节点的 _next 指针设置为 NULL。这是新节点的尾部标识，表示在新节点之后没有更多的节点。

  7. newnode->_data = x;：将新数据 x 存储在新节点的 _data 成员中。

  8. if (ps->size == 0)：检查队列是否为空（即队列中的元素数量为0）。

  9. ps->_phead = ps->_ptail = newnode;：如果是空队列，那么新节点同时是头节点和尾节点。因此，将头节点和尾节点指针都指向 newnode。

  10. else：如果队列不是空的，执行以下操作：

    • ps->_ptail->_next = newnode;：将当前尾节点的 _next 指针指向新节点，从而将新节点添加到队列的末尾。
    • ps->_ptail = newnode;：更新尾节点指针，使其指向新节点。

  11. ps->size++;：队列中元素的数量增加1。

这段代码实现了队列的尾部入队操作。它首先检查队列是否为空，然后相应地将新节点添加到队列的末尾，并更新尾节点指针和队列的元素数量。如果内存分配失败，程序将输出错误信息并退出。

队头出队列 

// 队头出队列 
void QueuePop(Queue* ps)
{
	assert(ps && ps->size);
	// 改变头结点
	ps->_phead = ps->_phead->_next;
	ps->size--;
}

这段代码定义了一个名为 QueuePop 的函数，其目的是从队列头部移除一个元素。

  1. #include"Queue.h"：这行代码应该位于文件的顶部，用于引入包含 Queue 结构体和 QNode 结构体定义以及 QDataType 类型定义的头文件。

  2. void QueuePop(Queue* ps)：函数定义开始，QueuePop 接收一个指向 Queue 结构体的指针 ps 作为参数。

  3. assert(ps && ps->size);：assert 是一个宏，用于在运行时测试一个条件是否为真。如果条件为假，则 assert 将产生一个断言失败，通常会导致程序异常终止。在这里，它用于确保传入的队列指针 ps 不是 NULL，并且队列中至少有一个元素（即 ps->size 大于0）。

  4. ps->_phead = ps->_phead->_next;：这行代码将队列的头节点指针 _phead 更新为指向下一个节点，从而移除当前队列头部的节点。由于队列是先进先出（FIFO）的数据结构，队头节点是将要被移除的节点。

  5. ps->size--;：队列中元素的数量减少1。

这段代码实现了队列的头部出队操作。它首先通过 assert 检查队列是否非空，然后将头节点指针移动到下一个节点，以此出队操作，最后更新队列的元素数量。

获取队列头部元素

// 获取队列头部元素 
QDataType QueueFront(Queue* ps)
{
	assert(ps && ps->size);
	return ps->_phead->_data;
}

  1. QueueFront 函数：

    • 这个函数接收一个指向 Queue 结构体的指针 ps。
    • assert(ps && ps->size);：使用 assert 宏确保传入的队列指针 ps 不是 NULL，并且队列中至少有一个元素（即 ps->size 大于0）。
    • return ps->_phead->_data;：返回队列头部节点的 _data 成员。由于队列是先进先出（FIFO）的数据结构，队头节点的 _data 成员包含了最早被加入的元素的值。

获取队列队尾元素 

// 获取队列队尾元素 
QDataType QueueBack(Queue* ps)
{
	assert(ps && ps->size);
	return ps->_ptail->_data;
}

  1. QueueBack 函数：

    • 这个函数同样接收一个指向 Queue 结构体的指针 ps。
    • assert(ps && ps->size);：使用 assert 宏确保传入的队列指针 ps 不是 NULL，并且队列中至少有一个元素。
    • return ps->_ptail->_data;：返回队列尾部节点的 _data 成员。在链式队列中，尾部节点是最后一个被加入的节点，其 _data 成员包含了最近一个被加入的元素的值。

获取队列中有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* ps)
{
	return ps->size;
}

  1. QueueSize 函数：

    • 这个函数接收一个指向 Queue 结构体的指针 ps。
    • return ps->size;：返回队列中有效元素的个数，即 size 成员的值。

检测队列是否为空，如果为空返回非零结果，如果非空返回0 

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* ps)
{
	assert(ps);
	return ps->size == 0;
}

QueueEmpty 函数：

  • 这个函数接收一个指向 Queue 结构体的指针 ps。
  • assert(ps);：使用 assert 宏确保传入的队列指针 ps 不是 NULL。
  • return ps->size == 0;：检查队列是否为空。如果 size 成员的值等于0，则表示队列为空，函数返回非零值（在C语言中，非零值被视为“真”），否则返回0（“假”）

 队列代码的总结 

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;
// 队列的结构 （因为队列是先进先出，后进后出，也就是和栈是相反的，此时会尾进头出，所以我们需要更新尾部和头部节点）
// (把头结点，尾结点，链表的实际的大小放里面，这样不需要每次使用的时候进行循环找尾，我们只需要每次更新尾结点就可以)
typedef struct Queue
{
	QNode* _phead;//头节点
	QNode* _ptail;//尾结点
	int size;
}Queue;
// 这里采取一级指针进行实现代码逻辑，如果不创建队列的结构，我们就需要采取二级指针
// 初始化队列 
void QueueInit(Queue* ps);
// 销毁队列 
void QueueDestroy(Queue* ps);
// 队尾入队列 
void QueuePush(Queue* ps, QDataType data);
// 队头出队列 
void QueuePop(Queue* ps);
// 获取队列头部元素 
QDataType QueueFront(Queue* ps);
// 获取队列队尾元素 
QDataType QueueBack(Queue* ps);
// 获取队列中有效元素个数 
int QueueSize(Queue* ps);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* ps);

Queue.c

#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* ps)
{
	ps->_phead = NULL;
	ps->_ptail = NULL;
	ps->size = 0;
}
// 销毁队列 
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->_phead;
	while (cur)
	{
		//存下下一个节点的地址，不会出现找空的情况
		QNode* next = cur->_next;
		free(cur);
		cur =next;
	}
}
// 队尾入队列 
void QueuePush(Queue* ps, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush:newnode:error:");
		exit(1);
	}
	//把需要插入的数值插入到节点里面
	newnode->_next = NULL;
	newnode->_data = x;
	
	// ps->_phead == ps->_ptail 的结果确实是 true，这表明队列中只有一个元素（头尾相接）。
	// 但是，通常情况下，我们不会使用 ps->_phead == ps->_ptail 
	// 来检查队列中是否只有一个元素。相反，我们通常会使用 ps->size == 1 或者 ps->_phead != NULL && ps->_ptail != NULL 
	// 来检查队列中是否只有一个元素。

	//插入节点 第一个节点,这里的判断是不能写成ps->_phead ==ps->_ptail；因为都是空指针不能进行比较
	//ps->_phead == NULL
	if (ps->size == 0)
	{
		ps->_phead = ps->_ptail = newnode;
	}
	else
	{
		//尾插节点
		ps->_ptail->_next = newnode;
		ps->_ptail= newnode;
	}
	ps->size++;
}
// 队头出队列 
void QueuePop(Queue* ps)
{
	assert(ps && ps->size);
	// 改变头结点
	ps->_phead = ps->_phead->_next;
	ps->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* ps)
{
	assert(ps && ps->size);
	return ps->_phead->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* ps)
{
	assert(ps && ps->size);
	return ps->_ptail->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* ps)
{
	return ps->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* ps)
{
	assert(ps);
	return ps->size == 0;
}

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

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

相关文章

[BJDCTF 2020]easy_md5、[HNCTF 2022 Week1]Interesting_include、[GDOUCTF 2023]泄露的伪装

[BJDCTF 2020]easy_md5、[HNCTF 2022 Week1]Interesting_include、[GDOUCTF 2023]泄露的伪装

目录 [BJDCTF 2020]easy_md5 ffifdyop [SWPUCTF 2021 新生赛]crypto8 [HNCTF 2022 Week1]Interesting_include php://filter协议 [GDOUCTF 2023]泄露的伪装 [BJDCTF 2020]easy_md5 尝试输入一个1&#xff0c;发现输入的内容会通过get传递但是没有其他回显 观察一下响应…
阅读更多...
数据结构与算法-排序算法3-插入排序

数据结构与算法-排序算法3-插入排序

目录 1.插入排序&#xff1a; 1.介绍&#xff1a; 2.动态图解 3.举例 4.小结插入排序规则 5.插入排序代码 6.运行时间 代码&#xff1a; 运行结果&#xff1a; 1.插入排序&#xff1a; 1.介绍&#xff1a; 数组中n个元素&#xff0c;把这n个待排序元素看成一个有序序…
阅读更多...
深度学习：光流估计新范式

深度学习：光流估计新范式

0.概述 在这篇文章中&#xff0c;我们将讨论两种基于深度学习的光流运动估计方法。FlowNet是第一个用于计算光流的CNN方法&#xff0c;RAFT是当前最先进的估计光流的方法。我们还将看到如何使用作者提供的经过训练的模型来使用PyTorch对新数据进行推断。 1. FlowNet FlowNet…
阅读更多...
读人工智能时代与人类未来笔记03_演变

读人工智能时代与人类未来笔记03_演变

1. 演变 1.1. 每个社会都找到了属于自己的一套适应世界的方法 1.1.1. 适应的核心&#xff0c;是有关人类心智与现实之间关系的概念 1.1.2. 人类认识周围环境的能力 1.1.2.1. 这种能力通过知识获得&#xff0c;同时也受到知识…
阅读更多...
CentOS 安装 SeaweedFS

CentOS 安装 SeaweedFS

1. SeaweedFS 介绍 SeaweedFS 是一个简单且高度可扩展的分布式文件系统。有两个目标&#xff1a; to store billions of files! (存储数十亿个文件&#xff01;)to serve the files fast! (快速提供文件&#xff01;) Seaweedfs的中心节点&#xff08;center master&#xff09…
阅读更多...
电容笔记汇总

电容笔记汇总

电容 一、电容理论基础 1、电容的本质 两个相互靠近的导体&#xff0c;中间夹一层不导电的绝缘介质&#xff0c;这就构成了电容器。当电容器的两个极板之间加上电压时&#xff0c;电容器就会储存电荷。 两个相互靠近的金属板中间夹一层绝缘介质组成的器件&#xff0c;当两端…
阅读更多...
JeeSite Vue3：前端开发页面如何动态设置菜单展示模式？

JeeSite Vue3：前端开发页面如何动态设置菜单展示模式？

推荐阅读&#xff1a; JeeSite Vue3&#xff1a;前端开发的未来之路(更新版) 随着技术的飞速发展&#xff0c;前端开发技术日新月异。在这个背景下&#xff0c;JeeSite Vue3 作为一个基于 Vue3、Vite、Ant-Design-Vue、TypeScript 和 Vue Vben Admin 的前端框架&#xff0c;引…
阅读更多...
研发管理之认识DevOps

研发管理之认识DevOps

文章目录 一、什么是DevOps二、DevOps的背景和起源三、DevOps的特点和价值1、特点&#xff1a;2、价值&#xff1a; 四、DevOps如何帮助提高软件交付速度和质量 一、什么是DevOps DevOps&#xff08;Development和Operations的组合词&#xff09;是一组过程、方法与系统的统称…
阅读更多...
Sketch总结

Sketch总结

sketch禁用了lineGap https://www.sketch.com/docs/designing/text/ http://www.sketchcn.com/sketch-chinese-user-manual.html https://github.com/sketch-hq/sketch-document https://developer.sketch.com/file-format/ https://animaapp.github.io/sketch-web-viewer/ htt…
阅读更多...
Python | Leetcode Python题解之第89题格雷编码

Python | Leetcode Python题解之第89题格雷编码

题目&#xff1a; 题解&#xff1a; class Solution:def grayCode(self, n: int) -> List[int]:ans [0] * (1 << n)for i in range(1 << n):ans[i] (i >> 1) ^ ireturn ans
阅读更多...
C++基础与深度解析 | 表达式 | 操作符

C++基础与深度解析 | 表达式 | 操作符

文章目录 一、表达式基础1.表达式的值类别2.表达式的类型转换 二、表达式详述1.算术操作符2.逻辑与关系操作符3.位操作符4.赋值操作符5.自增与自减运算符6.其他操作符三、C17对表达式的求值顺序的限定 一、表达式基础 表达式由一到多个操作数组成&#xff0c;可以求值并 ( 通常…
阅读更多...
2024年5月面试准备

2024年5月面试准备

2024年5月面试准备 资料来源Java基础泛型注解异常反射SPI机制Java集合CollectionMap 并发基础线程并发关键字并发集合Lock核心类并发集合核心类原子类核心类线程池核心类ScheduledThreadPoolExecutorForkJoinPoolFokJoinTask JUC原子类: CAS, Unsafe和原子类详解JUC 工具类 Jav…
阅读更多...
Nginx 生产环境部署的最佳实践

Nginx 生产环境部署的最佳实践

你好呀&#xff0c;我是赵兴晨&#xff0c;文科程序员。 最近一段时间&#xff0c;我一直在和大家一起探讨Nginx的相关话题。期间&#xff0c;我收到了很多小伙伴的私信&#xff0c;他们好奇地问我&#xff1a;在生产环境中&#xff0c;Nginx应该如何配置&#xff1f; 他们在…
阅读更多...
LeetCode题练习与总结：不同的二叉搜索树--96

LeetCode题练习与总结：不同的二叉搜索树--96

一、题目描述 给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;5示例 2&#xff1a; 输入&#xff1a;n 1 输出&…
阅读更多...
平衡三进制小数详解与进制转换

平衡三进制小数详解与进制转换

标准三进制是“逢三进一&#xff0c;退一还三”的机制&#xff0c;平衡三进制与之类似&#xff0c;但就是偏移了一下变得对称了&#xff0c;平衡三进制与标准三进制可以相互转换&#xff0c;但这样显得有点多余了&#xff0c;所以这里只讲平衡三进制与十进制的转换。 数字系统的…
阅读更多...
_pickle.UnpicklingError: STACK_GLOBAL requires str

_pickle.UnpicklingError: STACK_GLOBAL requires str

导致这个报错的原因是我跑yolo的时候修改数据集了&#xff0c;里面的label.cache没有删除&#xff0c;咱只要删除掉缓存就行&#xff01;&#xff01; 我这里是已经删除掉了&#xff0c;所以图片里面没有&#xff0c;一般就是在箭头所示位置有.cache文件的
阅读更多...
Python 全栈体系【四阶】（四十三）

Python 全栈体系【四阶】（四十三）

第五章 深度学习 九、图像分割 3. 常用模型 3.4 DeepLab 系列 3.4.1 DeepLab v1(2015) 3.4.1.1 概述 图像分割和图像分类不一样&#xff0c;要对图像每个像素进行精确分类。在使用CNN对图像进行卷积、池化过程中&#xff0c;会导致特征图尺寸大幅度下降、分辨率降低&…
阅读更多...
windows驱动开发-PCI和中断(二)

windows驱动开发-PCI和中断(二)

谈到中断使用PCI总线来作为例子是最合适的&#xff0c;在Windows发展过程中&#xff0c;PCI作为最成功的底层总线&#xff0c;集成了大量的外设&#xff0c;不夸张的说&#xff0c;目前PCI几乎是唯一的总线选择&#xff0c;故大部分情况下&#xff0c;只有PCI设备驱动程序会遇到…
阅读更多...
【回溯】1240. 铺瓷砖

【回溯】1240. 铺瓷砖

本文涉及知识点 回溯 LeetCode1240. 铺瓷砖 你是一位施工队的工长&#xff0c;根据设计师的要求准备为一套设计风格独特的房子进行室内装修。 房子的客厅大小为 n x m&#xff0c;为保持极简的风格&#xff0c;需要使用尽可能少的 正方形 瓷砖来铺盖地面。 假设正方形瓷砖的…
阅读更多...
【C++小语法】引用和内联函数（完结篇）

【C++小语法】引用和内联函数（完结篇）

在使用C语言编程过程中&#xff0c;C语言的要求之严格&#xff0c;编程过程之繁琐&#xff0c;大同小异的重复性工作&#xff0c;令C之父使用C语言编程时也深受其扰&#xff0c;于是乎C兼容C小语法诞生了 一、引用 1.引用概念 在C中&#xff0c;引用&#xff08;Reference&am…
阅读更多...
最新文章

Copyright @ 2022~2023