先入先出队列

public class Queue<Item> {
    private Node first;
    private Node last;
    private  int N;
    private class Node{
        Item item;
        Node next;
    }
    public boolean isEmpty() {return first==0;}
    public int size() {return N ;}
    public void enqueue(Item item){
        //从列尾添加元素
        Node oldlast =last;
        last=new Node();
        last.item=item;
        last.next=null;
        if (isEmpty()) first=last;
        else oldlast.next=last;
        N++;
    }
    public  Item dequeue(){
        //从列头删除元素
       Item item = first.item;
       first=first.next;
       if (isEmpty())  last=null;
       N--;
       return  item;

    }
}

链表是数组的一种重要的替代方式
与下压堆栈的不同点在于增加和删除元素时都得判断队列是否为空，从而调整头和尾指针，增加时为空调整头指针，删除时为空调整尾指针。