page 5

Code for linked list backed FIFO queue
//time: O(1), extra space: O(1)
public class MyQueue<Item> implements Iterator<Item> {
    private int N;
    private Node first;
    private Node last;
    private class Node {
        private Item item;
        private Node next;
    }
    public boolean isEmpty() {return N == 0;}
    public int size() {return N;}
    public void add(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if(isEmpty) first == last;
        else oldlast.next = last;
        N++;
    }
    public Item poll() {
        Item item = first.item;
        first = first.next;
        if(isEmpty()) last = null;
        N--;
        return item;
    }
    public Iterator<Item> iterator() {
        return new MyIterator();
    }
    private class MyIterator implements Iterator<Item> {
        Node current = first;
        public boolean hasNext() {return current != null;}
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}