Stacks und Generics

[districon]

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]

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]

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

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

 

[LimDul]

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]

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

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

 

[LimDul]

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]

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

Diese Forderung ist echt Banane.

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]

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]

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]

😉

 

[districon]

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]

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]

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]

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]

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]

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]

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]

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.

Aber mein Konstruktor is richtig?

 

[Barista]

Aber mein Konstruktor is richtig?

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

 

[districon]

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]

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

Der neue Stack verweist auf den alten.

 

[districon]

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]

Kann das so sein?

Ja. (Seufz)

 

[districon]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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 schaffenden (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.

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]

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]

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]

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.