/**
 * 該接口是：棧的頂層接口
 * 他的實現(xiàn)類會有：順序棧、鏈棧
 *
 * 棧：先入后出
 */
public interface IStack {
    void clear();//清空方法
    boolean isEmpty();//判空方法
    int length();//棧深度方法
    Object peek();//取棧頂元素并返回值，若棧為空，返回null
    void push(Object object) throws Exception;//入棧操作,元素進入棧頂
    Object pop();//將棧頂元素出站
}

public class Node {
    public Object object;
    public Node next;

    public Node(){
    }
    public Node(Object object){
        this.object = object;
    }
    public Node(Node next){
        this.next = next;
    }
    public Node(Object object,Node next){
        this.object = object;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "object=" + object +
                ", next=" + next +
                '}';
    }
}

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className LinkedStack:該棧類，使用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)，是鏈棧，這里使用單鏈表的方式實現(xiàn)
 * @date 2021-04-20 16:32
 *
 * 棧的特點是先進后出：
 * 因此我們可以使用頭插法，每次在頭部插入，出棧時只需獲取鏈表的頭結(jié)點即可。
 *
 * 鏈棧與順序棧的區(qū)別：
 * 順序棧底層是數(shù)組，因此必須初始化一個數(shù)組的容量，也就是棧的容量，鏈棧則無需此操作
 * 對比鏈棧和順序棧的實現(xiàn)，可以發(fā)現(xiàn)入棧和出戰(zhàn)方法的時間復(fù)雜度都是O（1），效率上沒有區(qū)別，但是順序棧占用的空間會相對更多
 * 一些，順序棧是通過指針指向假設(shè)的棧頂，其他元素其實依然存在，但鏈棧的棧頂之前的元素會被垃圾回收，因此鏈棧的實現(xiàn)綜合時間和
 * 空間來看，更優(yōu)秀一些。
 */
public class LinkedStack implements IStack {
    //這是首結(jié)點
    Node node;

    public LinkedStack(){
        node = new Node();
    }
}

    @Override
    public void clear() {
        node.next = null;
        node.object = null;
    }

    @Override
    public boolean isEmpty() {
        return node.object==null?true:false;
    }

    @Override
    public int length() {
        if(node.object==null)
            return 0;
        int j= 1;
        Node nodeNew = node;
        while(nodeNew.next!=null){
            j++;
            nodeNew = nodeNew.next;
        }
        return j;
    }

    @Override
    public void push(Object object) throws Exception {
        if(node.object==null){
            node.object = object;
            return;
        }
        //頭插法
        node = new Node(object,node);
    }

    @Override
    public Object peek() {
        return node.object;
    }

    @Override
    public Object pop() {
        if(node.object==null)
            return null;
        Node tem = node;
        node = node.next==null?new Node():node.next;
        return tem.object;
    }

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className LinkedStack:該棧類，使用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)，是鏈棧，這里使用單鏈表的方式實現(xiàn)
 * @date 2021-04-20 16:32
 *
 * 棧的特點是先進后出：
 * 因此我們可以使用頭插法，每次在頭部插入，出棧時只需獲取鏈表的頭結(jié)點即可。
 *
 * 鏈棧與順序棧的區(qū)別：
 * 順序棧底層是數(shù)組，因此必須初始化一個數(shù)組的容量，也就是棧的容量，鏈棧則無需此操作
 * 對比鏈棧和順序棧的實現(xiàn)，可以發(fā)現(xiàn)入棧和出戰(zhàn)方法的時間復(fù)雜度都是O（1），效率上沒有區(qū)別，但是順序棧占用的空間會相對更多
 * 一些，順序棧是通過指針指向假設(shè)的棧頂，其他元素其實依然存在，但鏈棧的棧頂之前的元素會被垃圾回收，因此鏈棧的實現(xiàn)綜合時間和
 * 空間來看，更優(yōu)秀一些。
 */
public class LinkedStack implements IStack {
    //這是首結(jié)點
    Node node;

    public LinkedStack(){
        node = new Node();
    }

    @Override
    public void clear() {
        node.next = null;
        node.object = null;
    }

    @Override
    public boolean isEmpty() {
        return node.object==null?true:false;
    }

    @Override
    public int length() {
        if(node.object==null)
            return 0;
        int j= 1;
        Node nodeNew = node;
        while(nodeNew.next!=null){
            j++;
            nodeNew = nodeNew.next;
        }
        return j;
    }

    @Override
    public Object peek() {
        return node.object;
    }

    @Override
    public void push(Object object) throws Exception {
        if(node.object==null){
            node.object = object;
            return;
        }
        //頭插法
        node = new Node(object,node);
    }

    @Override
    public Object pop() {
        if(node.object==null)
            return null;
        Node tem = node;
        node = node.next==null?new Node():node.next;
        return tem.object;
    }
}