(超详细)数据结构——“队列”的深度解析

 

目录

 

前言:

1.队列的概念   

2.队列的实现 

3.代码实现队列 

3.1 队列的初始化 

3.2 插入 

3.3 删除 

3.4 队列的队头,队尾和大小

3.5 判空 

3.6 销毁 

3.7 测试 

 


前言:

    队列与栈都是线性表,它们的结构也非常类似,都是一头进一头出,那么它们有什么区别吗?答案是有的,虽然它们同为线性表,但是栈的出栈入栈方式为后进先出,而队列的出栈入栈方式为先进先出,具体我们在正文讲解。

1.队列的概念   

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

2.队列的实现 

    队列与栈的结构类似,所以它和栈一样,使用链表和顺序表都可以实现队列,但是由于队列遵循先进先出的顺序,如果使用顺序表进行头删实现出队列的话,整个队列的数据需要频繁向前移动,代码效率相对较低,而使用链表的头删实现出队列的话,只需要将头节点删除即可,所以综上所述,我们将使用链表来实现队列。

3.代码实现队列 

    为了方便管理,我们还是将队列分为三个文件实现,分别是Queue.h (queue中译是队列的意思),Queue.c和test.c,由于我们选择使用链表实现队列,所以我们要先使用结构体实现一个单链表的节点,这个节点包含数据和下一个节点的地址,存储数据变量的类型由我们将来要存储的数据决定,所以我们使用typedef队对数据类型进行改名,在这里我们将int作为测试类型,所以我们要对int重命名:

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

   基于队列先进先出的原则,我们需要得到队列的头和尾,必要时还需要知道队列的大小,所以我们额外创建一个结构体来存储队列的首地址,尾地址和队列的大小:

typedef struct Queue
{QNode* Qtail;QNode* Qhead;int size;}Queue;

3.1 队列的初始化 

   我们现在有两个结构体,我们该如何初始化呢?是对两个结构体都初始化,还是对其中某一个初始化呢。答案是对存储有队列首地址和尾地址的结构体初始化,因为代表链表节点的QNode结构体的初始化是在我们在堆上开辟新的空间时初始化,所以我们这个时候的初始化是对Queue初始化:

void QInit(Queue* pq)
{assert(pq);pq->Qhead = pq->Qtail = NULL;pq->size = 0;}//初始化

3.2 插入 

    我们这里的队列使用的是单链表,所以插入要使用尾插,删除使用头插,单链表的这两个操作完美的符合队列的先进先出的特性。在插入数据前,我们要先开辟一个新节点,如果这个节点有效,我们就对它初始化,让它的next指针指向空,将x赋给val。将新节点初始化完了之后,我们就要考虑插入的问题了,如果队列里没有任何成员,我们要插入的新节点就要同时赋给头指针和尾指针,如果队列里有成员,我们插入的新节点就只需要给尾指针的next指针,执行完插入操作后让size加1:

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->Qhead == NULL){pq->Qhead = pq->Qtail = newnode;}else{pq->Qtail->next = newnode;pq->Qtail = newnode;}pq->size++;
}//插入

3.3 删除 

    删除操作我们在前面讲过要使用头删,我们需要考虑队列是否为空,如果队列为空,则让程序无法执行删除操作,我们选择使用断言来限制队列为空使用删除的情况,与插入相同,我们需要考虑两种情况,如果队列中只有只有一个成员,那么这个成员同时被头指针和尾指针指着,如果我们要删除这个节点,那么我们要将头指针和尾指针同时置空,这样做是为了防止出现空指针的现象。第二种则是正常情况,我们用一个指针存储头指针的下一个节点的地址,将头指针指向的那块空间释放后(删除节点),再让头指针指向我们之前存储的地址,这样删除操作就算完成了:

void QueuePop(Queue* pq)
{assert(pq);assert(pq->Qhead);if (pq->Qhead->next == NULL){free(pq->Qhead);pq->Qhead = pq->Qtail = NULL;}else{QNode* next = pq->Qhead->next;free(pq->Qhead);pq->Qhead = next;}pq->size--;
}//删除

3.4 队列的队头,队尾和大小

  队列的队头和队尾只需要将头指针和尾指针指向成员的值返回就可以了,而队列的大小也比较简单,只需要返回size就可以了:

队头:

DataType QueueFront(Queue* pq)
{assert(pq);return pq->Qhead->val;
}

队尾:

QDataType QueueBack(Queue* pq)
{assert(pq);return pq->Qtail->val;
}

队列大小:

int Queuesize(Queue* pq)
{assert(pq);assert(pq->size >= 0);return pq->size;
}//大小

3.5 判空 

  我们有时会频繁对队列进行删除插入操作,这时我们可以使用这个方法来决定是否删除,如果队列为空,则不进行删除操作:

bool QEmpty(Queue* pq)
{assert(pq);assert(pq->size >= 0);return pq->size == 0;
}//判空

3.6 销毁 

  我们链表的节点都是从堆上开辟的,所以要手动将这些空间释放:

void QDestroy(Queue* pq)
{assert(pq);Queue* cur = pq->Qhead;while (cur){QNode* next = cur->Qhead->next;free(cur->Qhead);cur->Qhead = next;}pq->Qhead = pq->Qtail = NULL;pq->size = 0;
}

3.7 测试 

  到这里队列所有的方法都已经实现了,实现完之后不要忘记测试一下代码的有效性,我们来测试一下我们实现的方法:

我们插入了四个数字,然后使用判空,队头和删除方法来打印队列,可以看到都是没有问题的,讲到这里,队列就到此结束了,代码放在下面,感兴趣的小伙伴可以试试哦。

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* Qtail;QNode* Qhead;int size;}Queue;void QInit(Queue* pq);//初始化void QueuePush(Queue* pq, QDataType x);//插入void QueuePop(Queue* pq);//删除int Queuesize(Queue* pq);//大小//头尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);void QDestroy(Queue* pq);//销毁

Queue.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"void QInit(Queue* pq)
{assert(pq);pq->Qhead = pq->Qtail = NULL;pq->size = 0;}//初始化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->Qhead == NULL){pq->Qhead = pq->Qtail = newnode;}else{pq->Qtail->next = newnode;pq->Qtail = newnode;}pq->size++;
}//插入void QueuePop(Queue* pq)
{assert(pq);assert(pq->Qhead);if (pq->Qhead->next == NULL){free(pq->Qhead);pq->Qhead = pq->Qtail = NULL;}else{QNode* next = pq->Qhead->next;free(pq->Qhead);pq->Qhead = next;}pq->size--;
}//删除int Queuesize(Queue* pq)
{assert(pq);assert(pq->size >= 0);return pq->size;
}//大小//头、尾数据
QDataType QueueFront(Queue* pq)
{assert(pq);return pq->Qhead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);return pq->Qtail->val;
}bool QEmpty(Queue* pq)
{assert(pq);assert(pq->size >= 0);return pq->size == 0;
}//判空void QDestroy(Queue* pq)
{assert(pq);Queue* cur = pq->Qhead;while (cur){QNode* next = cur->Qhead->next;free(cur->Qhead);cur->Qhead = next;}pq->Qhead = pq->Qtail = NULL;pq->size = 0;
}

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void test()
{Queue q;QInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);while (!QEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QDestroy(&q);}
int main()
{test();return 0;
}

 

 

 

 

 

 

 

 

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

“论单元测试方法及应用”写作框架,软考高级论文,系统架构设计师论文

论文真题 1、概要叙述你参与管理和开发的软件项目,以吸你所担的主要工作。 2、结给你参与管理和开发的软件项目&#xff0c;简要叙述单元测试中静态测试和动态测试方法的基本内容。 3、结给你惨与管理和研发的软件项目,体阐述在玩测试过程中,如何确定白盒测试的覆盖标准,及如…

Three.js机器人与星系动态场景:实现3D渲染与交互式控制

内容摘要&#xff1a;使用Three.js库构建了一个交互式的3D场景。组件中创建了一个机器人模型&#xff0c;包括头部、眼睛、触角、身体和四肢&#xff0c;以及两个相同的机器人实例以实现动态效果。场景中还加入了粒子效果&#xff0c;模拟星系环境&#xff0c;增强了视觉效果。…

设备调试上位机GUI

C Fast Qt C 前端 原来真的不需要在 design 上画来画去&#xff0c;有chat-gpt 那里不知道问哪里 全是组件拼起来的,不需要画,最后发现其实也是定式模式,跟着AI 学套路

JavaScript将参数传递给事件处理程序

本篇文件我们将实现导航栏中&#xff0c;选中时候&#xff0c;会将您选中的进行高亮显示&#xff1b; ● 首先我们来获取我们想要的HTML元素 const nav document.querySelector(.nav);● 接着我们来写选中的高亮显示 nav.addEventListener(mouseover, function (e) { //鼠…

Python系统教程01

Python 是一门解释性语言&#xff0c;相对更简单、易学&#xff0c;它可以用于解决数学问题、获取与分 析数据、爬虫爬取网络数据、实现复制数学算法等等。 1、print()函数&#xff1a; print()书写时注意所有的符号都是英文符号。print()输出内容时&#xff0c;若要输出字符…

安卓实现微信聊天气泡

一搜没一个能用的&#xff0c;我来&#xff1a; 布局文件&#xff1a; <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xml…

【MySQL】数据库事务详解

文章目录 前言1. 事务的定义2. 事务的四个特性2.1 原子性2.2 一致性2.3 隔离性2.4 持久性 3. 事务的并发问题3.1 脏读3.2 不可重复读3.3 幻读3.4 更新丢失 4. 事务的隔离级别5. 事务的使用结语 前言 假设我们现在需要操作数据库进行转账&#xff0c;A 给 B 转账 100 块钱&…

掌握React与TypeScript:从零开始绘制中国地图

最近我需要使用reactts绘制一个界面&#xff0c;里面需要以中国地图的形式展示区块链从2019-2024年这五年的备案以及注销情况&#xff0c;所以研究了一下这方面的工作&#xff0c;初步有了一些成果&#xff0c;所以现在做一些分享&#xff0c;希望对大家有帮助&#xff01; 在这…

【Kotlin】Kotlin 基础语法指南

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…

基于TCP/QT/C++的网盘系统测试报告

目录 一、项目介绍 1、项目描述 2、项目组成模块 3、项目技术要点 二、用户功能测试 1、查看在线用户测试 1.1、运行服务器 1.2、登录两个账号 1.3、点击显示在线用户&#xff0c;可以看到jack和lucy 2、搜索用户测试 2.1、打开服务器&#xff0c;登录两个账号jack,lucy 2.2、在…

嵌入式学习——硬件(IIC、ADC)——day56

1. IIC 1.1 定义&#xff08;同步串行半双工通信总线&#xff09; IIC&#xff08;Inter-Integrated Circuit&#xff09;又称I2C&#xff0c;是是IICBus简称&#xff0c;所以中文应该叫集成电路总线。是飞利浦公司在1980年代为了让主板、嵌入式系统或手机用以连接低速周边设备…

Linux高并发服务器开发(八)Socket和TCP

文章目录 1 IPV4套接字结构体2 TCP客户端函数 3 TCP服务器流程函数代码粘包 4 三次握手5 四次挥手6 滑动窗口 1 IPV4套接字结构体 2 TCP客户端 特点&#xff1a;出错重传 每次发送数据对方都会回ACK&#xff0c;可靠 tcp是打电话的模型&#xff0c;建立连接 使用连接 关闭连接…

【代码随想录】【算法训练营】【第49天】 [300]最长递增子序列 [674]最长连续递增序列 [718]最长重复子数组

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 day 49&#xff0c;周二&#xff0c;坚持不了一点~ 题目详情 [300] 最长递增子序列 题目描述 300 最长递增子序列 解题思路 前提&#xff1a;最大递增子序列的长度 思路&#xff1a;动态规划 d…

RedHat9 | podman容器-续集

一、管理容器存储和网络资源 使用容器来运行简单的进程&#xff0c;然后退出。可以配置容连续运行特定服务&#xff0c;如数据库服务。如果持续运行服务&#xff0c;需要向容器添加更多的资源&#xff0c;如持久存储或对其他网络的访问权限。 针对企业容器平台上的大型部署&a…

汽车零部件材料耐候性测试氙光太阳辐射系统试验箱

概述 汽车零部件等领域的材料耐候性测试是一项关键的质量控制环节&#xff0c;它关乎汽车部件在各种气候条件下的性能表现和寿命。塑料件光照老化实验箱&#xff0c;即氙灯老化试验箱&#xff0c;在其中扮演着至关重要的角色。通过模拟自然环境中的光照、温度、湿度等条件&…

遇到多语言跨境电商系统源码问题?这里有解决方案!

从手机到电脑&#xff0c;从线下到线上&#xff0c;如今&#xff0c;跨境电商正在打破地域界限&#xff0c;成为全球贸易的新引擎。在这个全球化的背景下&#xff0c;跨境电商平台的运营也面临着一系列的挑战&#xff0c;其中之一就是多语言问题。如果你遇到了多语言跨境电商系…

【HALCON】如何实现hw窗口自适应相机拍照成像的大小

前言 在开发一个喷码检测软件的时候碰到相机成像和hw窗体的大小不一致&#xff0c;hw太小显示不完全成像的图片&#xff0c;这使得成像不均匀&#xff0c;现场辨别起来比较不直观&#xff0c;因此需要对其进行一个调整。 解决 省略掉读取图片的环节&#xff0c;我们只需要将…

全国产化飞腾模块BIOS下修复系统启动文件

1、背景介绍 全国产飞腾模块采用麒麟信安操作系统&#xff0c;当系统下面的grub.cfg文件被用户误操作导致无法启动时&#xff0c;可以在BIOS下通过U盘中备份的grub.cfg替换硬盘上原来的grub.cfg文件&#xff0c;从而实现启动。 2、操作步骤 首先进入BIOS命令行模式&#xff…

2.3章节Python中的数值类型

1.整型数值 2.浮点型数值 3.复数   Python中的数值类型清晰且丰富&#xff0c;主要分为以下几种类型&#xff0c;每种类型都有其特定的用途和特性。 一、整型数值 1.定义&#xff1a;整数类型用于表示整数值&#xff0c;如1、-5、100等。 2.特点&#xff1a; Python 3中的…

Ubuntu(通用)—网络加固—ufw+防DNS污染+ARP绑定

1. ufw sudo ufw default deny incoming sudo ufw deny in from any to any # sudo ufw allow from any to any port 5353 protocol udp sudo ufw enable # 启动开机自启 # sudo ufw reload 更改后的操作2. 防ARP欺骗 华为云教程 arp -d删除dns记录arp -a显示arp表 ipconfi…