栈和队列的实现（数组实现，链表实现）

栈的实现方式
##数组实现
public interface  MyStack<Item> extends Iterable<Item>{
        MyStack<Item> push(Item item);
        Item pop() throws Exception;
        boolean isEmpty();
        int size();
}
import java.util.Iterator;

public class ArrayStack<Item> implements MyStack<Item> {
    //栈元素数组只能通过转型来创建泛型数组
    private Item[] a=(Item[]) new Object[1];
    //元素数量
    private int N=0;


    @Override
    public MyStack<Item> push(Item item) {
        check();
        a[N++]=item;
        return this;
    }

    private void check() {
        if(N>=a.length){
            resize(2*a.length);
        }else if(N>0 && N<=a.length/4){
            resize(a.length/2);
        }
    }

    private void resize(int i) {
        Item[] temp=(Item[]) new Object[i];
        for (int j = 0; j <N ; j++) {
            temp[j]=a[j];
        }
        a=temp;
    }

    @Override
    public Item pop() throws Exception {
        if(isEmpty()){
            throw new Exception("Stack is Empty!");
            }
        Item item=a[--N];
        check();
        a[N]=null;//避免对象游离
        return item;
    }

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

    @Override
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        //返回逆序遍历的迭代器
        return new Iterator<Item>() {
            private int i=N;
            @Override
            public boolean hasNext() {
                return i>0;
            }

            @Override
            public Item next() {
                Item item=a[--i];
                return item;
            }
        };
    }
}
##链表实现
import java.security.spec.DSAPrivateKeySpec;
import java.util.Iterator;
import java.util.PriorityQueue;

public class ListStack<Item> implements MyStack<Item> {
    private Node top=null;
    private int N=0;
    private class Node{
        Item item;
        Node next;
    }
    @Override
    public MyStack<Item> push(Item item) {
        Node newTop=new Node();
        newTop.item=item;
        newTop.next=top;
        top=newTop;
        N++;
        return this;
    }

    @Override
    public Item pop() throws Exception {
        if(isEmpty()){
            throw new Exception("Stack is Empty！");
        }
        Item item=top.item;
        top=top.next;
        N--;
        return item;
    }

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

    @Override
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node cur=top;
            @Override
            public boolean hasNext() {
                return cur!=null;
            }

            @Override
            public Item next() {
                Item item=cur.item;
                cur=cur.next;
                return item;
            }
        };
    }
}
###队列
#链表实现
public interface MyQueue<Item> extends Iterable<Item> {
    int size();
    boolean isEmpty();
    MyQueue<Item> add(Item item);
    MyQueue<Item> remove() throws Exception;
}
import javax.xml.soap.Node;
import java.nio.file.NotDirectoryException;
import java.util.Iterator;

public class ListQueue<Item> implements MyQueue<Item> {
    private Node first;
    private Node last;
    private int N=0;
    private class Node{
        Item item;
        Node next;
    }
    @Override
    public int size() {
        return N;
    }

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

    @Override
    public MyQueue<Item> add(Item item) {
        Node newNode=new Node();
        newNode.item=item;
        newNode.next=null;
        if(isEmpty()){
            last=newNode;
            first=newNode;
        }else{
            last.next=newNode;
            last=newNode;
        }
        N++;
        return this;
    }

    @Override
    public MyQueue<Item> remove() throws Exception {
        if(isEmpty()){
            throw new Exception("stack is empty!");
        }
        Node node=first;
        first=first.next;
        N--;
        if(isEmpty()){
            last=null;
        }
        return (MyQueue<Item>) node.item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            ListQueue.Node cur=first;
            @Override
            public boolean hasNext() {
                return cur!=null;
            }

            @Override
            public Item next() {
                Item item= (Item) cur.item;
                cur=cur.next;
                return item;
            }
        };
    }
}