栈是一种只能从一端存取数据并且遵循“后进先出”原则的线性存储结构。这句话中体现了栈结构的三个特征——只能从一端存取数据，遵循“后进先出”的原则和线性存储结构。因此如果我们要实现一个栈结构的数据结构，就必须要满足这三点要求。提到线性结构，最容易想到的就是数组，因此栈结构的底层可以通过数组来存储数据。那么如何实现只能从一段存取数据和“后进先出”的原则呢？这里要知道，后面的这两个条件都和存取数据有关，而且这个存取规则和数组的并不一样，所以就需要重新定义存取规则。这里用一个指针来实现栈结构的存储。
定义一个指针，假设这个指针的名字叫a，一开始指针a指向的元素位置的索引为-1，即没有指向数组中的任何一个元素。当向数组中添加元素时，指针的位置就会向前移动，这样就实现了从一个端口添加元素。当完成添加元素的操作之后，假设已经添加了10个元素，此时最后一个元素的索引应该是9。当要取出元素时，让指针的位置向后移动，即如果取出一个元素，那么指针指向的元素的索引减一。所以进行获取数组中的元素的操作时，元素的索引的变化为9，8，7，6……-1。可以发现，最后添加的元素的索引为9，而它是最先被取出的，这样就实现了“后进先出”的规则。
通过上面的描述，已经知道了实现一个栈结构的基本思路，接下来就来具体实现一个数据结构为栈结构的容器。参考java中已经有的栈容器，要实现一个栈容器需要实现几个基本的方法——empty(判断容器是否为空)，pop(删除栈顶元素，并将栈顶元素返回)，push(将指定的元素添加到栈容器中)。
接下来创建一个栈容器结构，因为在执行添加元素的操作时添加的元素类型是不确定的，为了提高代码的复用性，这里应该将栈容器类定义为一个泛型类。然后根据上面的描述，需要定义一个私有数组来存储数据，这个数组的类型应该采用Object，因为事先并不知道要存入的数据的具体类型，而且因为JDK1.8之后支持延迟加载的操作，就是当需要的时候才创建对象，所以这里可以不指定数组长度。为了方便后期对数组进行扩容操作，还需要指定一个数组的默认长度。此外，记录栈容器当中的元素的个数以及操作元素索引的指针这个两个变量也是必须的。
创建完相关变量，接下来就可以对栈容器中的方法做出具体实现了。首先要实现的是添加元素的方法。因为在定义数组时并没有给出数组的大小，因此要实现添加元素的方法首先就要对数组进行初始化，然后还要将元素添加到容器中，并且此时应该记录元素的数目变化。这里要注意的是，数组的初始化并不是说创建一个简单的数组，因为要提高代码的复用性，在不知道后期究竟要添加多少个元素的情况下，初始化数组应该分为两个部分——在没有数组的情况下创建一个新的数组用来存储添加进来的元素以及在已经有数组的情况下如果原数组的长度不够要对原数组进行扩容两个部分。这样这一个步骤的实现代码就比较长，为了提高代码的可读性应定义一个方法来实现数组的初始化操作。这个方法在演示代码中定义为capacity，在capacity中难点在于理解数组的扩容操作。
扩容操作中包括两个部分，第一个部分，判断是否需要进行扩容操作。这一部分采用的代码为this.size - (this.defaultLength-1) >= 0，其中this.size指的是当前的元素个数，this.defahltLength指的是数组长度，减去1即（this.defaultLength-1）指的是数组的最大索引数。可能会有人认为这里的判断有问题，觉得当前元素个数减去数组的最大索引数这个判断条件不严谨，但是要注意一个问题，那就是如果数组长度已经不能存储元素了，那么就会提示数组元素溢出了。所以应该在数组还没有被存满的情况下进行扩容操作。第二个部分就是进行扩容的部分了，这里采用的代码为 this.defaultLength = this.defaultLength + (this.defaultLength>>1);
this.arr = Arrays.copyOf(this.arr,this.defaultLength);
第一行代码中的右位移运算符>>的意思是除以2，所以这一行代码之后，原数组的长度就被扩充到了原来的1.5倍。第二行是数组的拷贝操作，也就是将原数组的内容拷贝到新的数组中去的操作。
完成了数组的初始化，接下来就需进行添加元素的操作了。这里就是一个简单的赋值操作，因为一开始指针指向的位置为-1，并不是数组中的下标，所以在进行赋值操作之前要先移动指针的位置，具体体现在代码this.arr[++index] = item;中。元素个数的记录就极为简单了，只需要在完成添加元素的操作之后记录个数的变量加一即可。
实现了栈容器中最难实现的添加元素的方法，相对简单的获取元素的方法pop和判断容器是否为空的方法就很简单了。pop方法的内容是返回栈顶元素，因此在返回栈顶元素之前必须要判断容器是否为空，如果元素为空系统就要抛出一个异常，这个异常在java自带的栈容器中有，这里只需要导入即可。而判断容器是否为空也很简单，只需要看指针是否指向-1就行。如果容器不为空，则返回栈顶元素，也就是此时指针指向的元素，返回后指针需要向前一个元素进行移动，具体体现在代码return (E)this.arr[index--];中。这里要说明的是，栈容器中用pop方法取出容器后元素数量会减少，因此应该对size变量进行对应操作。此外，因为定义的数组为Object型，所以取出元素时要对数组进行强制转型。
有了上面的基础，判断栈容器是否为空的方法就超级简单了，只需要根据指针的位置是否在-1的位置上做出相应的判断即可。
import java.util.Arrays;
import java.util.EmptyStackException;
/**
* 自定义栈容器
*/
public class MyStack<E> {
private Object[] arr;//存放元素的物理结构
private int defaultLength = 4;//数组的默认长度
public int size;//记录栈容器的元素个数
private int index = -1;//操作数组索引位置的指针
/**
* 向容器中添加元素
*/
public E push(E item){
//初始化数组
this.capacity();
//添加元素
this.arr[++index] = item;
//记录元素个数
this.size++;
return item;
}
/**
* 数组初始化或者以1.5倍容量扩容
*/
private void capacity(){
//数组初始化
if(this.arr == null){
this.arr = new Object[defaultLength];
}
//数组扩容
if(this.size - (this.defaultLength-1) >= 0){
this.defaultLength = this.defaultLength + (this.defaultLength>>1);
this.arr = Arrays.copyOf(this.arr,this.defaultLength);
}
}
/**
* 获取栈顶元素
*/
public E pop(){
//如果容器为空，抛出异常
if(index == -1){
throw new EmptyStackException();
}
//记录元素个数
this.size--;
//返回元素
return (E)this.arr[index--];
}
/**
* 判断容器是否为空
*/
public boolean empty(){
return this.size == 0;
}
}
至此，我们就创建出了一个栈容器类了，为了验证我们创建的栈容器类是否合理，我们创建一个测试类来对其中的方法进行测试。具体结果如下：
package com.data.demo;
public class MyStackTest {
public static void main(String[] args) {
MyStack<String> myStack = new MyStack<>();
myStack.push("a");
myStack.push("b");
myStack.push("c");
myStack.push("d");
myStack.push("e");
myStack.push("f");
System.out.println(myStack.empty());
System.out.println(myStack.size);
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.empty());
}
}
