数据结构队列的实现

本章介绍数据结构队列的内容,我们会从队列的定义以及使用和OJ题来了解队列,话不多说,我们来实现吧
队列
1。队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出
FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
我们来看一下下面的这张图,让我们更好的理解它

我们从队尾入,队头出,只能是这样入栈和出栈
2。队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数
组头上出数据,效率会比较低。
那队列的实现我们是用链式结构来实现的,因为用数组下标的话,出栈的时候要往前挪动数据,会更麻烦,这样队列的意义就下降了,所以我们这里用的方法是链式结构。
typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;
这里我们定义的结构体Queue有很大的作用,因为队列不是像单链表那样,队列是有它的特点的,其中最大的一个特点就是入栈只能从尾入,出栈就是头出,所以我们在这里定义head和tail有很大的作用,定义在结构体当中会方便不少,那我们现在继续往下看我们的接口函数吧。
给大家看一下下面实现队列的接口函数,然后我们一步一步的来实现他们
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
队列的初始化
void QueueInit(Queue* q);
初始化我们初始的是结构体Queue中的内容
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;
}
首先要判断传过来的指针是否是为空,然后将头指针和尾指针都置为NULL。
销毁队列
void QueuePush(Queue* q, QueueDataType data)
首先我们要创造一个节点将它放入,创造节点的结构体就是QueueNode,然后我们要更新后面节点中的head和tail,这里大家肯定有疑问,我们竟然是更新指针,那我们应该传指针的地址才能起到作用,一级指针只能改变结构体的内容,那我们在这里传的话,难道不会产生问题吗?答案是不会,我们的结构体中放的就是指针,那我们只需要改变结构体的内容,就是head和tail就行,竟然是这样的话,我们传一个一级指针就可以起到我们的作用,所以传的是一级,那现在我们在插入函数中先创造一个节点,因为只能从队列的尾插入,而且有了这个指针,我们就不需要像单链表那样再去找尾,我们每次插入都会更新尾。
void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail\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;}
}
有了入栈就有出栈,出栈的话是从我们的队列最开始的地方出队,我们来实现一下吧!
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}
/
这里的空是因为如果我们的队列都是空的话,我们哪里还有数据进行删除呢
所以要先检查一下是不是为空,那接着我们把这个函数也实现一下吧
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
这个很好理解,如果为空就代表一个数也没有,那我们就不能再对队列进行操作了,那再来看我们下面的接口函数吧。
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q);return q->head->data;
}
有头就有尾,希望我们的人生也是
那我再来实现一下取尾的接口吧
QueueDataType QueueBack(Queue* q)
{assert(q);return q->tail->data;
}
我们继续往下走,实现一下我们后面的接口函数,这些基本上都很简单,我就也不再解释了,看代码就能理解的
int QueueSize(Queue* q)
{assert(q);int count = 0;QueueNode* cur = q->head;while (cur){count++;cur = cur->next;}return count;
}
销毁队列
void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}}
统计我们队列节点的数量我们遍历一遍就可以实现了,定义一个cur指针进行遍历,那其他的我们也都讲完了,后面分享栈和队列的OJ题给大家,看完之后对队列有了更深的理解
完整代码
#include"Queue.h"// 初始化队列
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail\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;}
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);int count = 0;QueueNode* cur = q->head;while (cur){count++;cur = cur->next;}return count;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}}
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
今天的分享就到这里了,我们下次再见
相关文章:
数据结构队列的实现
本章介绍数据结构队列的内容,我们会从队列的定义以及使用和OJ题来了解队列,话不多说,我们来实现吧 队列 1。队列的概念及结构 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,…...
Gti的基本介绍和使用方式
Git 是一种分布式版本控制系统, 主要用于管理软件开发过程中的代码变更。其基本概念包括: 仓库 (Repository): Git中存储代码的基本单位,即一个代码库。在仓库中可以存储多个分支、标签、提交记录等。 分支 (Branch): Git中的分支是代码的不同开发方向,…...
剑指Offer 24-反转链表
题目描述:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 解题思路: 这道题做过很多次,还是会…...
小研究 - Java虚拟机即时编译器的一种实现原理
深入分析了 Kaffe虚拟机的 JIT(Just-In-Ti…...
【LeetCode】416.分割等和子集
题目 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示…...
go vet中的那些检测项
go vet 是 Go 语言自带的一个工具,用于分析 Go 代码中的常见错误和潜在问题。它可以检查代码中可能存在的各种问题,例如: 未使用的变量、函数或包 可疑的函数调用 错误的函数签名 程序中的竞态条件 错误的类型转换等 本文意图指令当前go vet所…...
Qt 自定义菜单、右键菜单
在接触Qt这段时间以来,经常遇到菜单项的问题(右键菜单、托盘菜单、按钮菜单等),QMenu用于菜单栏,上下文菜单,弹出菜单等,利用QMenuQAction就可以达到效果! 右键菜单实现:通过重写contextMenuEv…...
VScode 编辑器报错: ‘HelloWorld‘ is declared but its value is never read.
.vue文件被标识红色波浪线;提示: HelloWorld is declared but its value is never read. 问题原因: 因为vue3已经不支持vetur插件。 1、在扩展里面进行搜索Vetur插件,进行禁用或卸载; 2、在 VScode扩展里面搜索并下载…...
如何使用LLM实现文本自动生成视频
推荐:使用 NSDT场景编辑器 助你快速搭建可二次编辑的3D应用场景 介绍 基于扩散的图像生成模型代表了计算机视觉领域的革命性突破。这些进步由Imagen,DallE和MidJourney等模型开创,展示了文本条件图像生成的卓越功能。有关这些模型内部工作的…...
Rust处理JSON
基本操作 Cargo.toml: [package]name "json"version "0.1.0"edition "2021"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html[dependencies]serde { version "1", features …...
Python如何操作网络爬虫
Python是一种非常强大的编程语言,用于网络爬虫操作也非常方便。Python提供了许多用于构建和操作网络爬虫的库和工具,如BeautifulSoup、Scrapy、Requests等。本文将详细介绍Python如何操作网络爬虫。 一、安装相关库 首先,我们需要安装Python…...
linux文件复制覆盖命令
目录 cp 命令参数2.cp -rf 出现复制不覆盖文件问题3.解决文件复制覆盖提示操作问题,以下四种方式,供大家参考使用。方法1:编写带cp的路径复制覆盖文件方法2:在CP命令前面加一个斜杠\,实现强制覆盖文件方法3:…...
modbus概览
modbus Modbus是Modicon(施耐德)公司于1979年开发的串行通信协议。它最初设计用于公司的可编程逻辑控制器(PLC)。 Modbus是一种开放式协议,支持使用RS232/RS485/RS422协议的串行设备,同时还支持调制解调器…...
KMP算法开荒
文章目录 一 、前言二、 暴力解法三、KMP算法原理3.1 自动子串的指针3.2 跳过多少个字符3.3 next数组 - 暴力3.4 next数组 - 求解 四 KMP实现 一 、前言 字符串匹配 import re print(re.search(www, www.runoob.com).span()) # 在起始位置匹配 print(re.search(com, www.run…...
XXL-JOB(2)
Glue模式 任务以源码的形式去维护调度中心,支持实时编译,无需指定JobHandler。 实际上是继承自JobHandler的java类代码,在执行器中运行,可以使用Resource/Autowire注入执行器里中的其他服务. 在执行器中添加service Service p…...
Linux常用命令_网络命令、关机重启命令
文章目录 1. 网络命令1.1 网络命令: write1.2 网络命令: wall1.3 网络命令: ping1.4 网络命令: ifconfig1.5 网络命令: mail1.6 网络命令: last1.7 网络命令: lastlog1.8 网络命令: traceroute1.9 网络命令: netstat1.10 网络命令: setup1.11 挂载命令 2. 关机重启命令2.1 shut…...
用Cmake build OpenCV后,在VS中查看OpenCV源码的方法(环境VS2022+openCV4.8.0) Part I
用Cmake build OpenCV后,在VS中查看OpenCV源码的方法 Part I 写在最前面,最近这段时间的工作需要用opencv,不仅是调包,还要能够看到opencv的源码。然后就跟着网上的教程实现了一遍,在实现过程中,遇到了不少…...
如何使用Docker搭建ZooKeepe集群
1、拉取镜像 # docker pull zookeeper:3.7.12、创建网络 Docker创建容器时默认采用bridge网络,自行分配ip,不允许自己指定。在实际部署中,需要指定容器ip,不允许其自行分配ip,尤其在搭建集群时。可以通过docker netw…...
【javaweb】学习日记Day3 - Ajax 前后端分离开发 入门
目录 一、Ajax 1、简介 2、Axios (没懂 暂留) (1)请求方式别名 (2)发送get请求 (3)发送post请求 (4)案例 二、前端工程化 1、Vue项目-目录结构 2、…...
SQL注入漏洞复现:探索不同类型的注入攻击方法
这篇文章旨在用于网络安全学习,请勿进行任何非法行为,否则后果自负。 准备环境 sqlilabs靶场 安装:详细安装sqlmap详细教程_sqlmap安装教程_mingzhi61的博客-CSDN博客 一、基于错误的注入 注入讲解 介绍 基于错误的注入(Err…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
