人生,需要有进栈出栈精神的体现.在哪里跌倒,就应该在哪里爬起来.无论陷入何等困境,只要抬头能仰望蓝天,就有希望,不断进取,你就可以让出头之日重现.困难不会永远存在,强者才能勇往直前. ——封清扬
📌栈的定义
栈和队列是两种重要的线性结构.从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为限定性的数据结构.但从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型.
栈(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外, 每一个元素有且只有一个直接后继元素. 数据元素之间的关系是一对一的关系. Operation InitStack(*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.当栈中存在一个元素时,top=0,因此同常把空栈的判定条件设为top=-1.
若现在有一个顺序栈,capacity是5,则栈普通情况,空栈和满栈的情况示意图如下:
在顺序栈中,进栈和出栈的逻辑完全和顺序表的尾插尾删逻辑一样,后续我们会一起实现一个顺序栈的程序,因此在这里就不多赘述了.
📌栈的链式存储结构
栈的链式存储结构,简称为链栈.
因为栈只在栈顶插入或删除的特性,我们在设计链栈时应当把栈顶放在单链表的头部,并且对链表来说,头指针是必须的,而对链栈来说,栈顶指针同样是必须的,因此我们不如将他们合二为一.
链栈示意图:
对于链栈来说,基本不存在栈满的情况.而对空栈来说,链栈的判断条件应该是top=NULL.
链栈的进栈操作
对于链栈的进栈push操作,假设元素新结点是e,top为栈顶指针,则进栈示意图如下:
链栈的出栈操作
对于链栈的出栈pop操作,假设top为栈顶指针,则出栈示意图如下:
📌栈的应用(待补)
🎏递归
🎏括号匹配问题
🎏四则运算表达式求值
结语
当我们了解了栈的定义后,接下来我们将一起实现一个顺序栈程序,由于篇幅有限,我会在下篇博客中为大家详细介绍一下顺序栈的实现,感兴趣的话可以点击下面链接查看:
希望这篇有关数据结构栈的介绍文章能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
数据结构栈和队列篇思维导图
