数据结构入门——大师：stack(一) ArrayStack

1.什么是栈

栈是一种后进先出的数据结构，也称LIFO，我们这里就用之前的Array类来实现一个底层是数组的栈

2.先定义一个接口，定义栈有哪些操作

public interface Stack<E> {
    /**
     * 获取栈内元素
     * @return 元素
     */
    int getSize();

    /**
     * 判断栈是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 压栈
     * @param e 要压入的元素
     */
    void push(E e);

    /**
     * 弹栈
     * @return 弹出栈的元素
     */
    E pop();

    /**
     * 查看栈顶元素
     * @return
     */
    E peek();
}

压栈 就是栈进入元素，弹栈也就是出栈

3.我们开始实现这些操作

/**
     * 这里底层是一个数组
     */
    private ArrayE<E> array;

    /**
     * 这里的栈的容量就是数组的容量
     * @param capacity 容量
     */
    public ArrayStack(int capacity){
        array = new ArrayE<E>(capacity);
    }

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

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

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

这里是一些初始化的操作

/**
     * 压栈也就是在数组尾部添加元素
     * @param e 要压入的元素
     */
    @Override
    public void push(E e) {
        array.addLast(e);
    }


    /**
     * 弹栈，由于是后进先出的数据结构，因此我们将末尾的元素移除出去，
     * 因为最先进来的肯定是末尾的元素
     * @return 出栈的元素
     */

    @Override
    public E pop() {
        //因为压入的元素在array的末尾，而stack必须是后进先出，因此应该移除最后一个
        return array.removeLast();
    }

    /**
     * 查看栈顶元素
     * @return 我们只要看数组的末尾元素即可
     */
    @Override
    public E peek() {
        return array.getLast();
    }

    @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();
    }

以上就是其核心的进栈出栈的操作