import java.lang.Object;

/** 
Die Klasse "Stack" enthält die Funktionalität eines Stacks / Kellerspeichers. 
Fabian Wleklinski 1999.
**/

class Stack {
	
	// ********** Public **********
	
	// Konstruktor. Erwartet zwei Parameter, die initiale Stackgröße, und den
	// Inkrement-Betrag für Erhöhung der Stackgröße
	public Stack(int initialCapacity, int capacityIncrement) {
  	super();
    this.items = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
	}
	
	// fügt einen Wert hinzu
	public void push( Object item ) {
		// für ausreichende Kapazität sorgen
		ensureCapacity(elementCount + 1);
		// neues Objekt speichern
	  items[elementCount++] = item;
  }
	
	/**
	liefert das "oberste" Element und löscht es
	**/
	public Object pop() {
		// "Oberstes" Element holen
		Object item = top();
		// "Oberstes" Element löschen
		elementCount--;
		
		return item;
	}
	
	/**
	liefert das "oberste" Element
	**/
	public Object top() {
		
    // Wenn Stack leer ist  -->  Fehler
		if (elementCount == 0) 
			throw new EmptyStackException();
		
  	return items[ elementCount-1 ];
	}
	
	/**
	ermittelt, ob der Stack leer ist
	**/
	public boolean isEmpty() {
		return (elementCount == 0);
	}
		
	/**
	stellt sicher, daß der Stack mindestns die angegebene Kapazität besitzt.
	**/
  public void ensureCapacity(int minCapacity) {
	  int oldCapacity = items.length;
	  if (minCapacity > oldCapacity) {
	    Object oldItems[] = items;
	    int newCapacity = (capacityIncrement > 0) ?
		    (oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	if (newCapacity < minCapacity) 
		    newCapacity = minCapacity;
	    items = new Object[newCapacity];
	    System.arraycopy(oldItems, 0, items, 0, elementCount);
	  }
	}
	
	// ********** Protected **********
		
	/** Der Puffer, in dem die Elemente gehalten werden **/
  protected Object items[];
		
	/** Inkrement-Betrag für Erhöhung der Stackgröße **/
	protected int capacityIncrement;

	/** Anzahl der Elemente im Stack **/
	protected int elementCount;
	  
}

/** 
Die Klasse "EmptyStackException" enthält eine Exception, die ausgelöst wird, wenn
versucht wird, von einem "leeren" Stack zu lesen.
Fabian Wleklinski 1999.
**/

class EmptyStackException extends RuntimeException {
  public EmptyStackException() {
  }
}