Einen Stack selbst implementieren

[Cherrycoke]

Hallo Community,

als Javaanfänger komme ich mit folgender AUfgabenstellung nicht klar:

Implementieren Sie eine Klasse Stapel unter Beachtung der folgenden Vorgaben:

- Der Typ der in jedem Knoten zu speichernden Daten soll variabel sein.
- Die einzelnen Knoten werden in einer Klasse Element gespeichert:

class Element<T>
{
private T daten;
private Element<T> nachfolger;
...
}

 Die Klasse Stapel soll folgende Methoden enthalten:
– Methode ablegen(T e), die ein neues Element mit Daten e oben einfügt
– Methode T entnehmen(), die das oberste Element entfernt und die darin enthaltenen
Daten zurückgibt
– Methode boolean leer(), die zurückgibt, ob der Stapel leer ist

Beim Versuch, ein Element aus einem leeren Stapel zu entnehmen, soll eine Exception geworfen werden.

Testen Sie Ihre Implementierung mit Hilfe einer Test-Klasse.

Bisher fehlt mir der zündende Gedanke. Aus der Aufgabenstellung geht hervor, dass ich drei Dateien anlegen muss. Einmal Stapel.java. dann Element.java, und die Testklasse TestStapel.java.

Es scheitert bei mir schon an Stapel.java. Die sieht bei mir im Moment wie folgt aus:

import java.util.EmptyStackException;

public interface Stapel {
  public void ablegen(T e);
  public T entnehmen()
      throws EmptyStackException;
  public boolean leer();
}

Wie mache ich denn nun in der Klasse Element weiter?

Ich verstehe zwar, wie ein Stack aufgebaut ist (ich kann ihn in C programmieren), alelrdings weiß ich nicht, wie ich das in Java umsetzen kann. Könnte mir vielleicht jemand weiter helfen? Das wäre super!

 

[Bratkartoffel]

Hallo,

Als Element kannst du eigentlich jedes beliebige Object hernehmen (daher auch die Generics mit dem <T>), die kannst du gestalten wie du willst.

Java selbst hat schon eine Klasse Stack, welche deinen Anforderungen entsprechen sollte. Wenn du das JDK installiert hast, dann kannst dir auch den Sourcecode der Klasse anschauen, falls du nicht weiter kommst

Gruß
BK

// Edit: Hier kannst du die Java-Klasse auch anschauen: http://www.docjar.com/html/api/java/util/Stack.java.html

Wie du siehst, ist da nicht viel Code dabei und dürfte an sich von der Funktionsweise nicht groß anders als ein C++ Programm sein.

 

[Cherrycoke]

Hmm, ich mache es mir mit Java immernoch recht schwer. Ich habe mir mal die fertige Klasse angeschaut, aber ganz so schlau wurde ich daraus leider nicht. Ich will einfach nur wieder meine Pointer aus C zurück. Die fehlen mir. ;-)

Also, ich habe nun zwei Dateien. Stapel.java:

import java.util.EmptyStackException;
 
public interface Stapel {
  public void ablegen(T e);
  public T entnehmen()
      throws EmptyStackException;
  public boolean leer();
}

und Element.java:

public class Element<T>{
	private T daten;
	private Element<T> nachfolger = -1;
	
		/**
		* Konstruiert einen Stack
		*/
		public Stapel() {
	
		}
   
		/**
		* Gibt zurück ob ein Stack leer ist oder nicht
		* 
		* @return true falls der STack leer ist, false sonst.
		*/
		public boolean leer() {
	
		}
		
		
		/**
		* Gibt das zuletzt eingefügte Element im Stack zurück und entfernt dieses.
		* 
		* @return Das zuletzt eingefügte Element
		* @throws EmptyStackException Wenn der Stack leer ist.
		*/
		public T entnehmen(){
		
		}
		
		/**
		* Fügt das Element e dem Stack T zu
		*/
		public ablegen( T e ){
		
		}
	
}

Soweit bin ich nun gekommen. Beginnen wir nun bei dem Anfang meiner Probleme. Was schreibe ich denn in den Konstruktor rein?
In C habe ich einmal die Daten, einen Pointer auf den Vorgänger der Daten und einen Pointer auf den Anfang (dort wo hinzugefügt und gelöscht werden soll) des Stacks gebraucht.

Kann mir nochmal jemand helfen? Ich bin in Java leider noch nicht so fit.

P.S.
In der fertigen Java-Klasse wird als Konstruktor einfach nur super() angegeben. Was bedeutet das denn?

 

[CPoly]

Soweit bin ich nun gekommen. Beginnen wir nun bei dem Anfang meiner Probleme. Was schreibe ich denn in den Konstruktor rein?
In C habe ich einmal die Daten, einen Pointer auf den Vorgänger der Daten und einen Pointer auf den Anfang (dort wo hinzugefügt und gelöscht werden soll) des Stacks gebraucht.

Wieso ist denn Stack bei dir ein Interface? Mach daraus eine Klasse (die sollte auch generisch sein. Also Stack<T>). Dort hast du ein Datenelement vom Typ Element, welches auf das erste Element zeigt (da ist dein geliebter Pointer...). In der Klasse Element hast du wiederrum ein Datenelement von eben diesem Typ, womit du auf den Nachfolger zeigst oder auf null, wenn es das letzte Element ist.

P.S.
In der fertigen Java-Klasse wird als Konstruktor einfach nur super() angegeben. Was bedeutet das denn?

Stack erbt von Vector. Mit super wird die Instanz der Superklasse angesprochen und mit super() der Konstruktor eben dieser.

 

[Cherrycoke]

Wieso ist denn Stack bei dir ein Interface? Mach daraus eine Klasse (die sollte auch generisch sein. Also Stack<T>). Dort hast du ein Datenelement vom Typ Element, welches auf das erste Element zeigt (da ist dein geliebter Pointer...). In der Klasse Element hast du wiederrum ein Datenelement von eben diesem Typ, womit du auf den Nachfolger zeigst oder auf null, wenn es das letzte Element ist.

Seid bitte etwas nachsichtig mit mir, aber das ist alles sehr neu für mich. Ich programmiere in Java erst seit wenigen Wochen...

Wie lasse ich denn nun daten auf das erste Element zeigen?

public class Stapel<T> {
    private Element<T> daten = ?; 
}

 

[CPoly]

Da wir selbst aktuell in der Vorlesung das Collection Framework und speziell generics durchnehmen und ich eben erst ein Übungsblatt abgegeben habe, habe ich es schnell mal implementiert.

Aber tu dir selbst den gefallen und kopier es nicht einfach.

Stapel mit innere Klasse Element (wird nur innerhalb der Klasse Stapel benötigt)

import java.util.EmptyStackException;

public class Stapel<T> {
    private Element<T> first;//zeigt auf das erste Element

    Stapel() {
        first = null;//ein leerer Stack hat kein erstes Element
    }
    
    boolean empty() {
    	return first == null;
    }

    void push(T data) {
        if(first == null) {//stack ist leer
            first = new Element<T>(data);
        }
        else {
        	Element<T> el = new Element<T>(data);//neues Element
        	el.setNext(first);//das neue Element zeigt auf das erste
        	first = el;//das neue ist jetzt das erste
        }
    }
    
    T pop() {
    	if(first == null)
    		throw new EmptyStackException();
    	
    	T result = first.getData();
    	first = first.getNext();//den Zeiger umhängen auf das zweite Elemente
    	
    	return result;
    }
    
    private class Element<T> {
    	private Element<T> next;
    	private T data;

    	Element(T data, Element<T> next) {
    		this.data = data;
    		this.next = next;
    	}
    	
    	Element(T data) {
    		this(data, null);
    	}

    	public Element<T> getNext() {
    		return next;
    	}

    	public void setNext(Element<T> next) {
    		this.next = next;
    	}

    	public T getData() {
    		return data;
    	}

    	public void setData(T data) {
    		this.data = data;
    	}
    }
}

Main Klasse und Methode.

public class Main {
	public static void main(String[] args) {
		Stapel<String> stack = new Stapel<String>();
		stack.push("Bier");
		stack.push("Beer");
		stack.push("Even more Beer!");
		
		while(!stack.empty()) {
			System.out.println(stack.pop());
		}
	}
}

Die Ausgabe des Programms ist
Even more Beer!
Beer
Bier

 

[Cherrycoke]

Zuerst möchte ich einmal die Communiy hier generell loben. Hier wird wirklich immer einem freundlich geholfen. Finde ich super! Da bekomme ich schon fast ein schlechtes Gewissen, wenn man eine Frage stellt.

Aber tu dir selbst den gefallen und kopier es nicht einfach.

Ich bin eben deine Lösung Schritt für Schritt durchgegangen, und habe es danach "selbst" noch einmal programmiert. Ich denke, ich habe es nun verstanden. Am Anfang hatte ich noch eine Frage bezüglich des this.Attribut, was sich aber jetzt auch erübrigt hat.

Eine kleine Frage hätte ich noch: Kennt jemand zufällig einen guten Link, wo die Zugriffsberechtigungen (private, public, ect.) erklärt werden?

Vielen Dank!

 

[Carron]

Google hilft:
http://www.tilman.de/uni/ws03/alp/java.php

auf http://wiki.infostudium.de/wiki/Sichtbarkeit_(Java) findet sich eine Übersicht, die sich ungefähr so darstellt:

• private
  Komponente kann nur innerhalb der Klasse angesprochen werden
• kein Modifier (default bzw. package visibility)
  Komponente kann nur innerhalb des Pakets angesprochen werden
• protected
  Komponente kann nur innerhalb des Pakets angesprochen werden UND von allen erbenden Klassen
• public
  Komponente kann von überall angesprochen werden