public class GreenNodeStack<E> {

    private Node<E> tos;  //reference to the top of stack node
    private int size;     //number of nodes in the stack
    private Node<E> free; //reference to first free node
    private int freeSize; // number of free nodes
	
    public GreenNodeStack(){tos = null; size = 0; free = null; freeSize = 0;}
	
    public int size(){return size;}
	
    public boolean isEmpty(){return tos == null;}

    private Node<E> newNode(E e, Node<E> node){
	if (free == null) return new Node<E>(e,node);
	Node<E> freeNode = free;
	free = free.getNext();
	freeNode.setElement(e);
	freeNode.setNext(node);
	freeSize--;
	return freeNode;
    }
    //
    // reuse a free node or make a new one
    //
	
    public void push(E element){
	tos = newNode(element,tos);
	//tos = new Node<E>(element,tos); 
	size++;
    }
    //
    // NOTE: no overflow exception!
    //
	
    public E top() throws StackException {
	if (isEmpty()) throw new StackException("empty");
	return tos.getElement();
    }

    private void makeFree(Node<E> node){
	node.setNext(free);
	free = node;
	freeSize++;
    }
    //
    // push this node onto the free list
    //
	
    public E pop() throws StackException {
	if (isEmpty()) throw new StackException("underflow");
	Node<E> node = tos;
	E element = node.getElement();
	tos = tos.getNext();
	makeFree(node);
	size--;
	return element;
    }

    private String toString(Node<E> node){
	if (node == null) return "";
	return "," + node.getElement() + toString(node.getNext());
    }
	
    public String toString(){
	String s = "";
	if (size > 0) s = s + tos.getElement() + toString(tos.getNext());
	s = "[" + s + "]  [";
	if (freeSize > 0) s = s + free.getElement() + toString(free.getNext());
	return s + "]";
    }
}