当前位置: 首页> 健康> 美食 > 文化墙_建设官方企业网站_淘宝关键词排名查询工具_恶意点击推广神器

文化墙_建设官方企业网站_淘宝关键词排名查询工具_恶意点击推广神器

时间:2025/7/11 23:31:04来源:https://blog.csdn.net/2401_87465145/article/details/147491512 浏览次数:0次
文化墙_建设官方企业网站_淘宝关键词排名查询工具_恶意点击推广神器

一:引言:

上次我们学习了双向链表的实现,这次我们来学习两个新的数据结构,因为比较简单,就放在一块学习。

二:栈的实现

1. 栈的结构与性质

只凭文字来描述的话不够生动,下面我们就以图画的形式来直观感受一下

在这里插入图片描述

2. 思考:

既然我们已经知道了的结构和性质,那么就是来实现。我们用什么来实现呢?
先来考虑拿刚学的链表来实现
在这里插入图片描述

接着再来考虑用顺序表来实现
在这里插入图片描述
可以看到用顺序表链表实现的时间复杂度都为o(1),那么只好再从空间角度来比较,若用链表来实现的话,需要不停地申请新节点,并且链表的存储结构还不一定连续,容易造成空间的碎片化,而顺序表的话存储结构是一个接一个的连续着的,空间利用率会更好,并且顺序表采用动态数组,也能做到动态扩容,因此,结合以上几点分析,还是用顺序表来实现更好一点。

3. 定义栈

在这里插入图片描述
因为进栈出栈都是在栈顶进行,因此这里需要定义栈顶位置,除了动态数组,还需要知道的空间大小,因此再定义一个容器大小

4. 初始化

声明:

注意这里因为要改变结构体中的成员,因此传入的是结构体指针(结构体的地址)
在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述

5. 入栈

声明:

在这里插入图片描述

逻辑分析:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述
可以看到测试正常

6. 出栈

声明:

在这里插入图片描述

逻辑分析:

出栈其实就是顺序表的删除逻辑,只需让top--即可,这时top位置的元素就是无效元素了。
注:但进行出栈操作之前还要判断是否为空,也就是top是否为0。

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述
可以看到测试没问题

7. 取出栈顶元素

声明:

在这里插入图片描述

逻辑实现:

因为在每次入之后top会往后走一格,因此栈顶位置即为top - 1
在这里插入图片描述

8. 栈中有效元素个数

声明:

在这里插入图片描述

逻辑实现:

由于我们是从下标为0的位置开始使用,因此top的值即为中有效元素的个数
在这里插入图片描述

9.销毁

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述

三:队列的实现

1. 队列的结构和性质

队列:一种具有先进先出性质的连续存储的数据结构。
下面通过图画来辅助理解:
在这里插入图片描述

2.思考:

在知道了队列的性质和结构之后,就是来实现队列,下面我们还是从顺序表链表的角度来考虑。
先来看顺序表:
在这里插入图片描述
接下来再看链表:
在这里插入图片描述
通过上述分析可以看到无论是顺序表还是链表,时间复杂度都不能做到入队出队的时间复杂度同时为o(1)
因此就需要想办法来优化一下:我们可以发现:队列的出队入队,一个是针对队头,一个是针对队尾,队列的中间部分我们不关心,并且队列是由一个个节点组成的,因此可以分为两个结构,定义一个队列结构,定义一个节点结构,这样就可以实现队列出队入队时间复杂度都为o(1)

3. 定义队列

在这里插入图片描述

这里我们先定义了每个节点的结构,然后定义了队列结构,其中维护了指向队头和指向队尾的两个结构体指针

4. 初始化

声明:

这里还是老样子,由于需要修改结构体的成员,要改变实参,因此传入的是结构体指针(结构体的地址)
在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述
可以看到初始化正常、

5.入队

声明:

在这里插入图片描述

逻辑分析:

在这里插入图片描述

逻辑实现:

在这里插入图片描述
进队分为了两种情况:空队列非空队列

6. 判空

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

7.出队

声明:

在这里插入图片描述

逻辑分析:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

8. 取出队头元素

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述
这里我们让1 2 依次入队,之后我们又执行了一次出队,因此队头就成了2

9. 取出队尾元素

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述

10.队列中有效元素个数

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述

11.销毁

声明:

在这里插入图片描述

逻辑实现:

在这里插入图片描述

测试:

在这里插入图片描述

总结:

在这篇博客中,我们实现了具有先进后出性质的和具有先进先出性质的队列
下篇博客我们将练习几道关于队列oj题

关键字:文化墙_建设官方企业网站_淘宝关键词排名查询工具_恶意点击推广神器

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: