数据结构---队列的实现

news/2024/11/29 11:56:49/

文章目录

  • 前言
  • 一、什么是队列?
  • 二、队列接口的实现
    • 1.队列结构的定义
    • 2.接口实现
  • 总结

前言

队列是一种特殊的线性表。

特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。

进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列中没有元素时,称为空队列。

队列的数据元素又称为队列元素。

在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。

因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表


一、什么是队列?

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。

队列具有先进先出FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

 

二、队列接口的实现

1.队列结构的定义

//队列--先进先出--用链表实现
typedef int QDataType;//队列的单节点定义
typedef struct QNode
{QDataType val;struct QNode* next;
}QNode;//队列整体定义,有头,尾,以及元素个数
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

原因:队列使用链表实现,使其每个节点的定义为链表节点形式,而因为队列是一个线性结构,需要有头尾节点进行访问,而且还需要返回其元素个数,便于某些特定场合下的访问,需要将其封装到结构体中,便于访问,因而定义两个结构体形式。

2.接口实现

1. 初始化

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

为什么加断言?

可以明确的知道,pq指针不为空,则需要进行断言,避免他人传错参数。

2. 销毁

//销毁
void QDestroy(Queue* pq)
{//空队列没必要销毁assert(pq);assert(pq->head != NULL);//依次进行释放QNode* cur = pq->head;while (cur){QNode* after = cur->next;free(cur);cur = after;}pq->head = pq->tail = NULL;pq->size = 0;
}

因为是从堆上动态开辟出来的节点,需要依次释放,避免一次性释放,无法找到剩下的节点,导致出现内存泄漏。

3. 插入(入队)

//插入--入队列
void QPush(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->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

入队过程:1.进行新节点的开辟,需要对malloc的结果进行检查,有备无患

2.有了新节点,需要进行链接过程,链接过程中,需要进行对于队列头尾指针的检查,避免出现非法访问的情况,因为在初始化过程,对于head和tail是赋为空指针的

3.检查完是否为空指针后,即开始链接,也就是进行普通的尾插过程。

4. 删除(出队列)

//删除--出队列
void QPop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//因为队列的性质,先进先出,则其删除是头删QNode* after = pq->head->next;free(pq->head);pq->head = after;pq->size--;
}

出队列过程:普通的头删即可,但是,需要注意的是空队列无需删除,需要对head进行判断,否则会出现非法访问情况

5. 获取元素个数

//返回队列元素个数
int QSize(Queue* pq)
{assert(pq);return pq->size;
}

很普通的操作,但是在某些特定的环境下,可以发挥出神奇的效果,可以使得获取元素效率很快

6. 获取队头和队尾元素及判空

//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//取队头元素
QDataType QFront(Queue* pq)
{assert(pq);//空队列不用取元素assert(!QEmpty(pq));return pq->head->val;}//取队尾元素
QDataType QRear(Queue* pq)
{assert(pq);//空队列不用取元素assert(!QEmpty(pq));return pq->tail->val;
}

判空和获取队头队尾元素配合使用,因为空的队列无法获取元素


总结

队列,数据结构中的特殊结构,具有先进先出的特性,使得在某些场合会被频繁利用,所以对于身为学习者的我们,需要掌握其实现逻辑和实现方法。


http://www.ppmy.cn/news/55661.html

相关文章

中国移动发布COCA软硬一体片上计算架构,引领云计算市场下一个黄金十年

当前,数字经济发展已经成为改变全球竞争格局的关键力量,随着算力成为数字经济新引擎,算力规模持续增长,算力结构发生改变。主动拥抱智算浪潮,持续输出优质算力支撑数字中国建设,适配泛在化、异构化算力推动…

跨域的五种最常见解决方案

在开发Web应用程序时,一个常见的问题是如何处理跨域请求。跨域请求是指来自不同源的请求,这些请求可能会受到浏览器的限制而不能被正常处理。在这篇文章中,我们将探讨跨域请求的常见解决方案,并了解每种解决方案的优缺点。 一、J…

Docker在Windows系统中的安装方法和使用方法

Docker在Windows系统中的安装方法和使用方法 Docker是一种容器化技术,可以让开发者将应用程序和其依赖项打包成一个可移植的容器,从而实现快速部署和运行。在Windows系统中,Docker可以通过以下步骤进行安装和使用。 优点: Dock…

掌握知识变现的四个步骤,你的知识就是印钞机

去年底,我开了一场直播来分享知识变现的方法,讲了一系列纯干货。 其实知识变现没有想象那么难,关键是方法,和其他事情一样,只要掌握了方法,普通小白也能按照我讲的方法,去做知识变现。 听课照做…

VsCode镜像下载(国内镜像源,高速秒下)

VsCode镜像下载(国内镜像源,高速秒下) vscode官方网站下载速度太慢,非正规网站又不太敢下,通过镜像源下载就好了。 你们不介意版本的话,下面是1.63版本的链接(直接复制下载就好了)&…

三星弃Google用Bing?谷歌赶工新AI搜索Magi

“三星考虑将手机端的默认搜索引擎由Google换成Bing”,《纽约时报》上的这则消息披露次日,微软股价上涨2%,谷歌母公司Alphabet股价下跌3%。 过去20年里,谷歌一直是在线搜索领域无人能敌的霸主,微软旗下的Bing只在3%-5…

嵌入式开发--无刷电机学习1--FOC简介

写在前面 最近刚学FOC电机控制,文中错误在所难免,欢迎批评指正,也欢迎在评论区留言讨论。 FOC意义 普通直流电机(DC MOTOR)的驱动是碳刷换向,能看到这篇文章的朋友应该不用我再去复述一遍直流电机的工作…

Java 基础进阶篇(五)—— 接口详解

文章目录 一、接口概述二、接口的基本使用三、接口从 JDK 8 开始新增的方法四、接口的注意事项(了解)补充:接口与接口的关系 一、接口概述 规范的基本特征是约束和公开。 接口就是一种规范,其约束别人必须干什么事情。 所以&…