Stack 栈

栈也是一种线性的数据结构。栈主要支持两种操作：push 和 pop。我们用前面实现的动态数组Array来实现我们自己的栈！

什么时是栈？

栈也是一种线性的，用于存储数据的线性数据结构。栈主要支持两种操作

1. 入栈, 也称 Push

2. 出栈, 也称 Pop

栈满足FILO规则，也就是先进后出规则。

比如下图中的"Apple"元素第一个 入栈，被放到了栈底。"Fries"最后一个入栈，被放到了栈顶。当元素出栈的时候，位于栈顶的元素第一个出栈，越靠近栈底的元素越后出栈。

栈的内部也有一个size指针, 指向下一个入栈的元素位置。push操作以后, size指针上移，pop操作以后, size指针下移。

这么一看我们完全可以利用我们上一节实现的Array来实现我们自己的栈！

栈的实现

栈的实现有多种方式，一种是通过动态数组, 另一种是通过链表。

为了增强代码的复用性和解耦，我们不从头实现一个栈。而是定义一个栈的接口, 动态数组或者链表，去实现这个接口即可。而事实上，通过我们上一节所学的Array来实现一个栈是非常简单的。

public interface IStack <E>{

    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();

}

push()方法 将一个元素入栈。peek() 方法返回栈顶的元素，但是不取出。pop()方法取出栈顶元素并返回。其他两个方法与Array相同, 这里就不做解释了。

随后我们定义一个ArrayStack 类去实现 IStack 接口即可。

public class ArrayStack<E> implements IStack<E> {
    Array<E> array;

    public ArrayStack(int capacity) {
        this.array = new Array<E>(capacity);
    }

    public ArrayStack() {
        this.array = new Array<E>();
    }

    @Override
    public int getSize() {
        return this.array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return this.array.isEmpty();
    }

    @Override
    public void push(E e) {
        this.array.addLast(e);
    }

    @Override
    public E pop() {
        return this.array.removeLast();
    }

    @Override
    public E peek() {
        return this.array.getLast();
    }

    public int getCapacity(){
        return this.array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res=new StringBuilder();
        res.append("Stack : ");
        res.append(" [ ");
        for (int i = 0; i < this.array.getSize(); i++) {
            res.append(this.array.get(i));
            if (i!=array.getSize()-1){
                res.append(", ");
            }
        }
        res.append(" ] top");
        return res.toString();
    }
}

可以看出，所有栈的操作, 都可以直接调用Array 的方法进行实现。

最后定义一个ArryStackTest类进行测试。我们依次向栈内push 数字0到5， 随后打印输出，再pop两次，再次输出

public class ArrayStackTest {

    public static void main(String[] args) {
        ArrayStack<Integer> stack=new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        stack.pop();
        System.out.println(stack);
    }
}

输出结果:

Stack :  [ 0 ] top
Stack :  [ 0, 1 ] top
Stack :  [ 0, 1, 2 ] top
Stack :  [ 0, 1, 2, 3 ] top
Stack :  [ 0, 1, 2, 3, 4 ] top
Stack :  [ 0, 1, 2 ] top