暴力数据结构之栈与队列(队列详解)

1.队列的定义

       队列是一种特殊的线性表,它遵循先进先出(FIFO)的原则。在队列中,只允许在表的一端进行插入操作(队尾),而在另一端进行删除操作(队头)。这种数据结构确保了最先进入队列的元素总是最先离开队列。队列中没有元素时,被称为空队列。队列的组织和实施训练通常由队列条令予以规定,用于规范部队、分队队列及其在各种条件下的运动队形和动作。

出队的是队头,入队的为队尾

2.实现队列 

对于队列,我们知道是一种线性表,我们可以使用单链表双向链表或者数组都可以实现,这里我们首先介绍使用单链表实现的。

对于单链表实现队列,我们知道队列有队头和队尾,所以设置两个指针*phead 和*ptail表示头尾,但是如何找到头和尾需要讨论,如果只是创建一个单链表,那么索引头尾就十分繁琐,所以我们可以设计两个链表一个存储数据一个索引头尾,这样就很方便的实现了队列。

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

 解释:创建一个单链表 QueueNode 用来存储队列元素,再创建一个单链表 Queue 索引队头和队尾,插入数据时 QueueNode 使用动态内存申请开辟空间节点 newnode, 尾节点 *ptail 指向新开辟的节点,即索引队尾,队头保持不变,从而实现索引头尾的功能。

3.队列的相关操作

3.1 初始化和销毁

初始化:断言传入指针不为NULL,将起索引作用的链表头尾均置为NULL,链表长度初始化为0。

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

销毁:创建一个cur指针保存头结点,依次释放,最后将整个链表初始化。

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

插入:队列只有队尾插入,所以直接在QueueNode单链表上动态内存开辟一个newnode新节点,然后让单链表Queue索引头尾,修改Queue中的数据。

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

删除: 首先判断删除的链表是否为NULL,不为NULL则可以删除,所以创建一个新的next 保存待删除节点,释放节点,置为NULL,当然若只有一个节点即*phead就是*ptail,将他们置为NULL即可。

// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = 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--;
}
 3.3 取出队头或队尾的数据

取出队头:这时两个单链表的作用就体现出来了,取队头直接取phead->val的元素即可。

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

 取出队尾:直接返回尾节点ptail->val的数据即可。

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
 3.4 判空与计算链表长度

计算链表长度:直接返回Queue中的size即可

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

判空: 判断链表长度是否为0,是则为空,反之不为空。

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

 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

第十一篇:操作系统新纪元:智能融合、量子跃迁与虚拟现实的交响曲

操作系统新纪元:智能融合、量子跃迁与虚拟现实的交响曲 1 引言 在数字化的浪潮中,操作系统如同一位智慧的舵手,引领着信息技术的航船穿越波涛汹涌的海洋。随着人工智能、物联网、量子计算等前沿技术的蓬勃发展,操作系统正站在一个…

98、技巧-颜色分类

思路 这道题的思路是什么,首先典型荷兰国旗问题: 该问题的关键在于我们要将所有的0放到数组的前部,所有的1放在中间,所有的2放在后部。这可以通过使用两个指针,一个指向数组开头的“0”的最后一个位置,另…

计算图与自动微分

计算图与自动微分 一、自动梯度计算1.1 数值微分(Numerical Differentiation)1.2 符号微分(Symbolic Differentiation)1.3 自动微分(Automatic Differentiation,AD)1.3.1 计算图1.3.2 正向传播1…

postman常用功能超全使用教程

Postman 使用 一、Postman 简介 Postman是一个接口测试工具,在做接口测试的时候,Postman相当于一个客户端,它可以模拟用户发起的各类HTTP请求(如:get/post/delete/put…等等),将请求数据发送至服务端,获取对应的响应结果。 二、Postman 功能简介 三、Postman 下载安装 Post…

Android GPU渲染SurfaceFlinger合成RenderThread的dequeueBuffer/queueBuffer与fence机制(2)

Android GPU渲染SurfaceFlinger合成RenderThread的dequeueBuffer/queueBuffer与fence机制(2) 计算fps帧率 用 adb shell dumpsys SurfaceFlinger --list 查询当前的SurfaceView,然后有好多行,再把要查询的行内容完整的传给 ad…

2024C题生物质和煤共热解问题的研究 详细思路

背景 随着全球能源需求的不断增长和对可再生能源的追求,生物质和煤共热解作为一种潜在的能源转化技术备受关注。生物质是指可再生能源,源自植物和动物的有机物质,而煤则是一种化石燃料。** 在共热解过程中,生物质和煤在高温和缺氧…

Java入门基础学习笔记14——数据类型转换

类型转换: 1、存在某种类型的变量赋值给另一种类型的变量; 2、存在不同类型的数据一起运算。 自动类型转换: 类型范围小的变量,可以直接赋值给类型范围大的变量。 byte类型赋值给int类型,就是自动类型转换。 pack…

【AMBA Bus ACE 总线 8 -- ICache maintenance】

请阅读【AMBA Bus ACE 总线与Cache 专栏 】 欢迎学习:【嵌入式开发学习必备专栏】 文章目录 ACE ICache maintenanceACE ICache maintenance 图 1-1 当一个OS run 多个cpu的时候,根据调度算法的不同,OS 可以根据调度算法的不同分别 run 在某个具体的CPU上,因此,它们会有…

非模块化 Vue 开发的 bus 总线通信

个人感觉,JavaScript 非模块开发更适合新人上手,不需要安装配置一大堆软件环境,不需要编译,适合于中小项目开发,只需要一个代码编辑器即可开发,例如 vsCode。网页 html 文件通过 script 标签引入 JavaScrip…

Bugku Crypto 部分题目简单题解(三)

where is flag 5 下载打开附件 Gx8EAA8SCBIfHQARCxMUHwsAHRwRHh8BEQwaFBQfGwMYCBYRHx4SBRQdGR8HAQ0QFQ 看着像base64解码 尝试后发现,使用在线工具无法解密 编写脚本 import base64enc Gx8EAA8SCBIfHQARCxMUHwsAHRwRHh8BEQwaFBQfGwMYCBYRHx4SBRQdGR8HAQ0QFQ tex…

机器学习的一些知识点分享

解决过拟合问题的常用方法有( )。 A 使用丢弃法 B 减少模型特征 C 使用正则化约束 D 增加训练样本数量 本题得分: 0分 正确答案: A,B,C,D (少选不得分) 2.填空题 (2分) 过拟合是指模型过于复杂,学习能力太强&a…

【17-Ⅱ】Head First Java 学习笔记

HeadFirst Java 本人有C语言基础,通过阅读Java廖雪峰网站,简单速成了java,但对其中一些入门概念有所疏漏,阅读本书以弥补。 第一章 Java入门 第二章 面向对象 第三章 变量 第四章 方法操作实例变量 第五章 程序实战 第六章 Java…

重载,重写,重定义,纯虚函数,多态习题

只要不够成重写就是重定义。 重定义: 抽象类: 包含纯虚函数的类就是抽象类。 1.纯虚函数的作用,强制子类去完成重写。 2.表示抽象的类型。 抽象就是在现实中没有对应的实体。 1. 下面哪种面向对象的方法可以让你变得富有( a) A 继承 B…

常见扩频系统的基础概念和模型

扩频系统是一种通信技术,它通过将信号的频谱扩展到一定程度来实现传输,这种系统的设计和实现涉及到多种不同的方法和技术。 扩频系统的主要特点和好处包括: 抗干扰能力强:由于信号被扩展到较宽的频带上,单位带宽内的功…

vue3对象数组格式的动态表单校验

如你有一个表单&#xff0c;表单内容是对象&#xff0c;但是对象内还有可动态循环的数组进行动态表单校验。 效果如图&#xff1a;查看源码 页面内容&#xff1a; <div class"arrForm-Box"><el-form :model"state.formData" :rules"rule…

spring boot参数验证注解@NotNull、@NotBlank和@NotEmpty区别

目录 前言说明举例 前言 使用spring boot参数验证是常常会使用NotNull、NotBlank和NotEmpty三个判断是否不为空的注解&#xff0c;中文都有不能为空的意思&#xff0c;大部分使用者都傻傻分清它们之间到底有什么区别。今天就让咱们来一起探索它们之间的不同吧。 说明 注解名…

数据驱动实战二

目标 掌握数据驱动的开发流程掌握如何读取JSON数据文件巩固PO模式 1. 案例 对TPshop网站的登录模块进行单元测试 1.1 实现步骤 编写测试用例采用PO模式的分层思想对页面进行封装编写测试脚本定义数据文件&#xff0c;实现参数化 1.2 用例设计 1.3 数据文件 {"login…

sprig 项目启动时报错:MybatisDependsonDatabaseInitializationDetector

问题 使用application.yml启动项目报错&#xff1a; 解决方案 修改pom.xml: 修改这两处的版本

[笔试训练](十八)

目录 052:字符串压缩 053:chika和蜜柑 054:01背包 052:字符串压缩 压缩字符串(一)_牛客题霸_牛客网 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 双指针模拟 class Solution { public:string compressString(string param) {int nparam.size();string ret;int num…

Linux 操作系统TCP、UDP

1、TCP服务器编写流程 头文件&#xff1a; #include <sys/socket.h> 1.1 创建套接字 函数原型&#xff1a; int socket(int domain, int type, int protocol); 参数&#xff1a; domain: 网域 AF_INET &#xff1a; IPv4 AF_INET6 &a…