【数据结构-初阶】详解线性表(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

【数据结构与算法】（LeetCode）141.环形链表 142.环形链表Ⅱ

【数据结构与算法】（LeetCode）141.环形链表 142.环形链表Ⅱ

文章目录 * 引言 * 环形链表判断 * 问题描述 * 解决方案：快慢指针法 * 原理分析 * 为什么快慢指针一定能相遇？ * 步长选择的数学分析 * 环形链表Ⅱ * 方法一 * 方法二：转换为相交链表问题 * 算法思路 * 实际应用与扩展 * 应用场景 引言 环形链表问题是数据结构与算法中的经典问题，在面试中出现频率极高。这类问题不仅考察对链表结构的理解，更考验解决问题的思维能力和数学分析能力。本文将详细分析环形链表的判断方法以及环入口节点的定位算法，帮助读者深入理解这一重要问题。 环形链表判断 问题描述 给定一个链表的头节点 head，判断链表中是否存在环。 解决方案：快慢指针法 快慢指针法是解决环形链表问题的经典方法，其核心思想是使用两个指针以不同速度遍历链表。 bool hasCycle(structListNode*head){structListNode* slow=head,*fast=head;while(fast&&fast->next){ slow=slow-&

By Ne0inhk
数据结构：队列

数据结构：队列

前言  本篇文章将讲解队列的概念和结构，队列的实现等知识的相关内容，本章代码实现的知识，与单向链表相关，所以如果还没看过单向链表文章，可以看看： https://blog.ZEEKLOG.net/2401_86982201/article/details/154615762?fromshare=blogdetail&sharetype=blogdetail&sharerId=154615762&sharerefer=PC&sharesource=2401_86982201&sharefrom=from_link 一、队列概念与结构 概念 与栈的数据结构类似，队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In

By Ne0inhk
Flutter 三方库 async_extension 的鸿蒙化适配指南 - 实现具备高级异步编排算法与流操作扩展的并发工具集、支持端侧复杂业务流的函数式处理实战

Flutter 三方库 async_extension 的鸿蒙化适配指南 - 实现具备高级异步编排算法与流操作扩展的并发工具集、支持端侧复杂业务流的函数式处理实战

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 async_extension 的鸿蒙化适配指南 - 实现具备高级异步编排算法与流操作扩展的并发工具集、支持端侧复杂业务流的函数式处理实战 前言 在进行 Flutter for OpenHarmony 的大规模异步业务系统（如实时行情刷新、多源数据聚合）开发时，如何更优雅地处理 Future 的超时竞争、Stream 的防抖（Debounce）或复杂的并发队列控制？虽然 Dart async 包提供了基础功能，但 async_extension 进一步扩展了异步编程的边界，提供了更符合函数式范式的工具。本文将探讨如何在鸿蒙端构建极致、高效的异步处理链路。 一、原直观解析 / 概念介绍 1.1 基础原理 该库通过对 Dart 核心异步类的非侵入式扩展（Extensions）

By Ne0inhk
链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

✨链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧🎯 * 视频地址 * 🚀 开篇引论：链表反转的进阶之路 * 🔄 基础筑基：链表【前n个节点】递归反转 * 1. 函数定义与核心功能 * 2. 递归实现思路拆解 * 3. 直观调用示例 * 4. 关键代码实现（C++）与详解 * 🎯 实战攻坚：LeetCode 92 链表区间反转 * 1. 题目问题描述 * 2. 神器加持：虚拟头节点（哨兵）技巧 * 3. 整体解题思路 * 4. 完整代码实现（C++）与逐行解析 * 5. 算法复杂度分析 * 📚 算法原理深度剖析 * 1. 递归反转的核心原理 * 2. 虚拟头节点的底层逻辑 * 💡 算法学习核心建议 * 结语 * ✅ 关键点回顾 视频地址

By Ne0inhk