[数据结构与算法]对数据结构——栈的理解（分别用数组和链表实现）

对栈的理解：

?栈是一种只能在一端进行插入或删除操作的线性表，特点是先进后出，所以用链表实现栈时，链表存储数据元素采用“头插法”，出栈时从头结点的下一个结点开始出栈；

用数组实现时，越后进栈的元素索引越大，出栈时索引大的元素先出栈；

以上两种方法均实现了“先进后出”的特点

不同的是，用数组实现时要初始化数组容量、由于数组容量确定，所以存在栈上溢出的风险

1、用链表实现：

public class Stack<T>{
    //首结点
    private Node head;
    //栈中的元素
    private int N;
    //内部结点类
    private class Node{
        public T item;
        public Node next;
        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }
    public Stack(){
        this.head = new Node(null,null);
        this.N = 0;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    //压栈
    public void posh(T t){
         //找到首结点指向的第一个结点
        Node oldFirst = head.next;
        //创建新结点
        Node newNode = new Node(t, null);
        //让首结点指向新结点
        head.next = newNode;
        //让新结点指向原来第一个结点
        newNode.next = oldFirst;
        //元素个数+1
        N++;
    }
    //弹栈
    public T pop(){
         //先找到首结点指向的第一个结点
        Node oldFirst = head.next;
        //让首结点指向第一个结点的下一个结点
        if (oldFirst==null){
            return null;
        }
        head.next = oldFirst.next;
        //元素个数-1
        N--;
        return oldFirst.item;
    }
    //栈顶元素
    public T top(){
        return head.next.item;
    }

2、用数组实现：

public class Stack_Arrays<T> {
    //用数组实现栈
    private T[] arrays;
    private int N;
    private int capacity;
    public Stack_Arrays(int capacity){
        //初始化存放数据的数组
        this.arrays = (T[]) new Object[capacity];
        this.N = 0;
    }
    //栈中元素个数
    public int size(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }
    //进栈
    public void push(T t){
        //System.out.println("a");
        /*if (size()>=capacity){
            return;
        }*/
        arrays[N++] = t;
    }
    //出栈
    public T pop(){
        if (size()>0){
            T t = arrays[size()-1];
            N--;
            return t;
        }
        return null;
    }
}