【数据结构-初阶】详解线性表(5)---队列

Ne0inhk

— 10 min read
【数据结构-初阶】详解线性表(5)---队列

🎈主页传送门:良木生香

🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》

🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
上期回顾:在上一篇文章(【数据结构-初阶】详解栈和队列(1)---栈)中我们讲到了在顺序表与链表之外的另一种线性表---栈,知道了这是一种具有先进后出和后进先出特点的数据结构,既然有先进后出,那么肯定就有先进先出的数据结构,所以这就是我们今天要讲的------队列

一、队列的概念

既然我们想要实现先进先出的效果，那肯定就不像栈那样有一端是堵起来的，想必应该是两端都开口吧。嗯，事实确实如此。

队列：是只允许在一端进行数据的插入操作，在另一端进行数据的删除操作的一种特殊的线性表，其具有先进先出FIFO(first in first out)的结构特点.

入队列:进行插入操作的一端叫做队尾

出队列:进行删除操作的一端叫做队头

下面是队列的示意图:

名字叫做队列,其实就像我们排队一样,先排的人先得服务,后排的人后得到服务,在队列中,先进来的元素先得到操作,后进来的服务后得到操作

 

二、队列的实现

想要实现队列,我们就要考虑与实现栈时一样的问题,那就是:底层用数组实现还是用链表实现?

首先我们来分析一下,队列是需要在队尾和队头进行频繁操作的数据结构,队尾通常容易实现,但是相较于队头,数组要实现所需要的时间成本就要远远大于链表了,所以综上所述,我们决定用链表为底来实现队列

2.1、队列的结构

既然底层用的是链表实现，那么接涉及到节点的问题，我们依旧将队列的节点设置成与链表节点相同即可。但这时候又有一个新的问题：用单链表还是双链表？我们依旧是从队列的定义出发。既然是一端进一端出，那只用考虑头尾位置的节点就行，不会像顺序表或者链表那样涉及到pos位置的插入删除,同时兼顾运行效率,我们决定采用单链表的作为队列节点的结构,这样一来,队列节点的结构就成了这样:
//现在定义队列节点: typedef struct QueueNode { Elemtype data; //数据域 struct QueueNode* next; //指针域 }QueueNode;

在队列中,哦不,应该说是在链表中,我们对于头部删除的操作是很方便的,但是队尾部插入的话就要经常遍历一遍链表然后再能进行操.像队列这种经常对队尾进行操作的数据结构,我们总不能每次插入都遍历一遍吧?这样的话真的就比老奶奶过马路还慢了,所以我们要定义一个尾指针,使它一直指向尾结点,所以下面才是队列真正的结构体:

//现在定义队列结构体: typedef struct Queue { QueueNode* phead; QueueNode* ptail; }Queue;

 

 

2.2、队列的初始化

队列的初始化与其他数据结构一样，都是对自己结构体里面的元素进行初始化，那在队列中，我们是对队列的节点进行初始化呢？还是对队列的头尾指针进行初始化呢？答案是对队列的头尾指针进行初始化，因为队列这个数据结构我们对是对头尾指针进行操作的，对于节点只是一个过程而已：
//现在初始化队列: void Init_Queue(Queue* pQueue) { pQueue->phead = pQueue->ptail = NULL; }

将两个指针置为空就行

 

 

2.3、入队

队列的入队一般是在队尾进行操作的，我们在编写代码的时候要留个心眼，如果当前队列一个元素都没有，那在插入的时候就是头尾指针指向同一个节点，如果队列中已经有元素了，那就只用对尾指针进行操作，最后记得将尾指针指向最新的节点下面是具体代码：
//现在是入队列 void Push_Queue(Queue* pQueue,Elemtype data) { assert(pQueue); //创建新节点 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { printf("新节点创建失败....\n"); return; } newNode->data = data; newNode->next = NULL; if (pQueue->phead == NULL) { //说明是头节点 pQueue->phead = pQueue->ptail = newNode; } //ptail newNode pQueue->ptail->next = newNode; pQueue->ptail = newNode; size++; //这是用来记录当前队列有效元素个数的变量的 }

 

 

2.4、出队

出队一般来说是对头指针进行操作的，与入队一样，我们也考虑到当队列中只有一个元素时，释放完头指针，要将头指针与尾指针同时置为NULL，如果队列中不止一个元素，那就只用对头指针进行操作，然后将头指针指向下一个元素，下面是具体的代码：
//出队列 void Pop_Queue(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法出队...\n"); return; } //如果只有一个节点 if (pQueue->phead == pQueue->ptail) { free(pQueue->phead); pQueue->phead = pQueue->ptail = NULL; } //phead phaed->next //delet phead else { QueueNode* delet = pQueue->phead; pQueue->phead = pQueue->phead->next; free(delet); delet = NULL; } size--; //这是用来记录当前队列中有效元素个数的变量 }

 

2.5、取队头队尾数据：

这个操作相对简单一点，我们只用返回队头队尾的节点元素即可，代码如下：
//取队头元素 Elemtype Get_first_elem(Queue* pQueue) { assert(pQueue); return pQueue->phead->data; } //取队尾元素 Elemtype Get_tail_elem(Queue* pQueue) { assert(pQueue); return pQueue->ptail->data; }

这里要注意的是，我们在设计返回类型的时候，要将返回值设置为我们想要的类型，在这里我提前将int 类型重命名为了Elmetype ,在代码总和那一块我会展示出来。

 

2.6、队列中有效的元素个数

在这个操作中，我们有两种操作方式，第一种就是传统的使用遍历的方式，将节点数一一记录下来；第二种就是在入队的时候用一个变量size++,在出队的时候对size--,这样就能实时更新队列中的元素个数了,第二种方式在返回个数的时候要比第一种快很多,下面是两种代码的展示:

//第一种的传统方式: //计算队列中有效的元素个数 int Size_Queue(Queue* pQueue) { assert(pQueue); int size = 0; QueueNode* pcur = pQueue->phead; while (pcur) { size++; pcur = pcur->next; } return size; } //第二种返回方式 int Size_Queue(Queue* pQueue,int size){ assert(pQueue)); return size; }

 

 

2.7、队列的销毁

队列的销毁与链表的销毁相同，用遍历指针逐一将节点一一销毁，最后将头尾指针置为NULL:
void Destory_Queue(Queue* pQueue) { assert(pQueue); QueueNode* pcur = pQueue->phead; while (pcur) { QueueNode* delet = pcur; pcur = pcur->next; free(delet); delet = NULL; } pQueue->phead = pQueue->ptail = NULL; }

要提醒的是,一定要将头尾指针置为NULL,不要这两个指针会成为野指针!!!!

 

 

三、综合代码

#define _CRT_SECURE_NO_WARNINGS 520 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<windows.h> typedef int Elemtype; //现在定义队列节点: typedef struct QueueNode { Elemtype data; //数据域 struct QueueNode* next; //指针域 }QueueNode; //现在定义队列结构体: typedef struct Queue { QueueNode* phead; QueueNode* ptail; }Queue; //现在初始化队列: void Init_Queue(Queue* pQueue) { pQueue->phead = pQueue->ptail = NULL; } //现在是入队列 void Push_Queue(Queue* pQueue,Elemtype data) { assert(pQueue); //创建新节点 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { printf("新节点创建失败....\n"); return; } newNode->data = data; newNode->next = NULL; if (pQueue->phead == NULL) { //说明是头节点 pQueue->phead = pQueue->ptail = newNode; } //ptail newNode pQueue->ptail->next = newNode; pQueue->ptail = newNode; } //出队列 void Pop_Queue(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法出队...\n"); return; } //如果只有一个节点 if (pQueue->phead == pQueue->ptail) { free(pQueue->phead); pQueue->phead = pQueue->ptail = NULL; } //phead phaed->next //delet phead else { QueueNode* delet = pQueue->phead; pQueue->phead = pQueue->phead->next; free(delet); delet = NULL; } } //取队头元素 Elemtype Get_first_elem(Queue* pQueue) { assert(pQueue); return pQueue->phead->data; } //取队尾元素 Elemtype Get_tail_elem(Queue* pQueue) { assert(pQueue); return pQueue->ptail->data; } //计算队列中有效的元素个数 int Size_Queue(Queue* pQueue) { assert(pQueue); int size = 0; QueueNode* pcur = pQueue->phead; while (pcur) { size++; pcur = pcur->next; } return size; } void Destory_Queue(Queue* pQueue) { assert(pQueue); QueueNode* pcur = pQueue->phead; while (pcur) { QueueNode* delet = pcur; pcur = pcur->next; free(delet); delet = NULL; } pQueue->phead = pQueue->ptail = NULL; } //现在是打印队列 void my_printf(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法打印...\n"); return; } else { QueueNode* pcur = pQueue->phead; while (pcur) { printf("%d ", pcur->data); pcur = pcur->next; } } } //现在是打印菜单 void printf_menu() { printf("=========================================\n"); printf("1.入队 2.出队\n"); printf("3.取队头元素 4.取队尾元素\n"); printf("5.计算队列元素个数\n"); printf("=========================================\n"); printf("\n"); } int main() { Queue L; Queue* pQueue = &L; Init_Queue(pQueue); int choose; do { system("cls"); printf_menu(); printf("当前的队列为:\n"); my_printf(pQueue); printf("\n"); printf("请输入你的选择:\n"); scanf("%d", &choose); switch (choose) { case 1: { printf("请输入你想输入的元素个数:\n"); int num = 0; scanf("%d", &num); Elemtype data = 0; printf("请输入你想输入的元素:\n"); for (int i = 0; i < num; i++) { scanf("%d", &data); Push_Queue(pQueue, data); } printf("正在输入...\n"); Sleep(1000); printf("输入成功~\n"); Sleep(2000); break; } case 2: { printf("正在出队...\n"); Sleep(1000); Pop_Queue(pQueue); printf("出队成功~\n"); Sleep(2000); break; } case 3: { Elemtype elem = Get_first_elem(pQueue); printf("正在取出对队头元素...\n"); Sleep(1000); printf("队头元素为: %d", elem); Sleep(2000); break; } case 4: { Elemtype elem = Get_tail_elem(pQueue); printf("正在取出对队尾元素...\n"); Sleep(1000); printf("队尾元素为: %d", elem); Sleep(2000); break; } case 5: { printf("正在计算队列大小...\n"); int num = Size_Queue(pQueue); Sleep(1000); printf("队列的大小为: %d", num); Sleep(1000); break; } case -1: { printf("正在退出程序...\n"); Sleep(1000); printf("退出成功~\n"); Sleep(500); } } } while (choose != -1); Destory_Queue(pQueue); return 0; }

以上就是我对队列基本知识的分享了，感谢大家的阅读~~~

 

文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。

 

Read more

DeepFace深度学习库+OpenCV实现——情绪分析器

DeepFace深度学习库+OpenCV实现——情绪分析器

目录 应用场景 实现组件 1. 硬件组件 2. 软件库与依赖 3. 功能模块 代码详解（实现思路） 导入必要的库 打开摄像头并初始化变量 主循环 FPS计算 情绪分析及结果展示 显示FPS和图像 退出条件 编辑 完整代码 效果展示 自然的 开心的 伤心的 恐惧的 惊讶的  效果展示 自然的 开心的 伤心的 恐惧的 惊讶的   应用场景         应用场景比较广泛，尤其是在需要了解和分析人类情感反应的场合。： 1. 心理健康评估：在心理健康领域，可以通过长期监控和分析一个人的情绪变化来辅助医生进行诊断或治疗效果评估。 2. 用户体验研究：在产品设计、广告制作或网站开发过程中，通过观察用户在使用过程中的情绪反应，来优化产品的用户体验。 3. 互动娱乐：在游戏或虚拟现实应用中，根据玩家的情绪状态动态调整游戏难度或故事情节，以增加沉浸感和互动性。

By Ne0inhk
最全java面试题及答案（208道）

最全java面试题及答案（208道）

本文分为十九个模块，分别是：「Java 基础、容器、多线程、反射、对象拷贝、Java Web 、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、MyBatis、RabbitMQ、Kafka、Zookeeper、MySQL、Redis、JVM」 ，如下图所示： 共包含 208 道面试题，本文的宗旨是为读者朋友们整理一份详实而又权威的面试清单，下面一起进入主题吧。 Java 基础 1. JDK 和 JRE 有什么区别？ * JDK：Java Development Kit 的简称，Java 开发工具包，提供了 Java

By Ne0inhk
10分钟打造专属AI助手！ToDesk云电脑/顺网云/海马云操作DeepSeek哪家强？

10分钟打造专属AI助手！ToDesk云电脑/顺网云/海马云操作DeepSeek哪家强？

文章目录 * 一、引言 * 云计算平台概览 * ToDesk云电脑：随时随地用上高性能电脑 * 二 .云电脑初体验 * DeekSeek介绍 * 版本参数与特点 * 任务类型表现 * 1、ToDesk云电脑 * 2、顺网云电脑 * 3、海马云电脑 * 三、DeekSeek本地化实操和AIGC应用 * 1. ToDesk云电脑 * 2. 海马云电脑 * 3、顺网云电脑 * 四、结语 * 总结：云电脑如何选择？ 一、引言 DeepSeek这些大模型让 AI 开发变得越来越有趣，但真要跑起来，可没那么简单！ * 本地配置太麻烦：显卡不够、驱动难装、环境冲突，光是折腾这些就让人心态崩了。 * 云端性能参差不齐：选错云电脑，可能卡到爆、加载慢，还容易掉线，搞得效率直线下降。 * 成本难控：有的平台按小时计费，价格一会儿一个样，

By Ne0inhk
用 DeepSeek 打造你的超强代码助手

用 DeepSeek 打造你的超强代码助手

DeepSeek Engineer 是啥？ 简单来说，DeepSeek Engineer 是一个基于命令行的智能助手。它能帮你完成这些事： * 快速读文件内容：比如你有个配置文件，直接用命令把它加载进助手，后续所有操作都可以基于这个文件。 * 自动改文件：它不仅能提建议，还可以直接生成差异表（diff），甚至自动应用修改。 * 智能代码生成：比如你让它生成代码片段，它会按照指定格式和规则直接返回。 更重要的是，这一切都是通过 DeepSeek 的强大 API 来实现的。想象一下，你有个贴身助手，不仅能听懂你的代码需求，还能直接动手帮你写！ 核心功能拆解 我们先来看 DeepSeek Engineer 的几个核心能力，让你更好地理解它的强大之处。 1. 自动配置 DeepSeek 客户端 启动这个工具时，你只需要准备一个 .env 文件，里面写上你的 API Key，比如： DEEPSEEK_API_

By Ne0inhk