【数据结构】什么是栈?

人生,需要有进栈出栈精神的体现.在哪里跌倒,就应该在哪里爬起来.无论陷入何等困境,只要抬头能仰望蓝天,就有希望,不断进取,你就可以让出头之日重现.困难不会永远存在,强者才能勇往直前. ——封清扬

📌栈的定义

栈和队列是两种重要的线性结构.从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为限定性的数据结构.但从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型.

栈(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为栈顶指针,则出栈示意图如下:

📌栈的应用(待补)

🎏递归

🎏括号匹配问题

🎏四则运算表达式求值