栈的Java实现

一.概述

栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。（类似弹夹装子弹）
栈是一种逻辑层面的数据结构，最终要使用物理存储结构来实现。物理存储结构有顺序存储结构（数组）和链式存储结构（链表）。
栈既可以用数组实现也可以用链表来实现。

二.用链表实现栈

压栈：
为了能够在遍历时先遍历到的是后面加入的元素，将使用头插法进行压栈！每次弹栈时弹的都是头节点指向的元素。
设有head头节点，当插入第一个元素：

当插入第二个元素，则插在①元素的前面，和head的后面（head仅作为标记节点，并不存储元素），
即令head指向②，②指向①即完成头插法：

弹栈：

弹出首结点指向的结点即可（后进先出），首结点指向的结点即为栈顶。

总结：头插头取，区别于队列。

代码实现：

public class stackLinkList<T> implements Iterable<T>{
    private int N;
    private Node head;

    public stackLinkList(){  //初始化栈空间
        this.head=new Node(null,null); //初始化标记(首)节点
        this.N=0;
    }

    private class Node{  //内部类
        public T item;
        public Node next;  //成员变量名和局部变量名可重复

        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
    public void push(T t){ //压栈（头插）
    //记录原来首结点指向的第一个结点
        Node oldFirst=head.next;
    //创造新结点
        Node newNode=new Node(t,null);
    //新结点指向oldFirst
        newNode.next=oldFirst;
    //首结点指向新节点
        head.next=newNode; //新加进来的结点为栈顶
        N++;
    }
    public T pop(){//弹栈（头取）
    //记录首结点指向的第一个非空结点，即栈顶
        Node oldFirst=head.next; 
        if(oldFirst.next!=null) {
            //首结点指向oldFirst的下一个结点
            head.next = oldFirst.next;
            N--;
            return oldFirst.item;//后进先出！弹出栈顶结点的值
        }else{
            return null;
        }
    }



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

    public int size(){
        return N;
    }

    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }

    public class MyIterator implements Iterator {
        private Node n; //记录每次遍历拿到的当前结点

        public MyIterator() {
            this.n = head;//初始化当前结点n
        }
        @Override
        public boolean hasNext() {
            return n.next != null; //n.next 不为null即还有下一个元素
        }


        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
        public static void main(String[] args) {
            stackLinkList<String> s1=new stackLinkList<>();
            s1.push("a");
            s1.push("b");
            s1.push("c");
            for (String k : s1) {
                System.out.println(k);
            }
            System.out.println("==================");
            s1.pop();
            for (String k : s1) {
                System.out.println(k);
            }
        }
    }