# Stacks und Generics



## districon (15. Jun 2021)

Hallo,
ich komme bei einer Methode nicht weiter. Ich soll einen Stapel implementieren, jedoch keine Klassen aus der API verwenden. Die Methode push soll ein Element an den Stack anhängen. Jedoch weiß ich nicht genau wie ich das tun soll. Einfach den Operator "+" verwenden funktioniert nicht.

```
public class Stack<E> {

    private E e;
    private Stack<E> stack;

    private Stack(Stack<E> stack) {
        this.stack = stack;
    }

    private static <E> Stack<E> create() {
        return null;
    }
    private static <E> Stack<E> push(Stack<E> a, E e) {

    }
```


----------



## Barista (15. Jun 2021)

districon hat gesagt.:


> public class Stack<E> { private Stack<E> stack;


Du willst den Stack mit Hilfe des Stack implementieren.

Nun ja, Münchhausen hat sich angeblich auch an den eigenen Haaren aus dem Sumpf gezogen.

Wenn Du keine Klasse aus dem Java API verwenden darfst, fallen die java.util-Collections weg.

Darfst Du Arrays verwenden?

Wenn ja, dann das Array in der Stack-Klasse kapseln und dynamisch vergrößern.

Wenn nein, dann kannst Du den Stack nach dem Prinzip einer einfachen linked List aufbauen.

Ist eigentlich sogar eleganter.


----------



## Barista (15. Jun 2021)

districon hat gesagt.:


> private static <E> Stack<E> create()


Diese Methode würde ich weglassen, es sei denn, es ist explizit eine Factory gefordert oder notwendig.


----------



## LimDul (15. Jun 2021)

Der Code sieht Banane aus. Eine Klasse X, die im Konstrktor ein Element der Klasse X benötigt? Wie willst du den Konstruktor jemals aufrufen.

Das Static sieht auch komplett falsch aus - warum soll die Methode push static sein? Das ist nicht sinnvoll.

Als erstes:
* Die Instanzvariablen wegwerfen, insbesondere stack
* Dir überlegen (Auf einem Blatt Papier oder ähnlichen) wie speicherst du Elemente in einem Stack, wenn du nur Karteikarten hast. Ich gehe mal davon aus, dass ihr eine LinkedList schon mal gebaut habt - ein Stack ist ähnlich.

Dann - und dann erst - anfangen Code zu schreiben


----------



## districon (15. Jun 2021)

LimDul hat gesagt.:


> Der Code sieht Banane aus. Eine Klasse X, die im Konstrktor ein Element der Klasse X benötigt? Wie willst du den Konstruktor jemals aufrufen.
> 
> Das Static sieht auch komplett falsch aus - warum soll die Methode push static sein? Das ist nicht sinnvoll.
> 
> ...


Alle Methoden müssen static sein und ich muss zwei Klassenvariablen haben. Einmal vom Typ Stack und vom generischen Typ E


----------



## LimDul (15. Jun 2021)

districon hat gesagt.:


> Alle Methoden müssen static sein und ich muss zwei Klassenvariablen haben. Einmal vom Typ Stack und vom generischen Typ E


Gut, das erste ist Weltfremd, aber sei es drum.

Die zweite Anforderung ist nicht unerwartet. Aber bevor du Code schreibst, überleg dir mal, wie du damit mit Karteikarten einen vollständigen Stack aufbauen kannst. Jede Karteikarte ist ein Objekt vom Typ "Stack", auf der du zwei Dinge notieren kannst: Einen Wert und die Adresse einer weiteren Karteikarte. Wie könnte man damit einen Stack modellieren?


----------



## Barista (15. Jun 2021)

districon hat gesagt.:


> Alle Methoden müssen static sein und ich muss zwei Klassenvariablen haben.


Diese Forderung ist echt Banane.


districon hat gesagt.:


> und ich muss zwei Klassenvariablen haben. Einmal vom Typ Stack und vom generischen Typ E


Das legt die implizite Forderung nach einer single linked list nahe.

Das Feld 'stack' ist eigentlich 'next'.

Begonnen wird in create mit null, einer leeren linked list.

next == null bedeutet, dass die linked list endet.


----------



## Barista (15. Jun 2021)

Barista hat gesagt.:


> Diese Forderung ist echt Banane.


Zumindest ist dies kein Java-Stil sondern C-Stil.

Euer Tutor hat im letzten Jahrtausend C gelernt und seitdem das Lernen abgeschaltet.


----------



## Blender3D (15. Jun 2021)

districon hat gesagt.:


> Jedoch weiß ich nicht genau wie ich das tun soll. Einfach den Operator "+" verwenden funktioniert nicht.


Du könntest so etwas machen.
[CODE lang="java" title="MyStack"]public class MyStack<T> {
    private static final int EMPTY = -1;
    private Object[] data;
    private int pos = EMPTY;

    public MyStack(int size) {
        data = new Object[size];
    }

    public boolean isEmpty() {
        return pos == EMPTY;
    }

    public boolean isFull() {
        return pos == data.length - 1;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty())
            throw new IllegalAccessError("Empty stack pop!");
        return (T) data[pos--];
    }

    public void push(T e) {
        if (isFull())
            throw new IllegalAccessError("Full stack push!");
        data[++pos] = e;
    }
}
[/CODE]
[CODE lang="java" title="TestStack"]public class TestStack {
    public static void main(String[] args) {       
        MyStack<String> stack = new MyStack<String>(5);
        String []values = {"Peter","Susi","Paul","Huber"};
        for(String s: values)
            stack.push(s);
        while( !stack.isEmpty() )
            System.out.println(stack.pop());
    }
}[/CODE]


----------



## Blender3D (15. Jun 2021)

😉


----------



## districon (17. Jun 2021)

LimDul hat gesagt.:


> Gut, das erste ist Weltfremd, aber sei es drum.
> 
> Die zweite Anforderung ist nicht unerwartet. Aber bevor du Code schreibst, überleg dir mal, wie du damit mit Karteikarten einen vollständigen Stack aufbauen kannst. Jede Karteikarte ist ein Objekt vom Typ "Stack", auf der du zwei Dinge notieren kannst: Einen Wert und die Adresse einer weiteren Karteikarte. Wie könnte man damit einen Stack modellieren?


Das heißt ich muss in meinem Konstruktor zwei Variablen haben. Einmal für den aktuellen Wert und einen für die Adresse des nächsten Stacks


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> Das heißt ich muss in meinem Konstruktor zwei Variablen haben. Einmal für den aktuellen Wert und einen für die Adresse des nächsten Stacks


Du meinst sicher "zwei Parameter" um zwei Felder zu setzen.

Ansonsten ja.


----------



## districon (17. Jun 2021)

Barista hat gesagt.:


> Du meinst sicher "zwei Parameter" um zwei Felder zu setzen.
> 
> Ansonsten ja.


Also ist Stack mein next und <E> ist mein Wert an der Stelle oder?


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> Also ist Stack mein next und <E> ist mein Wert an der Stelle oder?


Ja.

Deine Frage hat sicher den Hintergrund, dass Du unsicher bist, wie eine single linked list funktioniert.

Die Suchmaschine Deines Vertrauens wird Dir helfen.


----------



## districon (17. Jun 2021)

Barista hat gesagt.:


> Ja.
> 
> Deine Frage hat sicher den Hintergrund, dass Du unsicher bist, wie eine single linked list funktioniert.
> 
> Die Suchmaschine Deines Vertrauens wird Dir helfen.




```
private Stack(E current, Stack next) {
        this.e = current;
        this.stack = next;
    }
```

Also wäre das der Konstruktor?


----------



## districon (17. Jun 2021)

LimDul hat gesagt.:


> Gut, das erste ist Weltfremd, aber sei es drum.
> 
> Die zweite Anforderung ist nicht unerwartet. Aber bevor du Code schreibst, überleg dir mal, wie du damit mit Karteikarten einen vollständigen Stack aufbauen kannst. Jede Karteikarte ist ein Objekt vom Typ "Stack", auf der du zwei Dinge notieren kannst: Einen Wert und die Adresse einer weiteren Karteikarte. Wie könnte man damit einen Stack modellieren?




```
public class Stack<E> {

    private E value;
    private Stack stack;

    private Stack(E value, Stack next) {
        this.value = value;
        this.stack = next;
    }
```

So ähnlich? Aber es muss doch ein head Element geben, welches Null ist


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> So ähnlich? Aber es muss doch ein head Element geben, welches Null ist


Nein.

null heisst leere Liste bzw. wenn das Feld stack (besser next) null ist, gibt es keine nächste Liste.

Der head ist nur bei leerer Liste null, sonst nicht null.

Angehängt wird am Anfang, nicht am Ende.

Nun ja, das ist anders als bei einer _single linked list_, das ist eine _immutable single linked list_.


----------



## districon (17. Jun 2021)

Barista hat gesagt.:


> Nein.
> 
> null heisst leere Liste bzw. wenn das Feld stack (besser next) null ist, gibt es keine nächste Liste.
> 
> ...


Aber mein Konstruktor is richtig?


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> Aber mein Konstruktor is richtig?


Ja. (Hast Du irgendwas von dem, was ich gepostet habe verstanden?)


----------



## districon (17. Jun 2021)

Barista hat gesagt.:


> Ja. (Hast Du irgendwas von dem, was ich gepostet habe verstanden?)


Ja. Ich muss beim alten Stack quasi auf das neue verweisen, welches ich einfügen will


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> Ich muss beim alten Stack quasi auf das neue verweisen, welches ich einfügen will


Der neue Stack verweist auf den alten.


----------



## districon (17. Jun 2021)

Barista hat gesagt.:


> Der neue Stack verweist auf den alten.




```
private static <E> Stack<E> push(Stack<E> a, E e) {
        Stack<E> erg = new Stack<E>(e,a);
        return erg;
    }
```
Kann das so sein?


----------



## Barista (17. Jun 2021)

districon hat gesagt.:


> Kann das so sein?


Ja. (Seufz)


----------



## districon (18. Jun 2021)

Barista hat gesagt.:


> Ja. (Seufz)


Und wenn ich jetzt das oberste Element löschen will, muss ich auf das vorletze Element zugreifen und den "Zeiger" auf null setzen. Aber ich weiß garnicht wie ich da jetzt drauf zugreifen soll


----------



## kneitzel (18. Jun 2021)

Du nimmst Dir eine Referenz und setzt diese so lange auf den Nachfolger, bis du beim vorletzten Element angekommen bist. Was dies im Detail bedeutet kannst Du Dir ja in Ruhe überlegen. Am Besten malst Du es Dir einfach einmal auf (z.B. mit Referenzen als Pfeil).


----------



## districon (18. Jun 2021)

kneitzel hat gesagt.:


> Du nimmst Dir eine Referenz und setzt diese so lange auf den Nachfolger, bis du beim vorletzten Element angekommen bist. Was dies im Detail bedeutet kannst Du Dir ja in Ruhe überlegen. Am Besten malst Du es Dir einfach einmal auf (z.B. mit Referenzen als Pfeil).


Mmh, das verstehe ich nicht ganz


----------



## districon (18. Jun 2021)

kneitzel hat gesagt.:


> Du nimmst Dir eine Referenz und setzt diese so lange auf den Nachfolger, bis du beim vorletzten Element angekommen bist. Was dies im Detail bedeutet kannst Du Dir ja in Ruhe überlegen. Am Besten malst Du es Dir einfach einmal auf (z.B. mit Referenzen als Pfeil).


Ich weiß dass ich irgendwie next zurückgeben muss:

```
public class Stack<E> {

    private E value;
    private Stack<E> next;

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

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


----------



## Barista (19. Jun 2021)

districon hat gesagt.:


> Und wenn ich jetzt das oberste Element löschen will, muss ich auf das vorletze Element zugreifen und den "Zeiger" auf null setzen. Aber ich weiß garnicht wie ich da jetzt drauf zugreifen soll


Der Stack (lokale Variable oder Feld) ist dann einfach der vorletzte Stack.
Der Stack (aktueller head) ist dann einfach nicht mehr erreichbar und der Garbage Collector kümmert sich drum.


----------



## districon (19. Jun 2021)

Barista hat gesagt.:


> Der Stack (lokale Variable oder Feld) ist dann einfach der vorletzte Stack.
> Der Stack (aktueller head) ist dann einfach nicht mehr erreichbar und der Garbage Collector kümmert sich drum.


Der Stack funktioniert jetzt. Ich habe jedoch ein weiteres Problem. Lässt sich mit diesem Stack allein eine Queue umsetzen?


----------



## Blender3D (19. Jun 2021)

districon hat gesagt.:


> Der Stack funktioniert jetzt. Ich habe jedoch ein weiteres Problem. Lässt sich mit diesem Stack allein eine Queue umsetzen?


Macht nicht wirklich Sinn.
Stack arbeitet nach dem FILO Prinzip (First In Last Out) 
Queue arbeitet nach dem FIFO Prinzip (First In First Out)


----------



## districon (19. Jun 2021)

Blender3D hat gesagt.:


> Macht nicht wirklich Sinn.
> Stack arbeitet nach dem FILO Prinzip (First In Last Out)
> Queue arbeitet nach dem FIFO Prinzip (First In First Out)


Ja, aber das ist in der Aufgabenstellung so gefordert, leider...


----------



## Barista (19. Jun 2021)

districon hat gesagt.:


> Lässt sich mit diesem Stack allein eine Queue umsetzen?


Prinzipiell kann man Vieles machen.

Vielleicht nicht aus Linux ein Windows programmieren, aber Stack und Queue sind sich nicht so fremd.

Erst mal würde ich den ganzen Code in eine andere Klasse, ein anderes Package oder Projekt kopieren.

Wenn in der zu schaffenden (zu konstruierenden) Queue am Kopf eingefügt werden soll, dann muss sicher am Ende entnommen werden.

Also eine Methode take, die das letzte Element sucht und zurückgibt und den letzten(ersten) Stack am vorletzten(zweiten) Stack abschneidet (null zuweist).

Natürlich mit Behandlung der üblichen Sonderfälle, leerer Stack und Stack der Grösse 1.


----------



## districon (19. Jun 2021)

Barista hat gesagt.:


> Prinzipiell kann man Vieles machen.
> 
> Vielleicht nicht aus Linux ein Windows programmieren, aber Stack und Queue sind sich nicht so fremd.
> 
> ...


Wenn ich z.B. die Methode front implementieren will, die mir das erst eingefügte Element gibt, dann habe ich ein Problem. Ich hab als Attribut ja nur Stack<E> (darf keine weiteren Attribute deklarieren). Für ein einzelnes Element bräuchte ich ja ein einzelnes <E>


----------



## Barista (19. Jun 2021)

districon hat gesagt.:


> Wenn ich z.B. die Methode front implementieren will, die mir das erst eingefügte Element gibt, dann habe ich ein Problem. Ich hab als Attribut ja nur Stack<E> (darf keine weiteren Attribute deklarieren). Für ein einzelnes Element bräuchte ich ja ein einzelnes <E>


Du musst entweder den private Modifier am Feld stack entfernen, oder eine entsprechende get-Methode schreiben.
Damit kannst Du vom head zum jeweiligen next laufen.
Tut mir leid, dass meine Sichtweise (head und next) anders ist als Deine (Dir vorgegeben) front.
Du musst meine Aussagen eben entsprechend für Dich übersetzen.


----------



## mrBrown (19. Jun 2021)

districon hat gesagt.:


> Ja, aber das ist in der Aufgabenstellung so gefordert, leider...


Wie sieht denn die genaue Aufgabenstellung aus?

Den Stack umschreiben zu einer Queue oder eine Queue schreiben, die intern Stacks nutzt?


----------



## White_Fox (19. Jun 2021)

Ich denke, eine einfache Lösung könnte etwas Dekoratorartiges sein. Damit kommst du sogar ohne Array aus (was die Sache einfacher macht).

Einfach mal nach "Dekorator Entwurfsmuster" suchen...da solltest du etwas Passendes finden.


----------

