重学数据结构（二、栈）

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description 栈接口
 */
public interface Stack {
    public int getSize();          //返回栈中元素数目
    public boolean isEmpty();      //判空
    public Object top();           //取栈顶元素但不删除
    public void push(Object element);      //入栈
    public Object pop();              //出栈
}

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description 顺序栈--数组实现
 */
public class ArrayStack implements Stack{

    private static  int defaultSize=15;   //默认容量
    private int size;                    //实际容量：实际存储元素个数
    private Object[] data;               //存放元素的数组

    /**
     * 无参构造方法：按默认容量构造元素数组
     */
    public ArrayStack() {
        data=new Object[defaultSize];
        size=0;
    }

    /**
     * 有参构造方法：指定元素数组容量
     * @param size
     */
    public ArrayStack(int size){
        data=new Object[size];
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size==0;
    }

    /**
     * 取栈顶元素:不删除栈顶元素
     * @return
     */
    public Object top() {
        if (isEmpty())
            throw new RuntimeException("栈空");
        size--;
        return data[size-1];
    }

    /**
     * 入栈
     * @param element
     */
    public void push(Object element) {
        //数组已满，扩容
         if (size==data.length){
             //扩容两倍的新数组
             Object [] newData=new Object[size<<1];
             //拷贝数组
             System.arraycopy(data,0,newData,0,size);
             data=newData;
         }
         //栈顶上插入新元素
         data[size]=element;
         size++;
    }

    /**
     * 出栈
     * @return
     */
    public Object pop() {
        if (isEmpty())
            throw new RuntimeException("栈空");
        Object top=data[size-1];
        data[size-1]=null;
        size--;
        return top;
    }
}

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description
 */
public class ListStack implements Stack{
    //单向链表
    private SinglyLinkedList list;

    /**
     * 构造函数：初始化单向链表
     */
    public ListStack(){
        list=new SinglyLinkedList();
    }

    /**
     * 获取栈的容量
     * @return
     */
    public int getSize() {
        return list.getSize();
    }

    public boolean isEmpty() {
        return list.getSize()==0;
    }

    /**
     * 取栈顶元素
     * @return
     */
    public Object top() {
        //取列表的尾节点
        return list.get(list.getSize()-1);
    }

    /**
     * 入栈
     * @param element
     */
    public void push(Object element) {
        //队列尾插入
       list.addTail(element);
    }

    /**
     * 出栈
     * @return
     */
    public Object pop() {
        int topIndex=list.getSize()-1;
        //列表为节点
        Object top=list.get(topIndex);
        //删除尾结点
        list.remove(topIndex);
        return top;
    }
}