数据结构篇|栈

1. 简介

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——出自百度百科

栈的使用场景

• 编辑器的撤销操作
• 程序系统栈的调用

2. 栈的实现

实现这个栈在这里我选择复用上一篇文章实现的数组的一些方法，链接如下：

https://www.jianshu.com/p/a3c902e6cc94

  public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
  }

将实现的Array类拷贝过来之后，接着我们需要创建一个接口，这个接口中包含上图代码所示的方法，方法的作用基本和字面意思一样。getSize()方法表示获取栈中元素的个数，isEmpty()表示判断栈是否为空，push()表示向栈中添加一个E类型的元素，这里的E是泛型的类型，pop()方法是将一个元素进行出栈，peek()方法表示查看栈顶的元素是什么并将其返回。

3. 实现类的设计

  public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

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

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

创建完了接口之后我们再创建一个实现类，就取名叫做ArrayStack。类中包含的成员变量是复制过来的Array类，然后还有两个构造方法，第一个是需要传入一个栈的容量capacity，然后在方法中实现Array类并将容量设置为capacity。第二个构造方法适用于不知道栈需要多大容量的情况，这里就直接实例化Array类，那么容量就是10了。

• getSize()、isEmpty()方法的实现

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

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

这两个方法非常简单，getSize()方法是获得栈中元素个数的方法，那么就直接调用Array类中的getSize()方法即可。isEmpty()也是同样的，直接调用Array类中的方法即可。

• getCapacity()方法

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

这个方法的作用是获取栈的容量，那么直接调用对应方法即可。

• push()、pop()、peek()方法

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

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

    @Override
    public E peek(){
        return array.get(array.getSize()-1);
    }

这三个方法的实现也是可以复用Array类中的方法的。push()方法是向栈中添加元素，这里我们调用addLast()方法，直接向数组的末尾添加元素。pop()方法是让栈顶元素出栈，所以直接调用removeLase()即可。peek()方法是为了查看栈顶元素，所以我们需要查看数组中的最后一个元素。这里调用了Array类中的get()方法，传入的参数是数组中的最后一个元素。

• 测试ArrayStack
  这样我们就通过复用自己实现的Array类，实现了栈应该具有的功能。接下来就实现一个方法来测试我们的栈吧！

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