【数据结构】队列的实现及循环队列的实现详解(c语言)_1.建立一个循环队列,输出队头与队尾元素、元素个数; 2.入队,输出队头与队尾元素、-程序员宅基地

技术标签: c语言  数据结构  数据结构(C语言)  

目录

一.队列的基本概念及结构

二.队列的实现

1.队列实现的相关函数接口

2.定义结构体

3.初始化队列

 4.入队

 5.判断队列是否为空

 6.出队

 7.获取队头元素

 8.获取队尾元素

 9.获取队列的元素个数

 10.销毁队列

 三.循环队列的实现

1.循环队列的概念

2.循环队列的实现方式

3.定义一个结构体

 4.初始化

5.判断队列是否满了

 6.入队

 7.判断队列是否为空

 8.出队

 9.获取队头元素

 10.获取队尾元素

 11.销毁队列

 12.链表实现循环队列代码


一.队列的基本概念及结构

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

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

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

队列也可以使用数组和链表的结构实现,使用链表的结构实现更优一些

因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低

就像顺序表一样,头删一个数据时需要把后面的数据都往前移,此时的时间复杂度为O(n)

 如上图为队列的数组结构,链式结构的示意图

今天主要是要分享链式存储结构的相关操作

用链表实现队列有两种方法,1.头插尾删2.尾插头删

再通过比对以后呢我觉得第二种方法更好一些。原因下文会分析

二.队列的实现

1.队列实现的相关函数接口

2.定义结构体

通过下图可以看到定义了两个结构体,第一个结构就是我们常用的节点,而第二结构体中的成员可以理解为head指针是用来指向队头的tail指针是用来指向队尾的size用来反应队列中的元素个数,看到这肯定会有一些疑问,为什么要这样定义呢,这样定义的好处是什么

1.这样定义的好处

上文我们说了实现队列要用尾插头删来实现

当入队的时候尾插需要找到队列的尾,这样就需要把队列遍历一遍,此时入队列的时间复杂度为O(n)  

而我们使用tail指针指向尾,在尾插的时候就可以不用再遍历队列了,这时入队列的时间复杂度为O(1)

2.(1.头插尾删2.尾插头删)为什么第二种方法好

第一种方法 当出队列的时候需要尾删,此时还是需要遍历一遍队列找到尾节点前面的一个节点

此方法的时间复杂度为O(n)

第二种方法  因为有tail指针,此时尾插头删时间复杂度都为O(1)

因此尾插头删这种方法更好

3.初始化队列


 4.入队

 5.判断队列是否为空

 6.出队

重要的事说三遍!当删除最后一个数时tail要置空!

当删除最后一个数时tail要置空!

当删除最后一个数时tail要置空!防止野指针!!!

 7.获取队头元素

断言一下,如果队列为空就不能访问,防止非法访问

 8.获取队尾元素

断言一下,如果队列为空就不能访问,防止非法访问

 9.获取队列的元素个数

 10.销毁队列

 三.循环队列的实现

1.循环队列的概念

循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。

在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要将存储空间的第一个位置空闲,便可将元素加入到第一个位置(此时第一个位置为队尾)循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。

循环队列满足了日常中存储空间的重复使用

2.循环队列的实现方式

循环队列的实现方式有两种1.用数组实现2.用链表实现

下面我将阐述数组实现的方法

在实现循环队列时我们需要先定义Front变量表示队头 ,Rear -1变量表示队尾元素下表,

当我们定义k个容量的队列在判断空或满的情况时

队列为空时Front和Rear相等,队列满了的时候Front与Rear又相等,这样是不是就有点自相矛盾了呢,显然这样是不容易判断队列的空或满的

这是我们就需要采取另一种方法了,需要k个容量的队列时,可以申请k+1个容量的空间

这时当队列为空时Front==Rear,当队列满时Rear+1==Front(下文解释原因),这种情况就很容易判断了

下面这种情况也表示队列为空,只要Front等于Rear就表示队列为空,不局限于Front==Rear==0 

 当向队列插入一个数的时候,Rear就加1一次,删除一个数据的时候Front就加1一次,如下图

 入队的时候我们肯定是需要判断队列是否已满,如果已满就不能再插入了,此时肯定想到了Rear+1==Front时就满了(如下图)

 

,但是有种特殊情况(如下图),又该怎么判断呢

 向上图这种情况就需要Rear+1对k+1取模了,就如此时Rear==4,Front==0,

(Rear+1)%(k+1)==0,可以看到此时它们相等,这样就完成了队列的循环(下图示意图),取模可以让Rear重新回到0位置处

同理当只剩最后一个元素的时候,要把它删掉Front就需要加1,当Front加一就非法访问了,所以需要用上文中的方法 取模,(Front+1)%(k+1)这样它就能回到零位置处

示意图:

 现在就让我们用代码来实现它吧

3.定义一个结构体

其中的k表示队列的容量,它的用处后面的代码实现就可以知道了

 4.初始化

5.判断队列是否满了

 6.入队

入队失败就返回false,成功就返回true

 7.判断队列是否为空

 8.出队

出队失败就返回false,成功就返回true

 9.获取队头元素

 10.获取队尾元素

 11.销毁队列

销毁时它们的顺序不能反!!1

 12.链表实现循环队列代码

不过多描述了

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_72532428/article/details/129751649

智能推荐

ajax跨域与cookie跨域_一级域名 的cookie ajax 请求二级域名时获取cookie-程序员宅基地

文章浏览阅读389次。ajax跨域ajax跨域取数据(利用可以跨域加载js的原理 functioncallback(){ }这是需要返回这样一个js函数)ajax数据类型使用jsonp :如 ajax{ url:..._一级域名 的cookie ajax 请求二级域名时获取cookie

Flutter从0到1实现高性能、多功能的富文本编辑器(基础实战篇)_flutter 富文本-程序员宅基地

文章浏览阅读1.3k次,点赞2次,收藏2次。在上一章中,我们分析了一个富文本编辑器需要有哪些模块组成。在本文中,让我们从零开始,去实现自定义的富文本编辑器。注:本文篇幅较长,从失败的方案开始分析再到成功实现自定义富文本编辑器,真正的从0到1。— 完整代码太多, 文章只分析核心代码,需要源码请到代码仓库作为基础的富文本编辑器实现,我们需要专注于简单且重要的部分,所以目前只需定义标题、文本对齐、文本粗体、文本斜体、下划线、文本删除线、文本缩进符等富文本基础功能。//定义默认颜色​...///用户自定义颜色解析。_flutter 富文本

新一代异步IO框架——io_uring 架构-程序员宅基地

文章浏览阅读30次。近年来,Linux社区开发了一种新的异步IO框架,称为io_uring。io_uring通过提供高度可扩展和高性能的异步IO接口,有效地解决了传统异步IO框架中的一些性能瓶颈和限制。io_uring已经成为许多高性能应用程序的首选异步IO框架,为开发者提供了更好的IO处理能力。io_uring 架构是建立在Linux内核之上的,它使用了一组新的系统调用和内核机制,以提供高性能和低延迟的异步IO操作。io_uring的设计目标是提供一种简单而强大的接口,使得开发者可以轻松地利用异步IO的优势。

耗时一个月!期末熬夜复习整理 | 计算机网络(谢希仁第七版)大合集【知识点+大量习题讲解】_计算机网络期末复习题-程序员宅基地

文章浏览阅读2.5w次,点赞204次,收藏1.8k次。期末计网满绩计划教材:计算机网络(第七版)谢希仁版目录1. 概述2. 物理层3. 数据链路层(次重点)4. 网络层(重点)5. 运输层(重点)6. 应用层7. 网络安全最后1. 概述第一章概述2. 物理层第二章物理层3. 数据链路层(次重点)第三章数据链路层4. 网络层(重点)第四章网络层5. 运输层(重点)第五章运输层6. 应用层第六章应用层7. 网络安全稍后发布最后小生凡一,期待你的关注。..._计算机网络期末复习题

DNS解析中的A记录、AAAA记录、CNAME记录、MX记录、NS记录、TXT记录、SRV记录、URL转发等-程序员宅基地

文章浏览阅读6k次,点赞2次,收藏18次。AA记录: 将域名指向一个IPv4地址(例如:100.100.100.100),需要增加A记录NSNS记录: 域名解析服务器记录,如果要将子域名指定某个域名服务器来解析,需要设置NS记录SOASOA记录: SOA叫做起始授权机构记录,NS用于标识多台域名解析服务器,SOA记录用于在众多NS记录中标记哪一台是主服务器MXMX记录: 建立电子邮箱服务,将指向邮件服务器地址,需要设置MX记录。建立邮箱时,一般会根据邮箱服务商提供的MX记录填写此记录TXTTXT记录: 可任意填写,可为空。一_a记录

SpringBoot项目引入外部jar包_springboot引入外部jar包-程序员宅基地

文章浏览阅读695次。SpringBoot项目引入外部jar包_springboot引入外部jar包

随便推点

Hadoop 序列化机制_hadoop final-程序员宅基地

文章浏览阅读493次。序列化是指将结构化对象转化为字节流以便在网络上传输或者写到磁盘上进行永久存储的过程,反序列化是指将字节流转回结构化对象的逆过程序列化用于分布式处理的两大领域,进程间通信和永久存储。在Hadoop中,系统中多个节点上进程间的通信是通过“远程过程调用”(remote procedure call, RPC)实现的。RPC将消息序列化成二进制流后发送到远程节点,远程节点接着将二进制流饭序列化为原始..._hadoop final

tinymce富文本编辑器实现本地图片上传_tinymce images_upload_handler-程序员宅基地

文章浏览阅读5.7k次,点赞3次,收藏6次。在开发过程中使用tinymce富文本编辑器,发现他的图片上传默认是上传网络图片那么如何实现上传本地图片呢,上官网逛一圈,发现其实很简单在官网中找到下面这张图片,并且有相关的例子这里,我使用了自定义函数images_upload_handler (blobInfo, success, failure) { const url = 'uploadImg' ..._tinymce images_upload_handler

SpringCloud-拜托!面试请不要再问我Spring Cloud底层原理实战_spring cloud +sql springcloud底层组件-程序员宅基地

文章浏览阅读2.6k次,点赞5次,收藏14次。上一篇我们说到《拜托!面试请不要再问我Spring Cloud底层原理》,我们大概了解了Spring Cloud中各个组件的作用以及其背后实现的原理。但是俗话说得好,实践是检验真理的唯一标准。这一篇我们动手实践一下,即搭建一个包含订单服务、库存服务、仓库服务、积分服务的微服务架构项目。一、项目的工程结构工程名 服务名 端口号 shop-parent 父工程 ..._spring cloud +sql springcloud底层组件

安装及配置py-faster-rcnn(亲测且详细)-程序员宅基地

文章浏览阅读819次。Ubuntu16.04下编译py-faster-rcnn全过程,在本机上试验成功,亲测有效,清晰总结踩过的坑,常见问题及解决方案一并给出_py-fast

Hausaufgabe--Python 08-程序员宅基地

文章浏览阅读89次。0-- print A/B/C/D rather than detail score:score = float(input('please input your score: '))if score>=90: print('A')elif 80<=score<90: print('B')elif 60<=score<80: print('C'...

linux下mkdir头文件_Linux下的创建目录函数——mkdir()-程序员宅基地

文章浏览阅读2.2k次。原型:int mkdir (const char *filename, mode_t mode)返回0表示成功,返回-1表述出错。使用该函数需要包含头文件sys/stat.hmode 表示新目录的权限,可以取以下值:S_IRUSRS_IREADRead permission bit for the owner of the file. On many systems this bit is 040..._linux mkdir 头文件