Stacks und Generics

districon

Bekanntes Mitglied
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.
Java:
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

Top Contributor
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.
 

LimDul

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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

Top Contributor
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.
 

Blender3D

Top Contributor
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]
 

districon

Bekanntes Mitglied
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
 

districon

Bekanntes Mitglied
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?
Java:
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

Top Contributor
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

Bekanntes Mitglied
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?
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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:
Java:
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

Top Contributor
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.
 

Barista

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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.
 

White_Fox

Top Contributor
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.
 

Neue Themen


Oben