Consider Bloch's non$-$generic Stack implementation;

public class Stack $\{$

private Object$[]$ elements;

private int size $=0$;

private static final int DEFAULT$\_$INITIAL$\_$CAPACITY $=16$;

public Stack$()\{$

this.elements $=$ new Object$[$DEFAULT$\_$INITIAL$\_$CAPACITY$]$;

$\}$

public void push $($Object e$)\{$

ensureCapacity$()$;

elements$[$size$++]=$ e;

$\}$

public Object pop $()\{$

if $($size $==0)$ throw new IllegalStateException$("$Stack$.$pop"$)$;

Object result $=$ elements$[--$size$]$;

elements$[$size$]=$ null; $//$ Eliminate obsolete reference

return result;

$\}$

private void ensureCapacity$()\{$

if $($elements$.$length $==$ size$)\{$

Object oldElements$[]=$ elements;

elements $=$ new Object$[2*$size $+1]$;

System.arraycopy$($oldElements$,0,$ elements, $0,$ size$)$;

$\}$

$\}$

$\}$

$1.$Rewrite Stack to be immutable. Keep the representation variables elements and size.

$2.$Do the right thing with push$().$

$3.$Do the right thing with pop$().$

$4.$Get rid of anything that doesn't make sense in an immutable data type.