# Stack reversen ohne Java API



## districon (18. Jun 2021)

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 (18. Jun 2021)

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


----------



## districon (18. Jun 2021)

mihe7 hat gesagt.:


> 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 (18. Jun 2021)

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 (18. Jun 2021)

mihe7 hat gesagt.:


> 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 (18. Jun 2021)

```
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 (18. Jun 2021)

districon hat gesagt.:


> Ich bekomm da nen Stackoverflow Fehler


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


----------



## Barista (18. Jun 2021)

districon hat gesagt.:


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


`Stack<E> reversedStack = null;`


----------



## districon (18. Jun 2021)

```
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 (18. Jun 2021)

In Zeile 4 musst Du den neuen Stack auch vermerken.


----------



## mihe7 (18. Jun 2021)

```
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 (18. Jun 2021)

mihe7 hat gesagt.:


> ```
> public class Stack<E> {
> 
> private final E value;
> ...


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


----------



## mihe7 (18. Jun 2021)

Weil pop() next liefert.


----------



## districon (18. Jun 2021)

mihe7 hat gesagt.:


> 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 (18. Jun 2021)

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 (18. Jun 2021)

mihe7 hat gesagt.:


> 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 (18. Jun 2021)

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


----------



## districon (18. Jun 2021)

mihe7 hat gesagt.:


> 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 (18. Jun 2021)

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


----------



## districon (18. Jun 2021)

mihe7 hat gesagt.:


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


Okay jetzt hat es funktioniert


----------

