Stack reversen ohne Java API

[districon]

Hallo,
ich möchte eine Methode schreiben um einen Stack zu reversen. Leider funktioniert mein Code noch nicht ganz:

public class Stack<E> {

    private final E value;
    private final Stack<E> next;

    private Stack(E value, Stack<E> next) {
        this.value = value;
        this.next = next;
    }

    public static <E> Stack<E> create() {
        return null;
    }
    public static <E> Stack<E> push(Stack<E> a, E e) {
        Stack<E> erg = new Stack<E>(e,a);
        return erg;
    }

    public static <E> Stack<E> pop(Stack<E> a) { //pop(push(s,e) = s
        if (a == null) {
            return Stack.<E>create();
        }
        else if (a.value == null){
            return Stack.<E>create();
        }
        else {
            return a.next;
        }
    }
    public static <E> E top(Stack<E> a) {
        if (a == null) {
            return null;
        }
        else if (a.value == null){
            return null;
        }
        else {
            return a.value;
        }
    }
    public static <E> boolean isEmpty(Stack<E> a) {
        if (a == null) {
            return true;
        }
        else if (a.value == null) {
            return true;
        }
        else {
            return false;
        }
    }
    public static <E> Stack<E> reverse(Stack<E> s) {
        Stack<E> top = Stack.<E>pop(s);
        if (Stack.<E>isEmpty(s)) {
            return top;
        } else {
            Stack<E> bottom = reverse(s);
            Stack.<E>push(top, null);
            return bottom;
        }
    }
}

Was ist in der reverse Methode falsch?

 

[mihe7]

Zeile 58 gibt jetzt nicht wirklich viel Sinn, oder? Du hast bottom, pusht null in top und gibst dann bottom zurück.

 

[districon]

Zeile 58 gibt jetzt nicht wirklich viel Sinn, oder? Du hast bottom, pusht null in top und gibst dann bottom zurück.

Wie könnte man es dann machen? While Schleife solange bis isEmpty == true und dann immer eins poppen und auf einen neuen Stack pushen?

 

[mihe7]

top ist ja nicht leer, hat also ein Element, das Du mit Stack<E>.top(top); ermitteln kannst. Und, wenn diese unerträgliche Hitze mein Hirn nicht ganz weichgekocht hat, dann sollte es doch genügen, dieses Element auf bottom zu pushen.

 

[districon]

top ist ja nicht leer, hat also ein Element, das Du mit Stack<E>.top(top); ermitteln kannst. Und, wenn diese unerträgliche Hitze mein Hirn nicht ganz weichgekocht hat, dann sollte es doch genügen, dieses Element auf bottom zu pushen.

Ich bekomm da nen Stackoverflow Fehler

 

[districon]

public static <E> Stack<E> reverse(Stack<E> s) {
        Stack<E> reversedStack = new Stack<E>(null, null);
        while(!Stack.<E>isEmpty(s)) {
            Stack.<E>push(reversedStack, s.value);
            s = Stack.<E>pop(s);
        }
        return reversedStack;
    }

Ich hab mich jetzt dafür entschieden. Leider kommt da auch noch nicht ganz mein gewünschtes Ergebnis raus. Es returnt null, obwohl es ein String sein sollte

 

[mihe7]

Ich bekomm da nen Stackoverflow Fehler

Ach, da stimmt ja gar nix in der Methode. Moment.

 

[Barista]

Stack<E> reversedStack = new Stack<E>(null, null);

Stack<E> reversedStack = null;

 

[districon]

public static <E> Stack<E> reverse(Stack<E> s) {
        Stack<E> reversedStack = new Stack<E>(null, null);
        while(!Stack.<E>isEmpty(s)) {
            reversedStack = Stack.<E>push(reversedStack, s.value);
            s = Stack.<E>pop(s);
        }
        return reversedStack;
    }

So funktionierts

 

[Barista]

In Zeile 4 musst Du den neuen Stack auch vermerken.

 

[mihe7]

public class Stack<E> {

    private final E value;
    private final Stack<E> next;

    private Stack(E value, Stack<E> next) {
        this.value = value;
        this.next = next;
    }

    public static <E> Stack<E> create() {
        return null;
    }
    public static <E> Stack<E> push(Stack<E> a, E e) {
        Stack<E> erg = new Stack<E>(e,a);
        return erg;
    }

    public static <E> Stack<E> pop(Stack<E> a) { //pop(push(s,e) = s
        if (a == null) {
            return Stack.<E>create();
        }
        else if (a.value == null){
            return Stack.<E>create();
        }
        else {
            return a.next;
        }
    }
    public static <E> E top(Stack<E> a) {
        if (a == null) {
            return null;
        }
        else if (a.value == null){
            return null;
        }
        else {
            return a.value;
        }
    }
    public static <E> boolean isEmpty(Stack<E> a) {
        if (a == null) {
            return true;
        }
        else if (a.value == null) {
            return true;
        }
        else {
            return false;
        }
    }
    public static <E> Stack<E> reverse(Stack<E> s) {
        if (Stack.<E>isEmpty(s)) {
            return s;
        }

        Stack<E> remaining = Stack.<E>pop(s);
        if (Stack.<E>isEmpty(remaining)) {
            return s;
        } else {
            E top = Stack.<E>top(s);
            Stack<E> reversed = Stack.<E>reverse(remaining);
            reversed = Stack.<E>push(reversed, top);
            return reversed;
        }
    }

    public static <E> void print(Stack<E> s) {
        Stack<E> remaining = s;
        while (!Stack.<E>isEmpty(remaining)) {
            System.out.println(Stack.<E>top(remaining));
            remaining = Stack.<E>pop(remaining);
        }
    }

    public static void main(String[] args) {
        Stack<String> stack = Stack.<String>create();
        for (int i = 0; i < 10; i++) {
            stack = Stack.<String>push(stack, Integer.toString(i+1));
        }
        Stack.<String>print(stack);

        Stack<String> reversed = Stack.<String>reverse(stack);
        System.out.println("Reversed");
        Stack.<String>print(reversed);
    }
}

 

[districon]

public class Stack<E> {

    private final E value;
    private final Stack<E> next;

    private Stack(E value, Stack<E> next) {
        this.value = value;
        this.next = next;
    }

    public static <E> Stack<E> create() {
        return null;
    }
    public static <E> Stack<E> push(Stack<E> a, E e) {
        Stack<E> erg = new Stack<E>(e,a);
        return erg;
    }

    public static <E> Stack<E> pop(Stack<E> a) { //pop(push(s,e) = s
        if (a == null) {
            return Stack.<E>create();
        }
        else if (a.value == null){
            return Stack.<E>create();
        }
        else {
            return a.next;
        }
    }
    public static <E> E top(Stack<E> a) {
        if (a == null) {
            return null;
        }
        else if (a.value == null){
            return null;
        }
        else {
            return a.value;
        }
    }
    public static <E> boolean isEmpty(Stack<E> a) {
        if (a == null) {
            return true;
        }
        else if (a.value == null) {
            return true;
        }
        else {
            return false;
        }
    }
    public static <E> Stack<E> reverse(Stack<E> s) {
        if (Stack.<E>isEmpty(s)) {
            return s;
        }

        Stack<E> remaining = Stack.<E>pop(s);
        if (Stack.<E>isEmpty(remaining)) {
            return s;
        } else {
            E top = Stack.<E>top(s);
            Stack<E> reversed = Stack.<E>reverse(remaining);
            reversed = Stack.<E>push(reversed, top);
            return reversed;
        }
    }

    public static <E> void print(Stack<E> s) {
        Stack<E> remaining = s;
        while (!Stack.<E>isEmpty(remaining)) {
            System.out.println(Stack.<E>top(remaining));
            remaining = Stack.<E>pop(remaining);
        }
    }

    public static void main(String[] args) {
        Stack<String> stack = Stack.<String>create();
        for (int i = 0; i < 10; i++) {
            stack = Stack.<String>push(stack, Integer.toString(i+1));
        }
        Stack.<String>print(stack);

        Stack<String> reversed = Stack.<String>reverse(stack);
        System.out.println("Reversed");
        Stack.<String>print(reversed);
    }
}

Warum kommt bei meinem pop null raus, wenn ich das ausführe: Stack.push(null, "JohnDoe") ?
Das verstehe ich nicht ganz

 

[mihe7]

Weil pop() next liefert.

 

[districon]

Weil pop() next liefert.

Das wurde mir so erklärt, das ich das so machen soll. Pop soll das Oberste Objekt entfernten und den Reststack zurückliefern

 

[mihe7]

Das kann durchaus sein. Es geht darum: wenn Du einen Stack derart initialisierst, dass next null ist, dann wundert es nicht, wenn pop() null liefert.

 

[districon]

Das kann durchaus sein. Es geht darum: wenn Du einen Stack derart initialisierst, dass next null ist, dann wundert es nicht, wenn pop() null liefert.

Das ist aber so vorgegeben als Testfall. Ich kann daran nichts ändern

 

[mihe7]

Dann musst Du halt dafür sorgen, dass bei Übergabe von null, next nicht einfach auf null gesetzt wird...

 

[districon]

Dann musst Du halt dafür sorgen, dass bei Übergabe von null, next nicht einfach auf null gesetzt wird...

Aber es handelt sich ja dann um einen leeren Stack und in der Aufgabe steht, dass man null als Aktualparameter für das erste Argument wie einen leeren Stack behandeln soll

 

[mihe7]

Alternativ kannst Du bei pop() auch prüfen, ob next null ist und dann einen leeren Stack zurückgeben.

 

[districon]

Alternativ kannst Du bei pop() auch prüfen, ob next null ist und dann einen leeren Stack zurückgeben.

Okay jetzt hat es funktioniert