StapelListe

Polymorphe Implementierung der Schnittstelle Stapel als verkettete Liste aus der Bibliothek für das Lehrbuch Programmieren mit Java

Dokumentation Programmtext ohne Dokumentation

/*
 * @(#)kapitel9/StapelListe.java
 *	Bibliothek für das Lehrbuch in Java
 *	@author Prof. Solymosi, (c): APSIS GmbH
 *	@version 3.0
 *	@date 28. August 2000
*/
package lehrbuch.kapitel9;

/** Polymorphe Implementierung des Stapels als verkettete Liste */
public class StapelListe implements Stapel {

	/** parameterloser Konstruktor */
	public StapelListe() {
		anker = null;
	}

	/** Kopierkonstruktor.
		@param quelle const der zu kopierende Stapel
		@exception VollAusnahme der kopierte Stapel kann wegen Speichermangel nicht erstellt werden
	*/
	public StapelListe(final StapelListe quelle) throws VollAusnahme {
		this();
		kopieren(quelle);
	}

	/** entleert den Stapel */
	public void entleeren() {
		anker = null;
	}

	/** Trägt ein Element in den Stapel ein.
		@param element const das einzutragende Objekt
		@exception VollAusnahme das Objekt kann nicht mehr eingetragen werden
		@see StapelListe#istVoll
	*/ 
	public void eintragen (final Object element) throws VollAusnahme {
		try {
			anker = new Knoten(element, anker);
		}
		catch(OutOfMemoryError ausnahme) {
			throw new VollAusnahme();
		}
	}

	/** Gibt das jüngste Element aus dem Stapel.
		const
		@return das jüngste Element im Stapel
		@exception LeerAusnahme es gibt kein Objekt im Stapel
		@see StapelListe#istLeer
	*/ 
	public Object lesen () throws LeerAusnahme {
		try {
			return anker.wert;
		}
		catch(NullPointerException ausnahme) {
			throw new LeerAusnahme();
		}
	}

	/** Entfernt das jüngste Element aus dem Stapel.
		@exception LeerAusnahme es gibt kein Objekt im Stapel
		@see StapelListe#istLeer
	*/ 
	public void entfernen() throws LeerAusnahme {
		try { anker = anker.verbindung; }
		catch(NullPointerException ausnahme) { throw new LeerAusnahme(); }			
	}

	/** Überprüft ob der Stapel leer ist.
		Wenn false, LeerAusnahme wird nicht ausgelöst.
		const
		@return true wenn der Stapel leer ist
		@see StapelListe#lesen
		@see StapelListe#entfernen
	*/
	public boolean istLeer(){
		return anker == null;
	}

	/** Überprüft ob der Stapel voll ist.
		const
		Wenn false, VollAusnahme wird nicht ausgelöst.
		@return true wenn der Stapel voll ist
		@see StapelListe#eintragen
	*/
	public boolean istVoll() {
		try {
			Knoten knoten = new Knoten(); // Versuch
			return false; // ist gelungen
		} catch(OutOfMemoryError ausnahme) {
			return true; // kein Platz mehr
		}
	}

	// Implementierungen für kopieren und istGleich: mit Wiederholung und rekursiv
	/** Kopiert Inhalt des Stapels.
		@param quelle const der zu kopierende Stapel
		@exception VollAusnahme der kopierte Stapel kann wegen Speichermangel nicht erstellt werden
	*/
	public void kopieren(final StapelListe quelle) throws VollAusnahme {
		entleeren();
		Knoten knoten = quelle.anker;
		while (knoten != null) {
			eintragen(knoten.wert);
			knoten = knoten.verbindung;
		}
	}

	/** Vergleicht den Inhalt zweier Stapel.
		const
		@param stapel const der zu vergleichende Stapel
		@return true wenn die beiden Stapel dieselben Elemente enthalten
	*/
	public boolean istGleich(final StapelListe stapel) {
		Knoten dieses = anker;
		Knoten jenes = stapel.anker;
		while (dieses != null && jenes != null) {
			if (dieses.wert != jenes.wert)
				return false;
			dieses = dieses.verbindung;
			jenes = jenes.verbindung;
		}
		return dieses == null && jenes == null;
	}

	/** Kopiert Inhalt des Stapels; rekursive Implementierung.
		@param quelle const der zu kopierende Stapel
		@exception VollAusnahme der kopierte Stapel kann wegen Speichermangel nicht erstellt werden
	*/
	public void kopierenRek(final StapelListe quelle) throws VollAusnahme {
		anker = knotenKopie(quelle.anker);
	}
	private Knoten knotenKopie(final Knoten quelle) throws VollAusnahme {
		Knoten ziel = null;
		try {
			ziel = new Knoten(quelle.wert); // throws NullPointerException, wenn quelle == null
			ziel.verbindung = knotenKopie(quelle.verbindung); // rekursiver Aufruf
		}
		catch(NullPointerException ausnahme) {} // Liste zu Ende
		catch(OutOfMemoryError ausnahme) { // kein Speicher mehr frei
			throw new VollAusnahme();
		}
		return ziel;
	}

	/** Vergleicht den Inhalt zweier Stapel; rekursive Implementierung. 
		const
		@param stapel const der zu vergleichende Stapel
		@return true wenn die beiden Stapel dieselben Elemente enthalten
	*/
	public boolean istGleichRek(final StapelListe stapel) { 
		return knotenVergleichen(anker, stapel.anker);
	}

	private boolean knotenVergleichen(final Knoten erster, final Knoten zweiter) {
		try {
			return erster.wert == zweiter.wert & // throws NullPointerException, wenn eine Referenz == null
				knotenVergleichen(erster.verbindung, zweiter.verbindung); // rekursiver Aufruf
		}
		catch(NullPointerException ausnahme) { // eine der Listen zu Ende
			return erster == null & zweiter == null; // auch die andere?
		}
	}

	// private Komponenten:
	private class Knoten { // lokale Klasse ähnlich wie im Programm (9.9)
		Object wert;
		Knoten verbindung;
		Knoten() {} // parameterloser Konstruktor (Attrappe für den Versuch in voll)
		Knoten(final Object wert) { // Konstruktor mit einem Parameter
			this.wert = wert; // verbindung == null
		}
		Knoten(final Object wert, final Knoten verbindung) { // Konstruktor mit zwei Parametern
			this.wert = wert;
			this.verbindung = verbindung;
		}
	}

	private Knoten anker = null;

	/** Testtreiber */
	public static void main(String[] args) {
		try {
			StapelListe s = new StapelListe();
			StapelListe t = new StapelListe();
			System.out.println("StapelPol Test");
			System.out.println("leer? " + s.istLeer());
			s.eintragen(new Integer(1));
			System.out.println("Nicht leer? " + s.istLeer());
			System.out.println("lesen = 1?" + s.lesen());
			s.eintragen(new Integer(2));
			System.out.println("lesen = 2?" + s.lesen());
			s.entfernen(); // 2
			System.out.println("lesen = 1?" + s.lesen());
			s.eintragen(new Integer(2));
			s.eintragen(new Integer(3));
			s.eintragen(new Integer(4));
			System.out.println("Nicht voll? " + s.istVoll());
			System.out.println("Nicht leer? " + s.istLeer());
			s.eintragen(new Integer(5));
			System.out.println("Voll? " + s.istVoll());
			System.out.println("lesen = 5?" + s.lesen());

			t.kopieren(s);
			System.out.println("Gleich? " + t.istGleich(s));
			System.out.println("Gleich? " + s.istGleich(t));
			System.out.println("lesen = 5?" + t.lesen());

			s.entfernen(); // 5
			System.out.println("lesen = 4?" + s.lesen());
			System.out.println("Nicht gleich? " + t.istGleich(s));
			System.out.println("Nicht gleich? " + s.istGleich(t));

			s.entfernen(); // 4
			s.entfernen(); // 3
			s.entfernen(); // 2
			System.out.println("lesen = 1?" + s.lesen());
			s.entfernen(); // 1
			System.out.println("Nicht voll? " + s.istVoll());
			System.out.println("leer? " + s.istLeer());
			System.out.print("Ausnahme leer? ");
			try {
				System.out.println("lesen falsch: " + s.lesen());
			} catch (LeerAusnahme voll) {
				System.out.println("Ausnahme leer");
			}
			System.out.print("Ausnahme leer? ");
			try {
				s.entfernen();
			} catch (LeerAusnahme voll) {
				System.out.println("Ausnahme leer");
			}
			System.out.println("Test abgeschlossen");
		} catch (Exception ausnahme) {
			System.out.println("Ausnahme: " + ausnahme);
		}
	}
}