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

带你深入了解队列(c/cpp双版本模拟实现)

目录

一.队列的概念及结构

二.队列的实现

2.1队列的结构

2.2初始化队列

2.3队尾入队列 

2.4队头出队列 

2.5获取队列头部元素 

2.6获取队列队尾元素

2.7获取队列中有效元素个数 

2.8检测队列是否为空

2.9销毁队列 

三.C++ 版本模拟实现队列


一.队列的概念及结构

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

二.队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

2.1队列的结构

首先,先建立一个单链表,用来存储数据和链接结构

然后建立队列,队列有俩个节点,一个指向队列的开始,一个指向结尾

size 用于存储队列长度

// 链式结构:表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;

2.2初始化队列

队列的初始化,把队列的头尾都指向空,size设为0

void QueueInit(Queue* q)
{q->front = NULL;q->rear = NULL;q->size = 0;
}

2.3队尾入队列 

1.首先,malloc一个节点cur

2.判断malloc是否开辟成功

3.给创建成功的节点进行赋值

4.判断如果队列为空,直接插入节点即可(使队列的头尾都指向这个节点)

5.如果不为空,使队列的尾的下一个位置指向新创建的节点在然后队列的尾指向这个节点

6.最后,数据加一size++

void QueuePush(Queue* q, QDataType data)
{QNode* cur = (QNode*)malloc(sizeof(QNode));if (cur == NULL){perror("malloc ");exit(-1);}cur->data = data;cur->next = NULL;if (q->rear == NULL){q->front = q->rear = cur;}else{q->rear->next = cur;q->rear = cur;}q->size++;
}

2.4队头出队列 

1.先判断队列是否只有为空,如果是,退出

2.如果队列只有一个数据,直接对队列进行销毁即可

3.如果队列有多个数据,新建一个节点cur等于队列“头”的下一个地址,然后释放掉队头,再把队头指向cur(以前对头的下一个地址),使得第二个数据成为队头

4.最后,数据减一size--

void QueuePop(Queue* q)
{if(q->front==NULL){exit(-1);}if (q->front->next == NULL){free(q->front);q->front = q->rear = NULL;}else{QNode* cur = q->front->next;free(q->front);q->front = cur;}q->size--;
}

2.5获取队列头部元素 

直接取头指向的数据即可

QDataType QueueFront(Queue* q)
{return q->front->data;
}

2.6获取队列队尾元素

直接取队列尾指向的元素即可

QDataType QueueBack(Queue* q)
{return q->rear->data;
}

2.7获取队列中有效元素个数 

直接返回队列的size

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

2.8检测队列是否为空

检测队列是否为空,如果为空返回非零结果,如果非空返回0 

bool QueueEmpty(Queue* q)
{return q->front == NULL && q->rear == NULL;
}

2.9销毁队列 

1.采用while循环依次把队列中的节点全部释放

2.使队列头尾指向空,并且size置为0

void QueueDestroy(Queue* q)
{QNode* cur = q->front;while (cur){QNode* del = cur;cur = cur->next;free(del);}q->front = NULL;q->rear = NULL;q->size = 0;
}

三.C++ 版本模拟实现队列
 

     考虑到学校有好多老师上课,虽然说得是用c语言实现,却用cpp进行操作,现在给大家更新cpp版本的队列的模拟实现,cpp版本的扩容使用的new,函数参数使用的&,可能有同学对指针使用不太熟悉,所以我们同意用&(引用)来实现,方便大家的理解,就不再详细的进行说明了,思路跟c语言实现的一样,只是c和cpp的语言差距有所不同。

#include<iostream>
#include<assert.h>
using namespace std;typedef  int  QDataType;typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;// 初始化队列 
void QueueInit(Queue& q)
{q.front = NULL;q.rear = NULL;q.size = 0;
}
// 队尾入队列 
void QueuePush(Queue& q, QDataType data)
{QNode* cur = new QNode[sizeof(QNode)];if (cur == NULL){perror("malloc ");exit(-1);}cur->data = data;cur->next = NULL;if (q.rear == NULL){q.front = q.rear = cur;}else{q.rear->next = cur;q.rear = cur;}q.size++;
}
// 队头出队列 
void QueuePop(Queue& q)
{if (q.front->next == NULL){delete q.front;q.front = q.rear = NULL;}else{QNode* cur = q.front->next;delete q.front;q.front = cur;}q.size--;
}
// 获取队列头部元素 
QDataType QueueFront(const Queue& q)
{return q.front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(const Queue& q)
{return q.rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(const Queue& q)
{return q.size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(const Queue& q)
{return q.front == NULL && q.rear == NULL;
}
// 销毁队列 
void QueueDestroy(Queue& q)
{QNode* cur = q.front;while (cur){QNode* del = cur;cur = cur->next;free(del);}q.front = NULL;q.rear = NULL;q.size = 0;
}int main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);for (int i = 0;i < 3;i++){cout << QueueFront(q) << endl;QueuePop(q);}printf("%d", !QueueEmpty(q));QueueDestroy(q);return 0;
}

相关文章:

带你深入了解队列(c/cpp双版本模拟实现)

目录 一.队列的概念及结构 二.队列的实现 2.1队列的结构 2.2初始化队列 2.3队尾入队列 2.4队头出队列 2.5获取队列头部元素 2.6获取队列队尾元素 2.7获取队列中有效元素个数 2.8检测队列是否为空 2.9销毁队列 三.C 版本模拟实现队列 一.队列的概念及结构 队列…...

接口自动化测试实操

实现思路 使用excel管理用例用例信息&#xff0c;requests模块发送http请求&#xff0c;实现了记录日志&#xff0c;邮件发送测试报告的功能 目录结构如下&#xff1a; 下面直接上代码&#xff1a; 统筹脚本 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24…...

Virtual DOM

目录 Virtual DOM 前言 用法 代码 理解 Virtual DOM的工作原理&#xff1a; 为什么使用Virtual DOM? 哪些库/框架使用Virtual DOM? 总结 Virtual DOM&#xff08;虚拟DOM&#xff09;是一种编程概念&#xff0c;它是对真实DOM的轻量级抽象表示。在前端开发中&#x…...

数据结构与算法-二叉树的遍历

&#x1f31e; “少年没有乌托邦&#xff0c;心向远方自明朗&#xff01;” 二叉树 &#x1f388;1.二叉树的遍历&#x1f52d;1.1先序遍历&#x1f52d;1.2中序遍历&#x1f52d;1.3后序遍历&#x1f52d;1.4层次遍历&#x1f52d;1.5二叉树遍历的递归算法&#x1f4dd;1.5.1先…...

Qt之普通项目如何生成DLL(含源码+注释)

文章目录 一、示例图二、普通项目需要改造的内容三、源码&#xff08;创建了一个TestDLL的项目&#xff0c;更改内容主要在pro文件和maindow.h文件&#xff09;TestDLL.promainwindow.hmainwindow.cppmainwindow.ui 总结 一、示例图 使用不同的编译模式编译&#xff0c;会在对…...

Java注解及自定义注解

注解/元数据&#xff08;Annotation&#xff09;&#xff0c;是对代码级别的说明&#xff1b;在JDK1.5及以后版本引入的一个特性&#xff0c;与类、接口、枚举是在同一个层次。可以声明在包、类、字段、方法、局部变量、方法参数等的前面&#xff0c;用来对这些元素进行说明、注…...

ps2024滤镜插件Portraiture

Photoshop 是最常用到的综合性的设计工具&#xff0c;虽然PS一直在迭代升级&#xff0c;但是在细节功能上&#xff0c;PS总是无法完全满足全部所有的用户需求&#xff0c;今天coco玛奇朵推荐一个个截至目前最受欢迎的免费的PS插件&#xff0c;有了这些功能扩展的插件后PS如虎添…...

Vue 实战项目(智慧商城项目): 完整的订单购物管理功能 内涵资源代码 基于Vant组件库 Vuex态管理 基于企业级项目开发规范

鹏鹏老师的实战开发项目 文章目录 智慧商城项目01. 项目功能演示1.明确功能模块2.项目收获 02. 项目创建目录初始化vue-cli 建项目 03. 调整初始化目录结构1.删除文件2.修改文件3.新增目录 04. vant组件库及Vue周边的其他组件库05. 全部导入和按需导入的区别06. 全部导入07. 按…...

JVM——一些零散的概念(后续学习深入了再补充)

Native 凡是带了native关键字的&#xff0c;说明Java的作用范围的达不到了&#xff0c;需要调用底层C语言的库 调用native方法&#xff0c;会进入本地方法栈&#xff0c;调用本地接口(JNI) JNI的作用&#xff1a;扩展Java的使用&#xff0c;融合不同的编程语言为Java所用 它在内…...

OpenCV学习(三)——响应鼠标事件(获取点击点坐标和颜色,利用鼠标进行绘图)

响应鼠标事件 3. 响应鼠标事件3.1 获取鼠标点击的坐标3.2 获取鼠标点击像素点的颜色3.3 在鼠标点击的位置生成圆3.4 通过拖动鼠标来绘制填充矩形3.5 通过拖动鼠标绘制未填充矩形3.6 使用鼠标选点绘制多边形3.7 按住鼠标左键进行绘图 3. 响应鼠标事件 使用OpenCV读取图像&#…...

基于安卓android微信小程序的投票系统

项目介绍 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;投票系统小程序被用户普遍使用&#xff0c;为方便用户…...

没有上司的舞会

有了上一篇博客&#xff0c;没有看上一篇博客的可以看看上一篇博客&#xff0c;我们对没有上司的舞会这道题会有更好的理解~ 所以关键的思路就是确定对于每一个节点我们应该维护什么内容才是最合适的&#xff0c;这个题目和上一篇博客的最后一道题目很相似&#xff0c;我们思考…...

2.18每日一题(不直接给f(x)的定积分及变上限积分)

...

RHCE8 资料整理(四)

RHCE8 资料整理 第四篇 存储管理第13章 硬盘管理13.1 对磁盘进行分区13.2 交换分区&#xff08;swap分区&#xff09; 第14章 文件系统14.1 了解文件系统14.2 了解硬链接14.3 创建文件系统14.4 挂载文件系统14.5 设置永久挂载14.6 查找文件14.7 find的用法 第15章 逻辑卷管理15…...

目标跟踪ZoomTrack: Target-aware Non-uniform Resizing for Efficient Visual Tracking

论文作者&#xff1a;Yutong Kou,Jin Gao,Bing Li,Gang Wang,Weiming Hu,Yizheng Wang,Liang Li 作者单位&#xff1a;CASIA; University of Chinese Academy of Sciences; ShanghaiTech University; Beijing Institute of Basic Medical Sciences; People AI, Inc 论文链接&…...

Flink Data Sink

本专栏案例代码和数据集链接: https://download.csdn.net/download/shangjg03/88477960 1. Data Sinks 在使用 Flink 进行数据处理时,数据经 Data Source 流入,然后通过系列 Transformations 的转化,最终可以通过 Sink 将计算结果进行输出,Flink Data Sinks 就是用于定义…...

机器学习——正则化

正则化 在机器学习学习中往往不知道需要不知道选取的特征个数&#xff0c;假如特征个数选取过少&#xff0c;容易造成欠拟合&#xff0c;特征个数选取过多&#xff0c;则容易造成过拟合。由此为了保证模型能够很好的拟合样本&#xff0c;同时为了不要出现过拟合现象&#xff0…...

【c++】打家劫舍(动态规划)

打家劫舍 题目难度&#xff1a;高阶 时间限制&#xff1a;1000ms 内存限制&#xff1a;256mb 题目描述 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff…...

eslint提示 xxx should be listed in the project's dependencies

有时候手动安装了一个npm包A&#xff0c;npm包A里面包含了npm包B&#xff0c;这时候如果 import xxx from npm包B;eslint会报错&#xff0c;提示 npm包B 不在 package.json 里面 解决方法&#xff1a;在 eslintrc.js 增加配置 module.exports {rules: {import/no-extraneous-d…...

H3C LC-5120-52SC-HI配置管理IP

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、MGMT是什么&#xff1f;二、配置步骤1.连接ConsoleWindowsLinux1.配置minicom2.使用minicom 2.配置管理端口3.配置Web管理4.http其它配置项 总结 前言 最近…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

全面解析各类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&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...