Schlange Datenstruktur

[bRainLaG]

Hiho ich versuchs mal erneut da ich mein Problem nun scheinbar besser im Griff habe bzw es besser erklären kann.

Zuerst mein Java Code:

public class Queue {
	
	int i = 0;
	cell next = null;
	String content = "";
	
	class cell {
		
		cell next = null;
		String content = "";

		public cell (String content) {
				this.content = content; 
		}
		public cell getNext(){
			return next;
		}
		public void setNext(cell next){
			this.next = next;
		}
		public String toString() {
			String returnvalue = "";
			returnvalue += content;
			if (this.next != null) {
				returnvalue += next;
			}
			
			return returnvalue;
		}
	}
	
	public void appendElement(cell e){
		while (next != null){
			next.getNext();
		}
			next.setNext(e);
			i = i+1;
	}

	public void insertElement(cell e){
		
	}
}

Implementieren soll ich eine Schlange, bei der ein Element vorne inserted werden kann, am ende angehängt werden kann und gelöscht werden kann.
Was mir noch nicht einleuchtet ist, wie kann ich ohne direkten Pointer in Java den Kopf festlegen, und wie ich nur mit der Next-Refferenz auf das nächste Element die insert und remove Operation geregelt kriege. Wäre für Hilfe echt dankbar, da sich mir das nicht wirklich erschließt.

Um meinen Quelltext zu kommentieren etwas. Ich habe in die innere Klasse cell hereingeschrieben, das jedes Element immer auf das folgende verweisen soll und außerdem das diese "Zellen" strings enthalten.
Des weiteren habe ich i deklariert damit ich mir auch noch die Länge meiner Schlange ausgeben lassen kann. Bei der append Funktion bin ich so vor gegangen das ich gesagt habe solange der next nicht 0 ist, soll er weiterlaufen, wenn dieser 0 ist soll er das Element hinten ran schreiben.

 

[faetzminator]

Wenn [c]next == null[/c], dann kann man [c]next[/c] auf [c]e[/c] setzen, ansonsten Methode auf [c]next[/c] aufrufen. Btw, Klassen schreibt man CamelCase mit fürendem Grossbuchstaben (Methoden und Variablen (nicht static) mit führendem Kleinbuchstaben).

 

[bRainLaG]

aber wenn ich sage das next == 0 sein muss da inserte ich doch nicht weil ich beim inserten davor schreiben muss da muss doch next != 0 sein oder?

 

[faetzminator]

[c]0[/c] ist nicht [c]null[/c]. Wenn das Objekt null ist, dann hast du das Ende des Schwanzes erreicht... So meine ich es:

public void insertElement(Cell e){
    if (next == null) {
        next = e;
    } else {
        next.insertElement(e);
    }
}

 

[bRainLaG]

mir schon klar aber ich möchte ja mit insert erreichen, dass mein e vor das erste element gesetzt wird und nicht an das letzte gehängt wird.

Das heißt ich müsste vorher den Kopf der Schlange festlegen diesen dann durch e ersetzen und einen neuen Verweis auf das nun zweite vorher erste Element machen.
Nur wie ich das Codetechnisch mache weiß ich eben nicht

 

[faetzminator]

Ist in [c]next[/c] in Queue der erste Eintrag? Wenn ja, wieso heisst dieser nicht [c]first[/c]? Aber grundsätzlich musst du es so machen:

e.setNext(Queue.this.next);
Queue.this.next = e;

 

[bRainLaG]

Naja ich hab es deswegen next genannt, da ich ansonsten in meiner append funktion das next sonst nicht nutzen kann, da ich nicht genau weiß warum er in queue das next aus Cell nicht kennt.

Kannste das was du geschrieben hast ganz kurz kommentieren vieleicht wäre super

*edit*

hab mal bisschen was angepasst noch wäre für feedback sehr dankbar ob das so richtig ist.

in der Klasse Cell hinzugefügt:

Cell first = null;


		public Cell getFirst(){
			return first;
		}
		public Cell setFirst(Cell first){
			return this.first = first;

in der Queue hinzugefügt:

	public void insertElement(Cell e){
		while (first != null ){
			e.setNext(Queue.this.first);
			Queue.this.first = e;
		}
			first = e;
	}

hab ich mir so gedacht, das wenn schon ein element enthalten ist, also first != 0 dann mache dieses Element zum Nachfolger, und setzte das erste Element = e also dem einzufügenden ELement.

 

[faetzminator]

In der ersten Zeile hängst du an das neue (erste) Element das nächste, also das momentan erste. Danach musst du das neue natürlich noch als erstes setzen.

 

[bRainLaG]

naja ich hab es jetzt so gemacht, dass ich deine annahme genommen hab, aber nochmal extra für das erste Element eine implementierung vorgenommen habe kann ich das auch so machen?

 

[faetzminator]

Natürlich kannst du das. Ich würde auf die Schnelle so was erstellen:

public class Queue<T> {

    private Node first;
    
    public Node getFirst() {
        return first;
    }
    
    public void insert(Node node) {
        node.next = first;
        first = node;
    }
    
    public void append(Node node) {
        if (first == null) {
            first = node;
        } else {
            Node n = first;
            while (n.next != null) {
                n = n.next;
            }
            n.next = node;
        }
    }
    
    public void removeFirst() {
        if (first != null) {
            first = first.next;
        }
    }
    
    public void removeLast() {
        if (first != null) {
            if (first.next == null) {
                first = null;
            }
            Node n = first;
            while (n.next.next != null) {
                n = n.next;
            }
            n.next = null;
        }
    }
    
    public class Node {
        
        private Node next;
        private T data;
        
        public Node(T data) {
            this.data = data;
        }
        
        public T getData() {
            return data;
        }
        
        public Node getNext() {
            return next;
        }
    }
}

Anstatt der Rekursion beim Handling mit dem letzten Element habe ich eine Iteration implementiert. So kriegt man bei grösseren Queues keine SOE's.

 

[bRainLaG]

danke dir vielmals ein interesse hab ich allerdings noch.

Wenn ich die Funktionen nun in der Main-Methode aufrufen will wie kann ich das tuen also nehme wir an ich will mit Insert ein Element e1 einsetzen?

 

[faetzminator]

Du musst natürlich zuerst eine Queue haben.

Queue<String> queue = new Queue<String>();
queue.insert(e1); // dein e1
queue.insert(queue.new Node("foo")); // sonst noch irgendeine Node

Edit: natürlich funktioniert das mit deiner "cell" genau so, einfach ohne Generics (du erwartest immer String als Content).

 

[bRainLaG]

Du musst natürlich zuerst eine Queue haben.

Queue<String> queue = new Queue<String>();
queue.insert(e1); // dein e1
queue.insert(queue.new Node("foo")); // sonst noch irgendeine Node

Edit: natürlich funktioniert das mit deiner "cell" genau so, einfach ohne Generics (du erwartest immer String als Content).

grml ich hasse fehlende syntax kenntnisse

also was beim 2. passiert ist klar einfügen des elements
auch 3. ist mir klar da ich dazu den Knoten noch einfüge
nur die erste Zeile versteh ich nicht wirklich.

 

[faetzminator]

Es wird eine neue Instanz von Queue erzeugt und in der lokalen Variable queue, welche ebenfalls dort deklariert wird, abgespeichert. Mit den Generics gebe ich an, dass die Daten in einer Node vom Typ String sein müssen (in den Klassen Node und Queue stellvertretend als T).

 

[bRainLaG]

    	Cell e1 = new String("Dies ");

    	Queue<String> queue = new Queue<String>();
    	queue.insertElement(e1);
    	queue.insertElement(queue.new Cell("foo")); // sonst noch irgendeine Node
    }
}

hab bei e1 nun das problem das dies als statisches Element nicht zu einer nicht statischen Klasse Cell zugeordnet werden kann

 

[bRainLaG]

hat nicht zufällig jemand noch ne ahnung wie ich die Elemente syntaktisch richtig deklariere wär super

 

[faetzminator]

Da Cell eine Inner Class von Queue ist, muss auf eine Instanz von Queue eine neue Cell erstellt werden.

Queue<String> queue = new Queue<String>(); // zuerst die benötigte Queue erstellen
Cell e1 = queue.new Cell("Dies "); // Dann deine Zelle mit dem String "Dies "
queue.insertElement(e1); // hinzufügen