数据结构--队列（图文）

队列是一种特殊的线性表，其核心特点是先进先出。

概念及特点：

概念

队列是一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的线性表。进行插入操作的一端被称为队尾（Tail 或 Rear），进行删除操作的一端被称为队头（Head 或 Front）。在日常生活中，我们可以将队列比作排队等候的场景，排在前面的人会先得到服务，新来的人则排在队尾等待。
在这里插入图片描述

特点：

  1. 先进先出（FIFO）：队列的基本操作是入队和出队。入队操作是在队尾插入一个元素，而出队操作是从队头删除一个元素。这意味着最先进入队列的元素将最先被移除。

  2. 操作受限：与普通的线性表不同，队列的操作是受限制的。只能在队尾添加元素，只能在队头删除元素。

  3. 两种实现方式：队列可以通过数组或链表来实现。使用数组实现时，可能会遇到数组空间受限的问题，但可以通过循环队列的方式解决。使用链表实现时，可以动态地分配内存，但可能会有额外的内存开销。

  4. 动态变化：队列是一种动态的数据结构，其大小可以根据需要动态变化。在入队和出队操作时，队列的大小会相应地增加或减少。

  5. 应用广泛：队列在计算机科学中有广泛的应用，如广度优先搜索、任务调度、缓冲处理、线程同步等。

队列的操作

  • 初始化：创建一个空队列。

  • 入队：将一个元素添加到队列的末尾，即队尾。

  • 出队：从队列的开头，即队首，移除元素并返回该元素的值。

  • 返回队首元素：返回队列中的第一个元素的值，但不从队列中删除该元素。

  • 返回队尾元素）：返回队列中的末尾元素的值，但不从队列中删除该元素。

  • 获取队列元素个数：返回队列中的末尾元素的值，但不从队列中删除该元素。

  • 判断队列是否为空： 检查队列中是否没有任何元素。

  • 销毁队列：释放队列所占用的存储空间，使得队列不再存在。

队列的应用

队列的应用场景包括但不限于：

  • 打印机任务队列：打印机按照任务进入队列的顺序进行打印，确保了公平性和先到先服务的原则。

  • 网络请求处理：服务器使用队列来管理并响应客户端的请求，保证了请求按照到达顺序被处理。

  • 生产线作业：在生产线上，队列模型用于管理产品的生产流程，确保每个产品都能按照顺序经过各个加工阶段。

  • 消息队列：在消息传递系统中，消息被放入队列，然后由消费者按照顺序处理，支持异步消息处理和负载均衡。

  • 任务队列：在Web服务器和后台处理系统中，任务队列用于管理和调度异步任务，如发送电子邮件、处理图像等。

  • 优先级队列：在需要优先处理的场景中，如紧急任务或高价值任务，使用优先级队列可以确保这些任务能够优先被执行。

队列的实现

这里我们使用链表来实现队列。

首先创建三个文件：

  • Queue.h —— 用于声明函数的头文件。
  • Queue.c —— 队列主要函数的实现。
  • test.c——测试队列。

队列节点的定义

这里和单链表结构一致。

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

队列指针的定义

将队列的首尾指针封装成一个结构体，可以方便函数调用，统一接口。再使用一个整型size记录元素个数，利于其他函数功能实现。

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

在这里插入图片描述

初始化

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);//队列必须存在
	q->head = q->tail = NULL;
	q->size = 0;
}

销毁队列

创建指针循环遍历链表，每次记录下指针的下一个节点，释放指针指向的节点，指针指向下一个节点

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->head)//释放所有节点
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

入队列（队尾插入）

  • 情况一：队列为空直接申请新节点给头节点和尾节点；
  • 情况二：队列不为空，将新节点接入尾节点后即可。
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//判定是否申请成功
	{
		perror("newnode error\n");
		exit(1);
	}
	newnode->data = data;
	newnode->next = NULL;
 
	if (q->head == NULL)//对空队列入队的处理
	{
		q->head = q->tail = newnode;
	}
	else               //对非空队列入队的处理
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

出队列（队头删除）

  • 情况一：队列只有一个节点，直接释放即可；
  • 情况二：队列有多个节点，将头节点的下一个节点保存后释放头节点，在让头节点指向保存的节点。
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	if (q->head == q->tail)//对只有一个元素的队列的出队处理
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else          //对存在多个元素的队列的出队处理
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;
}

获取队头元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	return q->head->data;
}

获取队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->tail->data;
}

获取队列元素个数

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

队列判空

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

队列源码

Queue.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#include"Queue.h"
 
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);//队列必须存在
	q->head = q->tail = NULL;
	q->size = 0;
}
 
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//判定是否申请成功
	{
		perror("newnode error\n");
		exit(1);
	}
	newnode->data = data;
	newnode->next = NULL;
 
	if (q->head == NULL)//对空队列入队的处理
	{
		q->head = q->tail = newnode;
	}
	else               //对非空队列入队的处理
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}
 
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	if (q->head == q->tail)//对只有一个元素的队列的出队处理
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else          //对存在多个元素的队列的出队处理
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;
}
 
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	return q->head->data;
}
 
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->tail->data;
}
 
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
 
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
 
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->head)//释放所有节点
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

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

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

相关文章

测定分子结构丨核磁共振（NMR）测试原理、制样要求以及常见问题深度解密！...

测定分子结构丨核磁共振（NMR）测试原理、制样要求以及常见问题深度解密！...

✨【元素魔方学术俱乐部】✨ &#x1f469;‍&#x1f3eb;&#x1f468;‍&#x1f3eb;我们创建了一个学术交流群 给全国各地以及各种研究方向的硕博 和老师们提供一个交流的平台&#x1f4da;&#x1f9ea; 感兴趣的话欢迎加入 &#x1f4f2;本公众号中回复“社群” 会自动发…
阅读更多...
短剧APP平台开发，互联网下的市场发展前景

短剧APP平台开发，互联网下的市场发展前景

近几年&#xff0c;短剧作为当下的热门行业之一&#xff0c;具有非常大的发展空间&#xff0c;市场前景一片大好&#xff0c;成为了一个新的的蓝海赛道。 随着互联网科技的不断发展&#xff0c;行业数字化发展已经成为了必然趋势。短剧APP系统的开发让观众拥有了一个在线观看短…
阅读更多...
Windows 中的 Hosts 文件是什么？如何找到并修改它？

Windows 中的 Hosts 文件是什么？如何找到并修改它？

什么是 Hosts 文件 Hosts 文件是一个纯文本文件&#xff0c;存在于几乎所有的操作系统中&#xff0c;用于将主机名映射到 IP 地址。在域名系统&#xff08;DNS&#xff09;尚未普及之前&#xff0c;Hosts 文件是计算机网络中唯一用于主机名解析的方式。随着网络规模的扩大和 D…
阅读更多...
Mac可以读取NTFS吗 Mac NTFS软件哪个好 mac ntfs读写工具免费

Mac可以读取NTFS吗 Mac NTFS软件哪个好 mac ntfs读写工具免费

在跨操作系统环境下使用外部存储设备时&#xff0c;特别是当Windows系统的U盘被连接到Mac电脑时&#xff0c;常常会遇到文件系统兼容性的问题。由于Mac OS原生并不完全支持对NTFS格式磁盘的读写操作&#xff0c;导致用户无法直接在Mac上向NTFS格式的U盘或硬盘写入数据。下面我们…
阅读更多...
架构师必知的绝活-JVM调优

架构师必知的绝活-JVM调优

前言 为什么要学JVM&#xff1f; 首先&#xff1a;面试需要 了解JVM能帮助回答面试中的复杂问题。面试中涉及到的JVM相关问题层出不穷&#xff0c;难道每次面试都靠背几百上千条面试八股&#xff1f; 其次&#xff1a;基础知识决定上层建筑 自己写的代码都不知道是怎么回事&a…
阅读更多...
[ROS 系列学习教程] 建模与仿真 - 使用 ros_control 控制差速轮式机器人

[ROS 系列学习教程] 建模与仿真 - 使用 ros_control 控制差速轮式机器人

ROS 系列学习教程(总目录) 本文目录 一、差速轮式机器人二、差速驱动机器人运动学模型三、对外接口3.1 输入接口3.2 输出接口 四、控制器参数五、配置控制器参数六、编写硬件抽象接口七、控制机器人移动八、源码 ros_control 提供了多种控制器&#xff0c;其中 diff_drive_cont…
阅读更多...
揭示隐藏的模式：秩和检验和单因素方差分析的实战指南【考题】

揭示隐藏的模式：秩和检验和单因素方差分析的实战指南【考题】

1.研究一种新方法对于某实验结果准确性提高的效果&#xff0c;并将其与原有方法进行比较&#xff0c;结果见下表&#xff0c;请评价两者是否有不同? (行无序&#xff0c;列有序)-->单方向有序-->两独立样本的秩和检验) 如下图所示&#xff0c;先将相关数据导入spss。 图…
阅读更多...
springboot注解@ComponentScan注解作用

springboot注解@ComponentScan注解作用

一 ComponentScan作用 1.1 注解作用 项目会默认扫描SpringBootApplication注解所在路径的同级和下级的所有子包&#xff0c;使用ComponentScan后他会取代掉默认扫描。 ComponentScan 是Spring框架的注解&#xff0c;它的作用是扫描指定的包路径下的标有 Component、Service、…
阅读更多...
docker-mysql主从复制

docker-mysql主从复制

MySQL主从复制 安装docker和拉取镜像不再赘述 一.主服务器 1.新建主服务器容器-3307 &#xff08;这里设置的密码可能不生效&#xff0c;若未生效请看问题中的2&#xff09; docker run -p 3307:3306 --name mysql-master \ -v /mydata/mysql-master/log:/var/log/mysql \…
阅读更多...
mindspore打卡第9天 transformer的encoder和decoder部分

mindspore打卡第9天 transformer的encoder和decoder部分

mindspore打卡第9天 transformer的encoder和decoder部分 import mindspore from mindspore import nn from mindspore import ops from mindspore import Tensor from mindspore import dtype as mstypeclass ScaledDotProductAttention(nn.Cell):def __init__(self, dropout_…
阅读更多...
13017.win10安装WSL2及CUDA开发环境

13017.win10安装WSL2及CUDA开发环境

文章目录 1 win10版本1.1 关键项不能忽略 2 安装WSL2 ubuntu20.042.1 打开控制面板&#xff0c;开启虚拟子系统功能2.2 离线安装ubuntu2.2 WSL2 启动 ubuntu2.3 修改默认启动用户 3 ubuntu中安装vscode-server3.1 win10 中安装vscode3.2 ubuntu中安装vscode-server3.3 启动WSL2…
阅读更多...
嵌入式学习（Day 51:ARM指令/汇编与c语言函数相互调用）

嵌入式学习（Day 51:ARM指令/汇编与c语言函数相互调用）

1.Supervisor模式与SVC模式 Supervisor模式是ARM处理器的一个特权工作模式&#xff0c;允许执行特权指令和访问特权资源。SVC模式&#xff08;Supervisor Call&#xff09;是与Supervisor模式相关的一个功能或指令&#xff0c;用于从用户模式切换到Supervisor模式&#xff0c;…
阅读更多...
【C++ | 类型转换】转换构造函数、类型转换运算符 详解及例子源码

【C++ | 类型转换】转换构造函数、类型转换运算符 详解及例子源码

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a; 本文未经允许…
阅读更多...
认识100种电路之稳压电路

认识100种电路之稳压电路

在电子电路中&#xff0c;稳压电路扮演着至关重要的角色。那么&#xff0c;为什么电路需要稳压&#xff1f;稳压的原理又是什么&#xff1f;以及稳压需要用到哪些元器件&#xff0c;数量又有多少呢&#xff1f;今天&#xff0c;就让我们一同揭开稳压电路的神秘面纱。 【电路为什…
阅读更多...
【原创图解 算法leetcode 146】实现一个LRU缓存淘汰策略策略的数据结构

【原创图解 算法leetcode 146】实现一个LRU缓存淘汰策略策略的数据结构

1 概念 LRU是Least Recently Used的缩写&#xff0c;即最近最少使用&#xff0c;是一种常见的缓存淘汰算法。 其核心思想为&#xff1a;当内存达到上限时&#xff0c;淘汰最久未被访问的缓存。 2 LeetCode LeetCode: 146. LRU缓存 3 实现 通过上面LRU的淘汰策略可知&#…
阅读更多...
Zookeeper节点ACL权限设置—digest模式

Zookeeper节点ACL权限设置—digest模式

ACL全称为Access Control List&#xff08;访问控制列表&#xff09;&#xff0c;用于控制资源的访问权限。ZooKeeper使用ACL来控制对其znode&#xff08;ZooKeeper数据树的数据节点&#xff09;的访问。 zk利用ACL策略控制节点的访问权限: CREATE c 可以创建子节点 DELETE …
阅读更多...
Java中System的用法

Java中System的用法

System指的是当前进程运行的操作系统&#xff0c;属于java.lang包下面的类 常见的用法有以下几种&#xff1a; 第一种简单,我们直接上第二种方法吧 currentTimeMills()用法 // 演示currentTimeMillis方法public static void main(String[] args) {// 获取当前时间所对应的毫秒…
阅读更多...
《红黑树大能量——set，map封装模拟》

《红黑树大能量——set，map封装模拟》

前言 书接上篇博客《手撕红黑树》&#xff0c;我们学习到了红黑树是如何通过其内部方式来管理数据的&#xff0c;本篇文章将基于上篇文章继续探讨红黑树的更多应用。set&#xff0c;map是STL库中很重要的容器&#xff0c;他们就是利用红黑树作为底层来实现的&#xff0c;今天让…
阅读更多...
入门Java爬虫：认识其基本概念和应用方法

入门Java爬虫：认识其基本概念和应用方法

Java爬虫初探&#xff1a;了解它的基本概念与用途&#xff0c;需要具体代码示例 随着互联网的快速发展&#xff0c;获取并处理大量的数据成为企业和个人不可或缺的一项任务。而爬虫&#xff08;Web Scraping&#xff09;作为一种自动化的数据获取方法&#xff0c;不仅能够快速…
阅读更多...
数据结构--堆（图文）

数据结构--堆（图文）

在开始学习堆之前&#xff0c;我们要先简单了解二叉树 二叉树 一棵二叉树是结点的一个有限集合&#xff0c;该集合: 为空由一个根结点加上两棵子树&#xff08;左子树和右子树&#xff09; 特殊的二叉树&#xff1a; 满二叉树&#xff1a;一个二叉树&#xff0c;如果每一…
阅读更多...
最新文章

Copyright @ 2022~2023