Stack - listenbasierte Implementierung

[cartier]

Hallo zusammen

Ich habe von meinem Dozenten folgende Aufgabe erhalten und komme leider nicht weiter. Ein Teil des Codes habe ich probiert zu programmieren. Aufgabe:

Betrachten Sie das folgende Klassengerüst:

import java.util.NoSuchElementException;
//SimpleStack Datenstruktur besteht aus einem data-Eintrag und einem Verweis auf 
//  den rest, eine Datenstruktur vom gleichen Typ
public class SimpleStack {
   private SimpleStack rest = null;
   private Object data;

   public SimpleStack(){}

   private SimpleStack( Object data, SimpleStack rest ){
      this.rest=rest; this.data=data;
   }
   void push( Object data ){
      rest = new SimpleStack( data, rest );
   }
   Object pop(){
      if( rest==null ) throw new NoSuchElementException();
      Object rc = rest.data;
      rest=rest.rest;
      return rc;
   }

Ergänzen Sie diese Klasse um die fehlenden Stack-Methoden, sowie um eine Methode
public String toString()
so dass ein Stack s nach s.push("Hallo"); s.push("Berlin"); s.push("Salut"); System.out.println( s );
den folgenden Output liefert:
(Salut, Hallo, Berlin) oder alternativ: (Salut (Hallo (Berlin))) oder alternativ : (Salut (Hallo (Berlin())))

Mein Versuch habe ich anhand von einigen Übungsfolien so programmiert (leider bin ich wirklich noch ein grosser Anfänger in Java und weiss überhaupt nicht wie weiter machen):

//Erste klasse:

publicinterface Stack {


    void push(Object o);


    Object peek();


    Object pop();


    boolean isEmpty();
//Zweite Klasse

publicclass MyStack implements Stack  {
private Object[] oA = new Object [1];
privateintpos = 0;
public static void main (String[] args){
Stack s = new MyStack();
System.out.println("Stack leer:" + s.isEmpty() );
s.push("Berlin");
System.out.println( s.peek() );
s.push("Hallo");
System.out.println( s.peek() ); 
s.push( "Salut" );
System.out.println( "Stack schirttweise leeren..."); 
System.out.println("Stack leer:" + s.isEmpty() ); 
while( !s.isEmpty())
System.out.println( s.pop());
}


public void push (Object o) {
if ( pos == oA.length){
Object[] oATemp = new Object [2* oA.length ]; //1
for (int i = 0; i < oA.length; i++) { //2
oATemp[i] = oA [i];
oA = oATemp; // 3
}
}
oA[ pos++] = o;
}


public Object peek(){
return oA[pos-1];
}


public Object pop () {
return oA[ --pos ];
}


publicboolean isEmpty(){
return pos == 0;
}
}
//dritte klasse

publicclass YourStack implements Stack {


    @Override
    public void push(Object o) {
        // TODO Auto-generated method stub


    }


    @Override
    public Object peek() {
        // TODO Auto-generated method stub
        returnnull;
    }


    @Override
    public Object pop() {
        if ([U]rest[/U]==null) throw new [U]NoSuchElementException[/U]();
        returnnull;
    }


    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        returnfalse;
    }


}
}

Kann mir jemand weiterhelfen?

LG

 

[Flown]

Musst du jetzt das Grundgerüst das du als erstes gepostet hast verwenden oder mit Arrays arbeiten?
Stell doch den ganzen Übungszettel online!

 

[cartier]

Ich muss das Grundgerüst weiter ausbauen, das ich am Anfang gepostet habe. Die Aufgabenstellung wie mein Dozent sie gestellt hat, ist oben genau so hingeschrieben. Der untere Code ist von mir irgendwie zusammengebaut worden.

LG

 

[Flown]

Habt ihr was mit Generics schon gemacht?

 

[Flown]

Egal ich zeig dir jetzt mal den Ansatz (mit Generics erweitert):

Falls dein Interface so aussieht:

public interface MyStack<T> {

  void push(T o);
  T peek();
  T pop();
  boolean isEmpty();
}

Dann muss deine Implementierung dementsprechend so aussehen:

class SimpleStack<T> implements MyStack<T> {

  private SimpleStack<T> rest = null;
  private T data;

  public SimpleStack() {
  }

  private SimpleStack(T data, SimpleStack rest) {
    this.rest = rest;
    this.data = data;
  }

  @Override
  public void push(T data) {
    rest = new SimpleStack(data, rest);
  }

  @Override
  public T pop() {
    if (rest == null) {
      throw new NoSuchElementException();
    }
    T rc = rest.data;
    rest = rest.rest;
    return rc;
  }

  @Override
  public T peek() {
    // Gib das oberste Element zurück -> siehe wie das bei pop funktioniert mit rc ... da muss nichts am rest geändert werden
  }

  @Override
  public boolean isEmpty() {
    // Ist wahr wenn rest was ist?
  }

  @Override
  public String toString() {
    // Kann man auf mehrere Arten implementieren: Bei Rekursion -> Wenn isEmpty() gib "()" zurück sonst Klammer auf data und dann rest.toString und Klammer zu
    // Mit Schleife ist das noch einfacher for(SimpleStack<T> s = rest; !s.isEmpty(); s = s.rest) { // String zusammensetzen }
  }
}

Bei weiteren Fragen her damit... Musst aber bis morgen warten.