当前位置: 首页 > news >正文

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

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;
}

 

相关文章:

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

1.队列的定义 队列是一种特殊的线性表,它遵循先进先出(FIFO)的原则。在队列中,只允许在表的一端进行插入操作(队尾),而在另一端进行删除操作(队头)。这种数据结构确保了最…...

仿照JDK源码写一个ArrayList实现

仿照JDK编写一个简化的ArrayList实现是一个很好的学习Java集合框架内部工作原理的方式。以下是一个简化版的ArrayList实现,它包含了基本的添加、获取、删除和大小检查功能。 public class MyArrayList<E> {private static final int DEFAULT_CAPACITY = 10;private Obj…...

[链表专题]力扣21, 234

1. 力扣21 题 : 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a;输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4] 示例 2&#xff1a;输入&#xff1a;l1 [], l2 [] 输出&…...

智慧便民小程序源码系统 求职招聘+房产出租+相亲交友 带完整的安装代码包以及系统搭建教程

在数字化、智能化的今天&#xff0c;我们的生活节奏越来越快&#xff0c;对于各种服务的需求也越发多元化和个性化。为了满足广大市民对于便捷、高效、全面的服务需求&#xff0c;罗峰给大家分享一款智慧便民小程序源码系统&#xff0c;集求职招聘、房产出租、相亲交友三大功能…...

苹果免签封装的优势和安全风险

哈喽&#xff0c;大家好呀&#xff0c;淼淼又来和大家见面啦&#xff0c;许多小伙伴应该都知道&#xff0c;App Store一直是iOS应用的主要分发渠道&#xff0c;苹果生态系统的监管是十分严格的&#xff0c;以此确保了应用质量与用户的安全。而苹果免签封装则是有一种不需要通过…...

hook抓包trace定位实战

title: SO逆向之大众点评cx date: 2022-02-07 19:27:28 tags: SOfrida categories: 安卓逆向 toc_number: true抓包10.37.13 打开首页一篇文章,APP默认TCP连接,通过降级采用HTTP连接 jadx反编译代码中 public int g() {Object[] objArr = new Object[0];ChangeQuickRedire…...

SMB 协议详解之-TreeID原理和SMB数据包分析技巧

在前面分析SMB协议数据包的过程中,这里,可以看到在SMB协议中存在很多的ID,即Unique Identifiers。那么这些ID表示什么含义?在实际分析数据包的过程中如何根据这些ID进行过滤分析?本文将介绍SMB/SMB2中的tree id ,并介绍如何通过tree id 快速的分析SMB数据包中各种命令交互…...

博士阶段应该搞什么:-人才引进要求

目录 专利,高水平论文(一作),技能证书,职称,高端竞赛,科研成果奖 济宁学院...

超全MySQL锁机制介绍

前言 MySQL作为关系型数据库管理系统中的佼佼者&#xff0c;为了保证数据的一致性和完整性&#xff0c;在并发控制方面采用了锁机制。锁机制是数据库管理系统用于控制对共享资源的访问&#xff0c;避免多个事务同时修改同一数据造成的数据不一致问题。了解MySQL的锁机制对于数…...

【CV】计算机视觉中的特征追踪与背景处理

计算机视觉领域中的重要任务之一是视频特征追踪&#xff0c;它可以用于目标跟踪、运动分析、行为识别等应用。然而&#xff0c;在实际应用中&#xff0c;经常会遇到需要仅处理视频中特定特征物体而忽略背景的情况&#xff0c;这就需要进行背景处理。本文将介绍如何使用Python和…...

CAPL如何实现TLS握手认证

CAPL有专门的章节介绍如何实现TLS握手认证的函数: CAPL调用哪些函数实现TLS握手认证,需要了解TLS在整个通信过程的哪个阶段。 首先TCP需要建立连接,这是TLS握手的前提。当TLS握手认证完成后,可以传输数据。 所以TLS握手开始前需要确保TCP建立连接,TCP传输数据前需要确保…...

Linux -- 日志

一 日志的重要性 在之前的编程经历中&#xff0c;如果我们的程序运行出现了问题&#xff0c;都是通过 标准输出 或 标准错误 将 错误信息 直接输出到屏幕上&#xff0c;以此来排除程序中的错误。 这在我们以往所写的程序中使用没啥问题&#xff0c;但如果出错的是一个不断在运行…...

WebRtc 视频通话,语音通话实现方案

先了解一下流程 和 流程图(chatGpt的回答) 实现 (底层代码实现, 可作为demo熟悉) 小demo <template><div><video ref"localVideo" autoplay muted></video> <!-- 本地视频元素&#xff0c;用于显示本地视频 --><video ref"r…...

IndyTcpServer使用详解

1、IndyTCPserver的创建 IdTCPServer1.DefaultPort:= 8000; IdTCPServer1.ListenQueue:= 1024; //同时处理请求队列数限制 IdTCPServer1.MaxConnections:= 1024; //同时连接数量限制,为0不限制连接数 IdTCPServer1.ContextClass:= TNewIdServerContext; //设置为自定义TIdSe…...

pytest + yaml 框架 - 参数化读取文件路径优化

针对小伙伴提出参数化时读取外部文件&#xff0c;在项目根路径运行没问题&#xff0c;但是进入到项目下子文件夹运行用例&#xff0c;就会找不到文件问题做了优化。 关于参数化读取外部文件相关内容参考前面这篇pytest yaml 框架 -25.参数化数据支持读取外部文件txt/csv/json/…...

C++:多态-重写和重载

重写&#xff08;Override&#xff09;和重载&#xff08;Overload&#xff09;是面向对象编程中常用的两个概念&#xff0c;它们虽然都涉及到方法的定义&#xff0c;但是在实现和使用上有着不同的特点。 重写&#xff08;Override&#xff09;&#xff1a; 重写是指在子类中重…...

element ui的table多选

使用el-table的selection-change事件来获取选中的值&#xff1b; 例&#xff1a; html代码&#xff1a; <el-button type"primary" click"openTableSet">列表设置</el-button><!-- 列表设置弹框 --> <el-dialog :close-on-click-mo…...

python基础---基础运算

基础运算 可以使用type获取一个变量的类型 常见的数据类型 整形, 可以存储任意大小的整数, 支持二进制&#xff08;如0b100&#xff0c;换算成十进制是4&#xff09;、八进制&#xff08;如0o100&#xff0c;换算成十进制是64&#xff09;、十进制&#xff08;100&#xff09;…...

【数学】泰勒公式

目录 引言 一、泰勒公式 1.泰勒公式及推导 &#xff08;1&#xff09;推导 &#xff08;2&#xff09;公式 2.泰勒中值定理 &#xff08;1&#xff09;定理1&#xff08;佩亚诺余项&#xff09; &#xff08;2&#xff09;定理2&#xff08;拉格朗日余项&#xff09; …...

C++基础-编程练习题及答案

文章目录 前言一、查找“支撑数”二、数组元素的查找三、爬楼梯四、数字交换五、找高于平均分的人 前言 C基础-编程练习题和答案 一、查找“支撑数” 【试题描述】 在已知一组整数中&#xff0c; 有这样一种数非常怪&#xff0c; 它们不在第一个&#xff0c; 也不在最后一个&…...

eNSP-抓包解析HTTP、FTP、DNS协议

一、环境搭建 1.http服务器搭建 2.FTP服务器搭建 3.DNS服务器搭建 二、抓包 三、http协议 1.HTTP协议&#xff0c;建立在TCP协议之上 2.http请求 3.http响应 请求响应报文参考&#xff1a;https://it-chengzi.blog.csdn.net/article/details/113809803 4.浏览器开发者工具抓包…...

【栈】Leetcode 验证栈序列

题目讲解 946. 验证栈序列 算法讲解 在这里就只需要模拟一下这个栈的出栈顺序即可&#xff1a;使用一个stack&#xff0c;每次让pushed里面的元素入栈&#xff0c;如果当前栈顶的元素等于poped容器中的当前元素&#xff0c;因此就需要让栈顶元素出栈&#xff0c;poped的遍历…...

【数据库原理及应用】期末复习汇总高校期末真题试卷08

试卷 一、选择题(每题 2 分&#xff0c;共 30 分)    1. ___ ____是长期存储在计算机内的有组织,可共享的数据集合. A.数据库管理系统 B.数据库系统 C.数据库 D.文件组织 2. 数据库类型是按照 来划分…...

每天五分钟深度学习:数学中的极值

本文重点 在数学领域中,极值是一个极其重要的概念,它不仅在纯数学理论研究中占据核心地位,而且在工程、物理、经济等实际应用领域也发挥着不可替代的作用。极值问题涉及函数的最大值和最小值,是微积分学中的一个基本问题。本文旨在详细介绍数学中的极值概念、性质、求解方…...

【Linux】Linux——Centos7安装Tomcat

1.下载Tomcat 安装包 官网地址&#xff1a;Apache Tomcat - Apache Tomcat 9 Software Downloadshttps://tomcat.apache.org/download-90.cgi 2.将下载的安装包上传到 Xftp 上&#xff0c;我是直接放到 usr 下了 3.将安装包解压到 /usr/local/ tar -zxvf apache-tomcat-9.0.8…...

SpringBoot+vue实现右侧登录昵称展示

目录 1. 定义User数据 1.1.在created方法获取数据 1.2.头部导航栏绑定User数据 1.3.在data中定义User数据 2. 获取数据 2.1.接收父组件传递的值 2.2.展示数据 3. 页面效果 在SpringBoot和 Vue.js 结合的项目中实现右侧登录昵称展示&#xff0c;通常涉及到前端的用户界面…...

【网络原理】UDP协议 | UDP报文格式 | 校验和 | UDP的特点 | 应用层的自定义格式

文章目录 一、UDP协议1.UDP的传输流程发送方接收方 2.UDP协议报文格式&#xff1a;长度受限校验和如何校验&#xff1a;CRC算法&#xff1a;循环冗余算法md5算法&#xff1a; 2.UDP的特点 二、开发中常见的自定义格式1.xml&#xff08;古老&#xff09;2.json&#xff08;最流行…...

NodeJs入门知识

**************************************************************************************************************************************************************************** 1、配置Node.js与npm下载&#xff08;精力所致&#xff0c;必有精品&#xff09; …...

代码随想录学习Day 34

62.不同路径 题目链接 讲解链接 动归五部曲&#xff1a; 1.确定dp数组及其下标的含义&#xff1a;dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数&#xff1b; 2.确定递推公式&#xff1a;因为只能往右或者往下&#xff0c;所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。 3.…...

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题 一、问题详细描述二、问题产生背景三、问题原因四、解决办法1、安装缺少的库2、直接更换更高版本的opencv 五、vs版本对应vc1、版本对应2、vs对应vc查看方法 一、问题详细描述 同样可能会报 &#xff…...