数据结构从入门到精通——队列

队列

  • 前言
  • 一、队列
    • 1.1队列的概念及结构
    • 1.2队列的实现
    • 1.3队列的实现
    • 1.4扩展
  • 二、队列面试题
  • 三、队列的具体实现代码
    • Queue.h
    • Queue.c
    • test.c
    • 队列的初始化
    • 队列的销毁
    • 入队列
    • 出队列
    • 返回队头元素
    • 返回队尾元素
    • 检测队列是否为空
    • 检测元素个数

前言

队列是一种特殊的线性数据结构，遵循先入先出（FIFO）的原则。它只允许在队列的末尾添加元素（称为入队操作），并从队列的开头移除元素（称为出队操作）。队列在多种应用中发挥着重要作用，如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。

一、队列

1.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头
在这里插入图片描述

1.2队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
在这里插入图片描述

1.3队列的实现

// 链式结构：表示队列 
typedef struct QListNode 
{ 
 struct QListNode* _pNext; 
 QDataType _data; 
}QNode; 
 
// 队列的结构 
typedef struct Queue 
{ 
 QNode* _front; 
 QNode* _rear; 
}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);

1.4扩展

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型
时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

在这里插入图片描述
在这里插入图片描述

二、队列面试题

  1. 用队列实现栈

  2. 用栈实现队列

  3. 设计循环队列

  4. 循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后，front=rear=99 ，则循环队列中的元素个数为（ ）
    A 、1
    B 、2
    C 、99
    D、 0或者100

  5. 以下( )不是队列的基本运算？
    A 、从队尾插入一个新元素
    B、 从队列中删除第i个元素
    C、 判断一个队列是否为空
    D、 读取队头元素的值

  6. 现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设
    队头不存放数据)
    A 、(rear - front + N) % N + 1
    B 、(rear - front + N) % N
    C 、(rear - front) % (N + 1)
    D 、(rear - front + N) % (N - 1)

答案：DBB

三、队列的具体实现代码

Queue.h

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

typedef int QDatatype;
typedef struct QueueNode
{
	QDatatype val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDatatype x);
//出队列
void QueuePop(Queue* pq);

//队头元素
QDatatype QueueFront(Queue* pq);
//队尾元素
QDatatype QueueBack(Queue* pq);

//检测是否为空
bool QueueEmpty(Queue* pq);

//检测元素个数
int QueueSize(Queue* pq);

Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode malloc :");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}
	pq->size++;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
	assert(pq->phead != NULL);
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);
	return pq->phead->val;
}
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail != NULL);
	return pq->ptail->val;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

test.c

#include"Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);

	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	QueueDestroy(&q);

	return 0;
}

队列的初始化

//队列的初始化
void QueueInit(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

队列的初始化是数据结构学习中不可或缺的一步，它标志着队列这一特定数据存储形式的诞生。队列，又称先进先出（FIFO）的数据结构，允许我们在一端（通常是队尾）添加元素，而在另一端（通常是队头）移除元素。这种特性使得队列在多种应用场景中发挥着重要作用，如操作系统中的任务调度、网络中的缓冲管理等。

在初始化队列时，我们首先需要分配一定的存储空间来存放队列元素。这个存储空间可以是数组、链表或其他适合的数据结构。初始化过程中，我们还需设置两个指针，分别指向队头和队尾，以便进行元素的添加和移除操作。

完成初始化后，队列就处于空状态，即没有元素可供处理。此时，任何尝试从队列中移除元素的操作都会失败，因为队列是空的。然而，可以向队列中添加元素，这些元素将按照添加的顺序依次排列。

随着元素的不断加入，队尾指针会向后移动，指向队列中最后一个元素。当需要从队列中移除元素时，队头指针会向前移动，指向下一个待处理的元素。这种指针的移动保证了队列的先进先出特性，即最早加入队列的元素将最先被移除。

除了基本的添加和移除操作外，队列还支持其他一些有用的操作，如检查队列是否为空、判断队列是否已满等。这些操作使得队列在实际应用中更加灵活和高效。

总之，队列的初始化是队列生命周期的开始，它为队列的后续操作提供了基础。通过对队列的合理初始化和管理，我们可以有效地处理各种需要先进先出处理顺序的场景，提高程序的效率和稳定性。

队列的销毁

//队列的销毁
void QueueDestroy(Queue* pq);

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

队列的销毁涉及清除所有队列元素并释放队列占用的内存空间，确保资源得到正确回收。这通常涉及遍历队列，逐个删除元素，并解除队列与其他数据结构或资源的关联。销毁队列后，其不再可用，需重新创建才能使用。

入队列

//入队列
void QueuePush(Queue* pq, QDatatype x);

void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode malloc :");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}
	pq->size++;
}

入队列（Enqueue）是队列操作的一种，指的是将一个元素添加到队列的尾部。在队列这种先进先出（FIFO）的数据结构中，新添加的元素将排在所有已有元素的后面，等待被处理或移除。入队列操作不会改变队列中已有元素的顺序，保证了队列的先进先出特性。在实际应用中，入队列常用于实现缓冲、任务调度、消息传递等场景。

出队列

//出队列
void QueuePop(Queue* pq);

void QueuePop(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
	assert(pq->phead != NULL);
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

出队列是指从队列中移除并返回队列头部的元素，通常用于实现先进先出（FIFO）的数据结构。在出队列操作中，队列头部元素被移除并返回，队列中的其他元素则向前移动一位。出队列操作的时间复杂度通常为O(1)，因为它只涉及到对队列头部元素的移除和返回，不需要遍历整个队列。在实际应用中，出队列操作常用于缓存管理、任务调度、网络流量控制等场景。

返回队头元素

//队头元素
QDatatype QueueFront(Queue* pq);

QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);
	return pq->phead->val;
}

队列是一种特殊的线性表，只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列具有先进先出（FIFO）的特性。

"返回队头元素"是对队列进行的一种操作，即获取队列前端（队头）的元素，但并不从队列中删除该元素。这通常用于查看队列中的第一个元素，但不改变队列的状态。

返回队尾元素

//队尾元素
QDatatype QueueBack(Queue* pq);

QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail != NULL);
	return pq->ptail->val;
}

检测队列是否为空

//检测是否为空
bool QueueEmpty(Queue* pq);

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

检测队列是否为空，可以通过检查队列的头部和尾部指针或索引来实现。如果头部和尾部指针或索引相同，说明队列为空；否则，队列不为空。此外，也可以使用队列提供的相关函数或方法，如isEmpty()等，来检测队列是否为空。在实际应用中，检测队列是否为空是常见的操作，常用于控制程序的流程。

在C语言中，没有相关的库函数检验是否为空，在c++中会有相关的数据结构的库

检测元素个数

//检测元素个数
int QueueSize(Queue* pq);

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

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

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

相关文章

练习ROS动作编程

练习ROS动作编程

ROS学习记录&#xff1a;动作编程 引言&#xff1a; ​ 通过本实验&#xff0c;我们将联系我们学过的动作编程&#xff0c;客户端发送一个运动目标,模拟小乌龟运动到目标位置的过程,包含服务端和客户端的代码实现&#xff0c;并且带有实时的位置反馈。 希望你在本次学习过后&am…
阅读更多...
计算机网络谢希仁第8版课后习题答案（PDF）

计算机网络谢希仁第8版课后习题答案（PDF）

百度网盘&#xff1a;https://pan.baidu.com/s/1cY_DkwaljjL7kU00-APLhw 提取码&#xff1a;5488
阅读更多...
linux网络通信（TCP）

linux网络通信（TCP）

TCP通信 1.socket----->第一个socket 失败-1&#xff0c;错误码 参数类型很多&#xff0c;man查看 2.connect 由于s_addr需要一个32位的数&#xff0c;使用下面函数将点分十进制字符串ip地址以网络字节序转换成32字节数值 同理端口号也有一个转换函数 我们的端口号位两个字…
阅读更多...
Spring boot 请求参数包含[]等特殊字符，导致无法接收问题

Spring boot 请求参数包含[]等特殊字符，导致无法接收问题

前言对字符进行转义修改tomcat 配置 前言 Spring boot 请求参数包含[]等特殊字符&#xff0c;导致无法接收问题 对字符进行转义 中括号[] 必须用%5B%5D转义&#xff0c;否则tomcat无法解析&#xff0c;回抛出不合法字符异常&#xff0c;不会进入控制器 修改tomcat 配置 p…
阅读更多...
Kubernetes 安全秘籍：5 个你必须知道的知识点

Kubernetes 安全秘籍：5 个你必须知道的知识点

Kubernetes 安全和身份验证是确保集群和应用安全的关键。今天将深入探讨 Service Account、身份验证和RBAC的关键概念和实践&#xff0c;帮助您构建安全可靠的应用。今天本文将着重于安全相关的内容&#xff0c;并提供更详细的示例和配置说明&#xff0c;帮助兄弟们更深入地理解…
阅读更多...
Java8 CompletableFuture异步编程-进阶篇

Java8 CompletableFuture异步编程-进阶篇

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 前言 我们在前面文章讲解了CompletableFuture这个异步编程类的基本用法&#xff0c;…
阅读更多...
猫头虎分享已解决Bug || 系统监控故障：MonitoringServiceDown, MetricsCollectionError

猫头虎分享已解决Bug || 系统监控故障：MonitoringServiceDown, MetricsCollectionError

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
【敬伟ps教程】文字处理工具

【敬伟ps教程】文字处理工具

文章目录 文字工具使用方式文字图层文字工具选项字符面板段落面板文字工具使用方式 文字工具（快捷键T），包含横排和直排两种类型 创建文本两种类型：点式文本、段落文本 创建文字方式 1、在画面上单击，出现文字光标，可输入文字，然后需要在工具栏中点击“√”或者 Ctrl+…
阅读更多...
存算一体成为突破算力瓶颈的关键技术？

存算一体成为突破算力瓶颈的关键技术？

大模型的训练和推理需要高性能的算力支持。以ChatGPT为例&#xff0c;据估算&#xff0c;在训练方面&#xff0c;1746亿参数的GPT-3模型大约需要375-625台8卡DGX A100服务器训练10天左右&#xff0c;对应A100 GPU数量约3000-5000张。 在推理方面&#xff0c;如果以A100 GPU单卡…
阅读更多...
UnityShader——09数学知识3

UnityShader——09数学知识3

方阵 行与列数量相等的矩阵,n*n阶矩阵 对角矩阵 当对角线以外的矩阵内元素全为0&#xff0c;则称之为对角矩阵&#xff0c;对角矩阵的前提是必须是方阵 单位矩阵 对角线元素全为1&#xff0c;其余元素全为0&#xff0c;属于对角矩阵的一部分 矩阵和向量 把1 * n阶矩阵称…
阅读更多...
JavaWeb - 2 - HTML、CSS

JavaWeb - 2 - HTML、CSS

什么是HTML、CSS&#xff1f; HTML&#xff08;HyperText Markup Language&#xff09;&#xff1a;超文本标记语言 超文本&#xff1a;超越了文本的限制&#xff0c;比普通文本更强大&#xff0c;除了文字信息&#xff0c;还可以定义图片、音频、视频等内容 标记语言&…
阅读更多...
ESP8266程序烧录方法（以ESPFlashDownloadTool为例）

ESP8266程序烧录方法（以ESPFlashDownloadTool为例）

0 工具准备 ESP8266必须包含的目标bin ESPFlashDownloadTool_v3.6.3.exe NodeMCU&#xff08;ESP8266&#xff09; sscom5 1 ESP8266程序烧录方法&#xff08;以ESPFlashDownloadTool为例&#xff09; 1.1 生成ESP8266所需的bin文件 可以参考前面所写的《安信可IDE&#xff0…
阅读更多...
被唤醒的“第二十条”深入人心

被唤醒的“第二十条”深入人心

近来张艺谋执导的电影《第二十条》&#xff0c;因为它与正在召开中的全国两会所发布的《最高人民法院工作报告》联系相当紧密&#xff0c;加之可免费收看&#xff0c;网民便相互转告&#xff0c;于是此信息条目立即冲上了网络热搜榜&#xff0c;观者如潮。因为最高人民法院工作…
阅读更多...
STM32 HAL库RTC复位丢失年月日的解决办法

STM32 HAL库RTC复位丢失年月日的解决办法

STM32 HAL库RTC复位丢失年月日的解决办法 0.前言一、实现方式1.CubeMX配置&#xff1a;2.MX_RTC_Init()函数修改2.编写手动解析函数 二、总结 参考文章&#xff1a;stm32f1 cubeMX RTC 掉电后日期丢失的问题 0.前言 最近在使用STM32F103做RTC实验时&#xff0c;发现RTC复位后时…
阅读更多...
LeetCode-Hot100

LeetCode-Hot100

哈希 1.两数之和&#xff1a; 给定一个整数数组nums和一个整数目标值target&#xff0c;请你再该数组中找出和为目标值target的那两个整数&#xff0c;并返回它们的数组下标。 思路&#xff1a;暴力解法是使用两层循环来遍历每一个数&#xff0c;然后找出两数之和等于target的…
阅读更多...
2024/3/9d打卡整数划分---背包动态规划方式，计数类动态规划

2024/3/9d打卡整数划分---背包动态规划方式，计数类动态规划

目录 题目 DP分析 第一种方法&#xff0c;背包DP 代码 第二种方法&#xff08;有点难想到&#xff09; 代码 题目 一个正整数 n 可以表示成若干个正整数之和&#xff0c;形如&#xff1a;nn1n2…nk&#xff0c;其中 n1≥n2≥…≥nk,k≥1。 我们将这样的一种表示称为正整数 …
阅读更多...
maven项目引入私有jar，并打包到java.jar中

maven项目引入私有jar，并打包到java.jar中

私有jar存放位置 maven依赖 <dependency><groupId>com.hikvision.ga</groupId><artifactId>artemis-http-client</artifactId><version>1.1.10</version><scope>system</scope><systemPath>${project.basedir}/s…
阅读更多...
FPGA高端项目：FPGA基于GS2971的SDI视频接收+HLS图像缩放+多路视频拼接，提供4套工程源码和技术支持

FPGA高端项目：FPGA基于GS2971的SDI视频接收+HLS图像缩放+多路视频拼接，提供4套工程源码和技术支持

目录 1、前言免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案的SDI接收转HDMI输出应用本方案的SDI接收图像缩放应用本方案的SDI接收纯verilog图像缩放纯verilog多路视频拼接应用本方案的SDI接收OSD多路视频融合叠加应用本方案的SDI接收HLS多路视频融合叠加应用本方案…
阅读更多...
基于YOLOv8深度学习的葡萄病害智能诊断与防治系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战

基于YOLOv8深度学习的葡萄病害智能诊断与防治系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：LoadingProgress）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：LoadingProgress）

用于显示加载动效的组件。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 LoadingProgress() 创建加载进展组件。 从API version 9开始&#xff0c;该接口支持在ArkTS卡片中使…
阅读更多...
最新文章

Copyright @ 2022~2023