s.push(1);
s.pop();
s.size();
s.isEmpty();
s.iterator();
Solution: the time complexity for push, pop, size, isEmpty are O(1), when resize is needed, the time cost is O(N), the time cost for iterator is O(N). The space complexity is O(N).
import java.util.Iterator;
public class MyArrayStack <Item> implements Iterable<Item>{
private int N = 0;
private Item[] a = (Item[])new Object[1];
public boolean isEmpty() { return N == 0;}
public int size() {return N;}
private Item[] resize(int maxN) {
Item[] tmp = (Item[])new Object[maxN];
for(int i = 0; i < N; i++) {
tmp[i] = a[i];
}
a = tmp;
return a;
}
public void push(Item item) {
if(N == a.length) {
a = resize(a.length*2);
}
a[N++] = item;
}
public Item pop() {
if(isEmpty()) return null;
Item result = a[--N];
a[N] = null;
if(N > 0 && N == a.length/4) {
a = resize(a.length/2);
}
return result;
}
@Override
public Iterator<Item> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<Item> {
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
}
public static void main(String[] args) {
MyArrayStack<Integer> stack = new MyArrayStack<>();
stack.push(5);
stack.push(10);
stack.push(1);
Iterator<Integer> it = stack.iterator();
System.out.println();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
System.out.println(stack.size());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
stack.push(7);
stack.push(3);
System.out.println(stack.size());
}
}
