【数据结构】——栈

一、栈的概念和结构

栈其实就是一种特殊的顺序表，其只允许在一端进出，就是栈的数据的插入和删除只能在一端进行，进行数据的插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵循先进后出LIFO（Last InFirst Out）的原则。

 压栈：栈的插入操作叫做进栈/压栈/入栈，入栈的位置也是在栈顶。

 出栈：栈的删除操作叫做出栈。出栈也是在栈顶。

那么我们的栈是要如何进行实现呢？

我们实现栈的话有两种：链表和数组。

如果是使用链表的话，那么我们要是以头为栈顶，那么我们进行头插的话，就需要先考虑链表是否为空的情况，然后我们的头插的结构也是比较麻烦，每次都需要进行节点的申请。

还有就是进行出栈的时候也比较麻烦。

如果我们使用数组，直接使用数组的尾部为栈顶，那么我们的压栈和出栈都可以直接进行，时间复杂度为O(1)。

不过链表和数组都是可以实现的，不过如果使用链表进行实现的话，我们就推荐使用链表的头为栈顶，然后数组的话我们建议使用数组的尾部为栈顶。这样可以使得压栈和出栈的时间复杂度都为O(1)。

二、栈的实现

1、栈的定义

我们上面提到了，我们实现栈，我们底层使用数组来实现，那么其定义和我们前面学习的顺序表基本是一样的，但是就是我们的栈是有一个限制的，就是其只能在一端进行出入。

栈的定义如下：

其实 arr就是我们存储数据的数组，然后top表示当前我们的栈有多少个元素，capacity就表示我们当前的栈最大的容量。
我们定义好后，那么我们对这个栈进行一个初始化：

因为栈的销毁这里也不做多的解释了。

栈的销毁：

下面我们实现栈的压栈：

我们栈的特点就是其只有一端可以进行压栈和出栈的操作，我们前面说到，我们使用数组来实现的话，那么我们是在数组的尾部进行压栈和出栈，那么我们该如何进行压栈呢？

我们在定义栈的时候，我们有一个成员top其是记录当前我们的栈中的有效成员个数的，那么我们的数组是可以通过下标进行插入数据的，不过要注意的是，我们的栈如果此时为空，而且其表示栈的容量的成员也是空的时候，那么我们就需要进行空间申请的，还有就是栈如果满了，那么我们此时也需要进行空间的申请。不过我们发现我们的栈为空和栈满的时候有个共同点，就是我们的top和capacity是i相等的。所以我们再入栈操作的时候，一开始需要先进行判断当前栈的空间是否足够，不够的话我们要进行扩容，然后我们扩容一般是二倍增容。还有一个特殊情况就是刚开始的时候，我们的容量还是0，那么我们此时进行二倍增容是行不通的，所以我们也特殊处理一下。

代码如下：

 上面我们实现了压栈，那么我们接下来就实现栈的另外一个功能：出栈

我们要出栈，那么我们的栈就要不为空才行，所以我们可以先写一个函数判断栈是否为空，然后通过这个函数我们就可以进行出栈，要注意的是我们的栈，出栈也是要在栈顶这一端，所以也是在数组的末尾端，那么我们的top进行--操作就可以了，那么就可以使得我们的栈的有效元素个数减-，而且是栈顶的第一个元素。

压栈：

 我们栈有时候只是需要取栈顶的元素，并不需要出栈，那么我们也可以写一个函数来实现，我们的取栈顶元素是很简单的，就是访问数组一样，我们就访问下标为top-1的元素即可。

然后我们也可以获取当前栈的实际有效元素个数：

可以看到我们的栈的两个大的功能还是很好实现的，和我们前面的顺序表大致一样，就是其要控制的是，其入栈和出栈的端要一致。