【数据结构】——栈

一、栈的概念和结构

栈实在就是一种特殊的次序表，其只允许在一端进出，就是栈的数据的插入和删除只能在一端举行，举行数据的插入和删除操纵的一端称为栈顶，另一端称为栈底。栈中的元素遵照先辈后出LIFO（Last InFirst Out）的原则。
 压栈：栈的插入操纵叫做进栈/压栈/入栈，入栈的位置也是在栈顶。
 出栈：栈的删除操纵叫做出栈。出栈也是在栈顶。

那么我们的栈是要怎样举行实现呢？
我们实现栈的话有两种：链表和数组。
假如是利用链表的话，那么我们要是以头为栈顶，那么我们举行头插的话，就须要先思量链表是否为空的情况，然后我们的头插的结构也是比力贫苦，每次都须要举行节点的申请。
还有就是举行出栈的时间也比力贫苦。
假如我们利用数组，直接利用数组的尾部为栈顶，那么我们的压栈和出栈都可以直接举行，时间复杂度为O(1)。
不外链表和数组都是可以实现的，不外假如利用链表举行实现的话，我们就保举利用链表的头为栈顶，然后数组的话我们发起利用数组的尾部为栈顶。如允许以使得压栈和出栈的时间复杂度都为O(1)。
二、栈的实现

1、栈的界说
我们上面提到了，我们实现栈，我们底层利用数组来实现，那么其界说和我们前面学习的次序表基本是一样的，但是就是我们的栈是有一个限制的，就是其只能在一端举行收支。
栈的界说如下：

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

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

下面我们实现栈的压栈：
我们栈的特点就是其只有一端可以举行压栈和出栈的操纵，我们前面说到，我们利用数组来实现的话，那么我们是在数组的尾部举行压栈和出栈，那么我们该怎样举行压栈呢？
我们在界说栈的时间，我们有一个成员top其是记载当前我们的栈中的有用成员个数的，那么我们的数组是可以通过下标举行插入数据的，不外要留意的是，我们的栈假如此时为空，而且其表现栈的容量的成员也是空的时间，那么我们就须要举行空间申请的，还有就是栈假如满了，那么我们此时也须要举行空间的申请。不外我们发现我们的栈为空和栈满的时间有个共同点，就是我们的top和capacity是i相称的。所以我们再入栈操纵的时间，一开始须要先举行判断当前栈的空间是否足够，不敷的话我们要举行扩容，然后我们扩容一样平常是二倍增容。还有一个特殊情况就是刚开始的时间，我们的容量照旧0，那么我们此时举行二倍增容是行不通的，所以我们也特殊处理惩罚一下。
代码如下：

 上面我们实现了压栈，那么我们接下来就实现栈的别的一个功能：出栈
我们要出栈，那么我们的栈就要不为空才行，所以我们可以先写一个函数判断栈是否为空，然后通过这个函数我们就可以举行出栈，要留意的是我们的栈，出栈也是要在栈顶这一端，所以也是在数组的末了端，那么我们的top举行--操纵就可以了，那么就可以使得我们的栈的有用元素个数减-，而且是栈顶的第一个元素。
压栈：

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

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

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