page 6

Code for array backed LIFO stack
//time: O(1), extra space: O(1)
public class MyStack<Item> {
    private int N = 0;
    private Item[] a = (Item[]) new Object[1];
    pubic boolean isEmpty() {return N == 0;}
    public int size() {return N;}
    private void resize(int cap) {
        Item[] tmp = (Item[])new Object[cap];
        for(int i = 0; i < a.length; i++) {
            tmp[i] = a[i];
        }
        a = tmp;
    }
    public void push(Item item) {
        if(N == a.length) resize(N*2);
        a[N++] = item;
    }
    public Item pop() {
        Item item = a[--N];
        a[N] = null;
        if(N > 0 && N < a.length/4) resize(a.length/2);
        return item;
    }
    public Iterator<Item> iterate() {
        return new MyIterator();
    }
    private class MyIterator implements Iterator<Item> {
        int i = N;
        public boolean hasNext() {return i > 0;}
        public Item next() {
            return a[--i];
        }
    }

}