/** Eine Klasse fuer Stapel bzw. Stacks. Ein Stack ist eine
    dynamische Datenstruktur, in die man eine beliebig hohe 
    Anzahl von Objekten einfuegen und die in ihr vorhandenen
    wieder aus herausnehmen kann. Dabei gilt das LIFO-Prinzip
    ("last in first out"): Das zuletzt eingefuegte Element ist
    dasjenige, das zuerst herausgenommen wird - ganz wie bei 
    einem Stapel Teller z.B. 
*/

public class LIFO
{
    private Object[] stapel;
    private int laenge = 1;  // zunaechst hier den "magischen Wert" 10 gehabt
    private int naechsterIndex;  // Index, an den geschrieben wird und bis zu
                                 // dem die gespeicherten Eintraege liegen

    /** Erzeugt einen leeren Stapel. */
    public LIFO()
    {
	stapel = new Object[laenge];
	naechsterIndex = 0;
    }

    /** Legt ein Element x auf den Stapel.
	@param x das Element */
    public void in(Object x)
    {
	if (naechsterIndex == laenge){  // dies ist der böse Fall!
	    int neueLaenge = 2 * laenge;
	    Object[] neuerStapel = new Object[neueLaenge];
	    for (int i = 0; i<laenge; i++){ // oder stapel.length statt laenge
		neuerStapel[i] = stapel[i]; // umkopieren
	    }
	    stapel = neuerStapel; // geht, weil der Typ nicht die Länge enthält
	    /* damit wird der alte Inhalt von stapel irrelevant und kann dann
	       vom Java Garbage Collector "weggeräumt" werden */
	    laenge = neueLaenge;  // nicht vergessen!
	}
	stapel[naechsterIndex] = x;
	naechsterIndex++;
    }

    /** Liefert von einem nicht-leeren Stapel das "oberste Element", sprich
	dasjenige, das unter den im Stapel vorhandenen zuletzt eingetragen 
        wurde. Ist der Stapel leer, so wird null zurueckgeliefert.
	@return das Element */
    public Object out()
    {
	// zunächst hatten wir bloß null zurückgegeben, damit die Klasse
	// immerhin kompilierte
	if (this.empty()){   // "this." ist unnoetig
	return null;
	}
	else{
	    naechsterIndex--;
	    return stapel[naechsterIndex];
	}
    }

    /** Testet, ob der Stapel leer ist. */
    public boolean empty()
    {
	return (naechsterIndex == 0);
	// zunächst hatte hier bloss "return true" gestanden
    }
}