【数据结构】栈（1）

1.栈的概念

栈：一种特殊的线性表，栈只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。

进栈：将元素放入栈中称为进栈、入栈或压栈

出栈：将元素从栈中删除称为出栈

注：栈的所有操作都是在栈顶操作，因为栈遵循先进后出的原则

2.栈的方法

上述是在Java中的栈的方法，接下来我们就来看看上述常用方法的功能

3.模拟实现栈

栈的所有操作只能在固定一端进行操作，所以它可以采取数组和链表进行存储

采用数组进行存储：可以在尾部进行插入和删除操作，这样时间复杂度为O(1)，但是美中不足点就是需要考虑扩容  

采用单链表进行存储：插入操作时间复杂度为O(1)，删除操作时间复杂度为O(n)

采用双链表进行存储：插入和删除操作时间复杂度为O(1)，但是需要存储上一个节点的地址和下一个节点的地址

从时间复杂度和空间复杂度的角度，数组实现栈更好一点。并且Java内部也是用数组实现的存储栈

那接下来我们就用数组实现栈：

首先我们得写一个类，将栈的实现过程，成员方法成员属性全部放在这个类中：

public class MyStack {
}

3.1 成员属性

定义一个 elem 的数组用来存放数据 ，在定义一个整型变量 size 记录有效元素的个数。栈的所有操作都是在一端进行的，我们可以通过 size -1 找到最后一个元素的位置

private int[] elem; //存放数据的数组
private int size; //有效元素个数
private static final int DEFAULT_CAPACITY = 10; //约定好的默认容量

3.2 构造方法

每一次实例化 MyStack 这个类时，都会自动调用这个构造方法，这个构造方法会给 elem 数组开辟 DEFAULT_CAPACITY （10）个空间，构造方法在对象的运行期间只会执行一次

public MyStack() {
    this.elem = new int[DEFAULT_CAPACITY];
    this.size = 0;
}