初阶数据结构之队列的实现

embedded/2024/11/27 14:10:57/

1 队列的定义

什么是队列呢？队列只允许在一端进行插入数据操作，在另一端进行删除数据操作。队列具有先进先出FIFO(First In First Out)的特性。

队头：删除数据的一端称为队头。

队尾：插入数据的一端称为队尾。

2 队列底层结构的选择

在这里插入图片描述

底层采用数组来实现，在删除队头元素的时候，需要移动数组元素，时间复杂度为O(N)，还会存在空间浪费。

在这里插入图片描述

采用链表实现队列，删除队头元素时，只需要让head指向下一个节点同时将头结点的空间还给操作系统。在队尾增加元素时，申请一块空间存放数据，让新节点成为链表尾节点，为了避免在增加元素时需要找链表尾节点，所以创建一个tail指针，指向链表尾节点。

因此采用链表来实现队列再合适不过了。

3 队列的实现

3.1 队列的定义

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;

3.2 队列的接口

//初始化队列
void QueueInit(Queue* pq);//队尾插入数据
void QueuePush(Queue* pq, QDataType x);//队头出数据
QDataType QueueFront(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//删除队头数据
void QueuePop(Queue* pq);//队列的大小
int QueueSize(Queue* pq);//队尾出数据
QDataType QueueBack(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

3.2.1 初始化队列

//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}

刚开始队列为空，head和tail指向NULL。保证pq不能为NULL，否则
通过pq去访问head和tail会造成野指针。

3.2.2 队尾插入数据

//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){printf("QueuePush():malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}

在这里插入图片描述

如果head为NULL，说明队列为空，则让head和tail同时指向头结点。
否则，则让tail->next保存新节点的地址同时让tail指向新节点，使新节
点成为链表的尾节点。

3.2.3 队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}else{return false;}
}

head指向NULL，说明队列为空，否则，队列不为空。

3.2.4 队头出数据

//队头出数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

队列不为空才能出数据，返回队列头结点的数据（因为head指向头结点）。

3.2.5 删除队头数据

//删除队头数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//记录下一个节点的地址QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}

删除数据首先要保证队列不能为空，其次使head指向头结点的下一个
节点，再释放头结点。如果head指向了NULL，说明队列为空，此时
应该将tail置为NULL。避免野指针的出现。

3.2.6 队列的大小

//队列的大小
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;int size = 0;while (NULL != cur){size++;cur = cur->next;}return size;
}

对链表进行遍历，计算链表节点的个数。

3.2.7 队尾出数据

//队尾出数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

保证队列不为空的前提下，返回tail指向的节点的数据。

3.2.8 销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->head!=NULL){QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->tail = NULL;
}

对链表进行遍历，先记录要删除节点的下一个节点的地址，然后释放
删除节点的空间，让head指向下一个节点。最后，将tail置为NULL
（避免野指针）。

4 队列完整代码的实现

Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;//初始化队列
void QueueInit(Queue* pq);//队尾插入数据
void QueuePush(Queue* pq, QDataType x);//队头出数据
QDataType QueueFront(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//删除队头数据
void QueuePop(Queue* pq);//队列的大小
int QueueSize(Queue* pq);//队尾出数据
QDataType QueueBack(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){printf("QueuePush():malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}//队头出数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}else{return false;}
}//删除队头数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//记录下一个节点的地址QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}//队列的大小
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;int size = 0;while (NULL != cur){size++;cur = cur->next;}return size;
}//队尾出数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->head!=NULL){QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->tail = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS#include"Queue.h"
void TestQueue1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);QDataType ret = QueueFront(&q);printf("%d ", ret);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);
}void TestQueue2()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);int size = QueueSize(&q);printf("%d ", size);QDataType ret = QueueBack(&q);printf("%d ", ret);QueueDestroy(&q);
}
int main()
{//TestQueue1();TestQueue2();return 0;
}

http://www.ppmy.cn/embedded/140914.html

相关文章

【Linux系统编程】第五十弹---构建高效单例模式线程池、详解线程安全与可重入性、解析死锁与避免策略，以及STL与智能指针的线程安全性探究

【Linux系统编程】第五十弹---构建高效单例模式线程池、详解线程安全与可重入性、解析死锁与避免策略，以及STL与智能指针的线程安全性探究

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、将日志加到线程池 1.1、Thread类 1.2、ThreadPool类 1.2.1、HandlerTask() 1.2.2、其他公有成员函数 1.3、主函数 2、…
阅读更多...
Android BottomNavigationView 底部导航栏使用详解

Android BottomNavigationView 底部导航栏使用详解

一、BottomNavigationView简介 BottomNavigationView是官方提供可以实现底部导航的组件&#xff0c;最多支持5个item&#xff0c;主要用于功能模块间的切换&#xff0c;默认会包含动画效果。 官方介绍地址&#xff1a;BottomNavigationView 二、使用BottomNavigationView a…
阅读更多...
SpringBoot（四十）SpringBoot集成RabbitMQ使用过期时间+死信队列实现延迟队列

SpringBoot（四十）SpringBoot集成RabbitMQ使用过期时间+死信队列实现延迟队列

前边我们使用RabbitMQ实现了高并发下对流量的削峰填谷。正常在实际应用中大概也就够用了。 有的时候呢&#xff0c;我们需要使用到延迟队列&#xff0c;RabbitMQ不像RocketMQ一样默认就支持延迟队列&#xff0c;RabbitMQ是不支持延迟队列的&#xff0c;但是呢&#xff1f;我们可…
阅读更多...
OCR-free Document Understanding Transformer

OCR-free Document Understanding Transformer

摘要：理解文档图像（如发票）是一个核心且具有挑战性的任务，因为它需要执行复杂的功能，如读取文本和对文档的整体理解。目前的视觉文档理解（VDU）方法将读取文本的任务外包给现成的光学字符识别（OCR）引擎，并专注于使用OCR输出进行理解任务。尽管基于OCR的方法显示出令人…
阅读更多...
c++编程玩转物联网：使用芯片控制8个LED实现流水灯技术分享

c++编程玩转物联网：使用芯片控制8个LED实现流水灯技术分享

在嵌入式系统中&#xff0c;有限的GPIO引脚往往限制了硬件扩展能力。74HC595N芯片是一种常用的移位寄存器&#xff0c;通过串行输入和并行输出扩展GPIO数量。本项目利用树莓派Pico开发板与74HC595N芯片&#xff0c;驱动8个LED实现流水灯效果。本文详细解析项目硬件连接、代码实…
阅读更多...
极狐GitLab 17.6 正式发布几十项与 DevSecOps 相关的功能【二】

极狐GitLab 17.6 正式发布几十项与 DevSecOps 相关的功能【二】

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 学习极狐GitLab 的相关资料&#xff1a; 极狐GitLab 官网极狐…
阅读更多...
零基础3分钟快速掌握 ——Linux【终端操作】及【常用指令】Ubuntu

零基础3分钟快速掌握 ——Linux【终端操作】及【常用指令】Ubuntu

1.为啥使用Linux做嵌入式开发 能广泛支持硬件 内核比较高效稳定 原码开放、软件丰富 能够完善网络通信与文件管理机制 优秀的开发工具 2.什么是Ubuntu 是一个以桌面应用为主的Linux的操作系统&#xff0c; 内核是Linux操作系统&#xff0c; 具有Ubuntu特色的可视…
阅读更多...
接上一主题，C++14中如何设计类似于std::any，使集合在C++中与Python一样支持任意数据？

接上一主题，C++14中如何设计类似于std::any，使集合在C++中与Python一样支持任意数据？

这篇文章的重点是C多态的应用&#xff0c;但是如果你是C新手&#xff0c; 你需要了解以下C知识&#xff1a; 类 构造函数 拷贝构造函数 虚拟函数 纯虚拟函数 析构函数 类的继承 运算符重写 模板类 模板参数 数组 数组的传递 指针与动态内存分配 Python&#xff1a; s …
阅读更多...
最新文章

Copyright @ 2022~2023