无锡网站设计无锡网站建设,高端网站建设价格,网站建设创业公司策划方案,自己的网站发文章怎么做外链#x1f984;个人主页:修修修也 #x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录
#x1f4cc;栈的定义
#x1f4cc;元素进栈出栈的顺序
#x1f4cc;栈的抽象数据类型
#x1f4cc;栈的顺序存储结构
#x1f4cc;栈的链式存储结构
链栈的进… 个人主页:修修修也 所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录
栈的定义
元素进栈出栈的顺序
栈的抽象数据类型
栈的顺序存储结构
栈的链式存储结构
链栈的进栈操作
链栈的出栈操作
栈的应用
递归
括号匹配问题
四则运算表达式求值
结语 人生,需要有进栈出栈精神的体现.在哪里跌倒,就应该在哪里爬起来.无论陷入何等困境,只要抬头能仰望蓝天,就有希望,不断进取,你就可以让出头之日重现.困难不会永远存在,强者才能勇往直前. ——封清扬 栈的定义 栈和队列是两种重要的线性结构.从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为限定性的数据结构.但从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型. 栈(stack)是限定仅在表尾进行插入和删除操作的线性表. 我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈.栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构. 要理解栈这个概念,我们需要注意,首先栈是一个线性表,也就是说,栈具有线性关系,即前驱后继关系.只不过它是一种特殊的线性表而已.定义中说栈在线性表的尾部进行插入和删除操作,这里的表尾指的是栈顶,而不是栈底. 栈的插入操作,叫做进栈,也称压栈,入栈.类似于子弹入弹夹,如下图: 栈的删除操作,叫作出栈,也有的叫作弹栈.如同弹夹中的子弹出弹夹,如下图: 生活中类似于栈先进后出概念的东西很多,如我们平常用的抽纸,装羽毛球的球筒,装子弹的弹夹等. 元素进栈出栈的顺序 虽然栈的定义中规定了栈中元素必须符合先进后出的规则,但并没有对元素进出栈的时间做限制,因此最先进栈的元素,不一定就最后出栈,例如: 现在有三个整型元素1,2,3依次进栈,会有以下5种不同的出栈顺序: 第一种:1进,2进,3进.3出,2出,1出. 出栈顺序:321. 第二种:1进,1出,2进,2出,3进,3出. 出栈顺序:123 第三种:1进,2进,2出,1出,3进,3出. 出栈顺序:213 第四种:1进,1出,2进,3进,3出,2出. 出栈顺序:132 第五种:1进,2进,2出,3进,3出,1出, 出栈顺序:231 你可能会好奇,按照排列组合应该还有一个312的出栈顺序啊,为什么没写呢?别急,这是我们要重点分析的一种情况,我们把它拉出来单独分析: 首先,要出3的话,那么3肯定进栈了.按照1,2,3的进栈顺序,3进栈了,那么1,2肯定已经进栈了,所以3出栈时栈内的情况应该是这样的: 3出栈后,栈内元素情况是这样的: 可以看到,当前栈中栈顶元素为2,但我们想要出栈的元素是1,这是不可能做到的,因为按照栈的先进后出原则,我们此时只能先出2,再出1. 因此312的出栈顺序是不可能的. 根据上述对312出栈顺序的分析,我们可以得出一个结论: 即当按照由1~x的元素顺序入栈时,假设当前栈顶元素为x,则该栈不可能实现按照x,x-2,x-1的顺序出栈.如下图: 栈的抽象数据类型 对于栈来讲,因为它的特殊性,因此在操作上相对于线性表有些变化,特别是插入和删除操作,只需要保留进栈和出栈两部分. 栈的抽象数据类型如下:
ADT 栈(stack)
Data栈的数据对象集合为 {a1, a2, ..., an},每个元素的类型均为STDataType.其中, 除第一个元素a1外, 每一个元素有且只有一个直接前驱元素.除了最后一个元素an外, 每一个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的关系.
OperationInitStack(*s); 初始化操作, 建立一个空的栈s.DestroyStack(*s) 若栈存在,则销毁它.StackEmpty(s); 若栈为空,返回true,否则返回false.ClearStack(*s); 将栈清空.GetTop(s, *e); 若栈存在且非空,用e返回s的栈顶元素.Push(*s,e); 若栈s存在,插入新元素e到栈s中并成为栈顶元素.Pop(*s,*e); 删除栈s中栈顶元素,并用e返回其值.StackLength(s); 返回栈s的元素个数.
endADT 栈的顺序存储结构 顺序栈和顺序表一样,都是使用数组来实现的,对于栈这种只能一头插入和删除的线性表来说,使用下标为0的一端做为栈底比较好.因为顺序表尾插和尾删的时间复杂度都是O(1),而头插和头删因为要挪动元素,所以时间复杂度为O(n).对比来看,显然是用下标为0的一端做头,然后在数组尾部进栈出栈是较优的选择. 在顺序栈中需要包含三个要素:存储数据的数组arr,顺序栈的当前存储容量capacity,顺序栈栈顶元素的位置top. 随着数据的进栈和出栈,top的位置是在变化的,但无论如何top也不能够比数组容量capacity还要大.因此top必须小于capacity.当栈中存在一个元素时,top0,因此同常把空栈的判定条件设为top-1. 若现在有一个顺序栈,capacity是5,则栈普通情况,空栈和满栈的情况示意图如下: 在顺序栈中,进栈和出栈的逻辑完全和顺序表的尾插尾删逻辑一样,后续我们会一起实现一个顺序栈的程序,因此在这里就不多赘述了. 栈的链式存储结构 栈的链式存储结构,简称为链栈. 因为栈只在栈顶插入或删除的特性,我们在设计链栈时应当把栈顶放在单链表的头部,并且对链表来说,头指针是必须的,而对链栈来说,栈顶指针同样是必须的,因此我们不如将他们合二为一. 链栈示意图: 对于链栈来说,基本不存在栈满的情况.而对空栈来说,链栈的判断条件应该是topNULL. 链栈的进栈操作 对于链栈的进栈push操作,假设元素新结点是e,top为栈顶指针,则进栈示意图如下: 链栈的出栈操作 对于链栈的出栈pop操作,假设top为栈顶指针,则出栈示意图如下: 栈的应用(待补)
递归
括号匹配问题
四则运算表达式求值 结语
当我们了解了栈的定义后,接下来我们将一起实现一个顺序栈程序,由于篇幅有限,我会在下篇博客中为大家详细介绍一下顺序栈的实现,感兴趣的话可以点击下面链接查看:
【数据结构】用C语言实现顺序栈(附完整运行代码)http://t.csdnimg.cn/ksbBH
希望这篇有关数据结构栈的介绍文章能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步! 相关文章推荐 【数据结构】什么是线性表? 【数据结构】线性表的链式存储结构 【数据结构】C语言实现顺序表万字详解(附完整运行代码) 【数据结构】C语言实现单链表万字详解(附完整运行代码) 【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码) 数据结构栈和队列篇思维导图
