Erste Schritte Queue

ioannis_m

Mitglied
Liebe Leute,

ich setze mich im Moment auseinander mit einer bescheidenen Queue, trotzdem an einer Stelle, verstehe ich die Logik des Codes überhaupt nicht. Meine Queue


Java:
        class Queue<T> {
        private Node<T> nodeHead = null;
        private Node<T> nodeEnd = null;
        private long size = 0L;
        	 
            public void enqueue(T x) {
                Node<T> newNode = new Node<T>(x, null);
        	    if (nodeHead == null) {
        	        nodeHead = newNode;
        	    } else {
        	        nodeEnd.next = newNode;
        	    }
        	        nodeEnd = newNode;
        	        size++;
                }
        	 
            public T dequeue() throws IllegalStateException {
                if (nodeHead == null) {
        	    throw new IllegalStateException();
        	    }
        	    T head = nodeHead.element;
        	    nodeHead = nodeHead.next;
        	    size--;
        	 
        	    return head;
        	}
        	 
            public long size() {
                return size;
            }
        	 
        class Node<T> {
        Node<T> next;
        T element;
        	 
            public Node(T element, Node<T> next) {
                this.element = element;
                this.next = next;
            }
        }// ende Node
        }// ende Queue


Ich will jetzt eine neue Queue erstellen und die Funktion enqueue(T x) aufrufen, z.B. mit:

Java:
Queue <String> str = new Queue <String>();
str.enqueue("Fido");



Bis auf die Zeile

Java:
 } else {

hat der Compiler folgendes erzeugt (glaube ich):

1. Ein Queue Objekt namens str mit zwei Node<T> Referenzen die auf null zeigen.
2. Ein Node Objekt namens newNode mit einem T element Referenz, die auf "Fido" zeigt, und einem Node<T> Referenz die auf null zeigt.
3. Die Node<T> nodeHead Referenz wird auf das Objekt newNode angewiesen.

Jetzt kommt die Zeile:

Java:
nodeEnd.next = newNode;

Was passiert da genau? Habe ich immer noch ingesamt zwei Objekte, mit jeweils zwei Referenzvariablen? Wenn diese Zeile versucht das Objekt newNode der Variablen Node<T> next zuzuweisen, könnte ich nicht einfach newNode.next = newNode schreiben? Die Rekursivität im Objekt newNode macht das ganze für mich ein bisschen schwieriger nachzuvollziehen...

Für jeden Erklärungsversuch bedanke ich mich in Voraus.

ioannis
 
T

TryToHelp

Gast
Hi,

ich verstehe dein Problem nicht, dein code für die Que sieht doch gut aus, habs nicht getestet, aber der Logig nach müsste es funktionieren, verstehe deine Frage nicht, aber eine Queue ist ein Objekt in das ich Elemente einfügen kann und abarbeiten, nach dem FiFo prinziep, im gegensatz zum Stack, der LiFo arbeitet ;-)
 

TKausL

Top Contributor
Hallo,

Eine Queue ist eine LinkedList, das heißt in der Liste ist nur eine Referenz auf das Erste und das Letzte Element in der liste.
Die Elemente enthalten dann jeweils auch Referenzen auf das vorherige und das nächste Element.
Stell dir das so vor:

in der Liste ist die Referenz zu Element #1 und Element #3 gespeichert.
in Element #1 ist die referenz zu Element #2 gespeichert.
in Element #2 ist die Referenz zu Element #3 gespeichert


Wenn ein neues Elelemt dazukommt wird also im bisher LETZTEN Element (nodeEnd) die referenz zum Neuen Element vermerkt (nodeEnd.next = newNode;)

In der Liste selbst wird danach das "Letzte" element ebenfals überschrieben mit dem neu dazugekommenen Element.
 

ioannis_m

Mitglied
Hallo zusammen,

danke die schnellen Antworten. Es geht darum. Auf dem Heap gibt es in diesem Moment zwei Objekte, ein Node (newNode) mit einer Node Referenz (next), und eine Queue mit zwei Node Referenzen (nodeHead und nodeEnd). Jetzt die Zeile

Java:
nodeEnd.next = newNode;

ist eine Zuweisung des newNode Objekts. An welche Referenzvariable, wenn ich insgesamt nur drei solche habe? Ich hätte also eines der folgenden erwartet (bis hier reichen meine Java Kenntnisse):

Java:
newNode.next = newNode oder
str.nodeHead = newNode oder
str.nodeEnd = newNode

Stattdessen kommt

Java:
nodeEnd.next = newNode;

was mich komplett verwirrt...

mfg
ioannis
 

TKausL

Top Contributor
Ich hätte also eines der folgenden erwartet (bis hier reichen meine Java Kenntnisse):

Java:
newNode.next = newNode oder
str.nodeHead = newNode oder
str.nodeEnd = newNode

Stattdessen kommt

Java:
nodeEnd.next = newNode;

was mich komplett verwirrt...

mfg
ioannis

zu #1: Damit würdest du ja eine Referenz der Node in sich selbst speichern. Total nutzlos.
zu #2 und #3: was genau ist str? wenn str die eigene klasse ist sollte #3 auch noch passieren, allerdings erst nachdem newNode auch in der nodeEnd vermerkt ist.
 

ioannis_m

Mitglied
Hallo nochmal,

str ist ein Queue Objekt, auf dem ich enqueue() aufrufe (siehe mein erstes Post). Obwohl deine Antwort hilft, die eigentliche Frage ist, welche der drei Referenzen (next im newNode, nodeHead im str, oder nodeEnd im str) mit der Zeile

Java:
nodeEnd.next = newNode;

dem Objekt newNode zugewiesen wird? Nach meinem Verständnis gibt es zu diesem Zeitpunkt kein nodeEnd Objekt (geschweige eins mit einer next Referenzvariable)

mfg
ioannis
 

TKausL

Top Contributor
dem Objekt newNode zugewiesen wird? Nach meinem Verständnis gibt es zu diesem Zeitpunkt kein nodeEnd Objekt (geschweige eins mit einer next Referenzvariable)

Hatte mir letztens mal den Source einer Queue angesehen, sobald du eine neue Queue erstellst wird eine neue leere Node erstellt und in nodeEnd und nodeFirst gespeichert.
 

ioannis_m

Mitglied
Hmm, ich habe also doch mehr als zwei Objekte auf dem Heap, und zwar mindestens noch zwei, die mit

Java:
        private Node<T> nodeHead = null;
        private Node<T> nodeEnd = null;

erstellt wurden, obwohl die Referenzen auf null zeigen. Weil aber jedes Node rekursiv ein anderes Node (next) enthält, dann müsste ich auf einmal unendliche Nodes haben, was nicht stimmen kann...
 

TKausL

Top Contributor
Weil aber jedes Node rekursiv ein anderes Node (next) enthält, dann müsste ich auf einmal unendliche Nodes haben, was nicht stimmen kann...
Wie?

BTW: Habe dein Problem jetzt erst verstanden. Bin von der Standart-Queue ausgegangen, garnicht gesehen dass du ja deine Queue komplett sebst schreibst und garnicht nur ein Ausschnitt aus der normalen Queue gepostet hast...

In deinem fall stimmt es, dass beim erstellen der Queue keine Nodes in der Queue sind.
 

ioannis_m

Mitglied
Dann, glaube ich die Frage, wann das Objekt nodeEnd ertellt wird, bleibt offen ;)

Vielen Dank für deine Zeit, es ist spät, vielleicht sollten wir auf morgen verschieben?
 
T

TryToHelp

Gast
Also in deiner enque Methode hast du kein Objekt namesn str, das hattest du vorher, nun ist es Node Object vom Typ <String> (bei dir Zeile 6+7)
Java:
public void enqueue(T x) {
   Node<T> newNode = new Node<T>(x, null);
hier übergibst du deiner Que die Klasse String und das objekt str.
Ein Neuer Konoten mit Inhalt <Type> String wird erstellt und dein übergebener String str wird dem Hinzugefügt.

Ist deine Queue leer, so wird dieses neue Objekt newNode nun als der Startpunkt deiner Queue gesetzt, also als erstes Objekt (Fi) Objekt welches beim späteren deque (Fo) als erstes gelesen wird.
Ist deine Liste jedoch nicht leer, also enthält schon ein paar objekte, wird dem Aktuell letztem Objekt nodeEnd als folge Objekt das neue angehängt (bei dir Zeile 10+11)
Java:
} else {
   nodeEnd.next = newNode;
Nun wird egal ob vorher leere oder nicht leere Queue, das neue Objekt (welches zu letzt rein kam und da FIFO) als letztes Objekt in der Queue gespeichert (bei dir Zeile 13)
Java:
nodeEnd = newNode;
danach wird noch die länge hochgezählt, da ja ein neues OPbjekt hinzu kam (bei dir Zeile 14)
Java:
size++;
 
T

TryToHelp

Gast

Kurz mal den Ablauf Skiziert
 

ioannis_m

Mitglied
Ich glaube ich hab es jetzt. Beim ersten Aufruf der Funktion enqueue(), bedeudet

Java:
nodeEnd.next = newNode;

nichts, weil nodeEnd noch auf null zeigt, das macht aber nichts weil die Zeile nicht ausgeführt wird. Beim zweiten Aufruf, zeigt nodeEnd auf einen Knoten, der eine Variable namens next hat, die newNode zugewiesen wird.

Viele Grüsse und Danke an alle
ioannis
 
T

TryToHelp

Gast
Ja habe ich hier ja geschrieben ;-)

...
Ist deine Liste jedoch nicht leer, also enthält schon ein paar objekte, wird dem Aktuell letztem Objekt nodeEnd als folge Objekt das neue angehängt (bei dir Zeile 10+11)
...

deswegen hat dein Code da eine if welches man für eine überprüfung benutzt, das bedeutet so viel wie WENN DANN TUE und das darauf folgende else was soviel bedeutet WENN DAS NICHT DER FALL IST MACHE wird dann ausgeführt.
Ist deine QUEUE leer, also noch
Code:
nodeHead
gleich
Code:
null
was dann im
Code:
if
überprüft wird, wird der WENN teil des
Code:
if
ausgeführt. Ist die QUEUE dann nicht mehr leer, also der 2. aufruf, ist
Code:
nodeHead
nicht mehr gleich
Code:
null
was dann im
Code:
if
teil FALSCH liefert und somit den
Code:
else
teil aufruft und somit der im durchlauf vorher gesetzten
Code:
nodeEnd
den Pointer/Zeiger/Verweis auf das nächste Objekt
Code:
nodeEnd.next
auf das neu eingefügte Objekt
Code:
newNode
zuweist
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Queue-Datenstruktur: nach dem Elementen entfernen, das Ergebnis ist immer noch nicht optimal. Java Basics - Anfänger-Themen 3
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
N Vererbung Queue bestehend aus Superclass- und Subclass-Objekten Java Basics - Anfänger-Themen 7
B Zahlenfolge von Queue in Stack Java Basics - Anfänger-Themen 29
J Java Queue mit default Werten erstellen Java Basics - Anfänger-Themen 4
P Priority Queue Performance Java Basics - Anfänger-Themen 3
Chabub Hilfe bei Stacks und Queue Java Basics - Anfänger-Themen 2
G Stack und Queue Arbeitsblatt Java Basics - Anfänger-Themen 3
F Queue zyklisch Java Basics - Anfänger-Themen 8
D Queue vs. Stack Java Basics - Anfänger-Themen 6
L Queue mithilfe von 2 Stacks erstellen Java Basics - Anfänger-Themen 1
B Automatisierung von Jobs / @EJB Scheduler / Verhinderung, dass Queue überläuft Java Basics - Anfänger-Themen 2
A Priority Queue / Comparator Java Basics - Anfänger-Themen 6
J Queue Warteschlange Java Basics - Anfänger-Themen 3
J Liste,Queue,Stack sortieren Java Basics - Anfänger-Themen 2
Y Unendlicher Ringbuffer (Queue) Java Basics - Anfänger-Themen 49
C Stack und Queue in Aktion (Bitte Hilfe für die Klausur) Java Basics - Anfänger-Themen 7
E Stack vs Queue - Gemeinsamkeiten / Unterschiede Java Basics - Anfänger-Themen 7
H Collections StackOverflowError in einer Queue Java Basics - Anfänger-Themen 3
R Klassen Die lineare Datenstruktur Queue Java Basics - Anfänger-Themen 3
JokerBlacky Klassen Klasse Queue Klasse mit Attributen anhängen und auslesen können Java Basics - Anfänger-Themen 4
K Queue enq Fehler Java Basics - Anfänger-Themen 2
F Thread der auf eine Queue wartet, sicher beenden Java Basics - Anfänger-Themen 4
A Queue (Array) leeren Java Basics - Anfänger-Themen 1
F HTTP Get Queue Java Basics - Anfänger-Themen 7
J Queue zyklisch auslesen Java Basics - Anfänger-Themen 4
B Generische Queue programmieren Java Basics - Anfänger-Themen 5
T Priority-Queue Java Basics - Anfänger-Themen 9
S Integer/Value-Paar in Prio-Queue ohne Comparator Java Basics - Anfänger-Themen 5
P Array queue problem Java Basics - Anfänger-Themen 1
L Queue programmieren via BlueJ Java Basics - Anfänger-Themen 5
B Multithreading und eigene Queue entwickeln Java Basics - Anfänger-Themen 3
G Queue auf einer Seite löschen, andre Seite schreiben Java Basics - Anfänger-Themen 3
G Queue mit int oder float Java Basics - Anfänger-Themen 3
Q queue.remove Element trotzdem noch vorhanden. Java Basics - Anfänger-Themen 10
P Priority Queue Java Basics - Anfänger-Themen 6
M Compiler-Fehler Queue als ArrayList mit Exceptions Java Basics - Anfänger-Themen 3
S Fehler beim Auslösen des ActionListeners in Verbindung mit einer Queue Java Basics - Anfänger-Themen 5
B Queue mit Daten aus einem Stack füllen Java Basics - Anfänger-Themen 21
P Collections Queue mittels ArrayList Java Basics - Anfänger-Themen 2
T Collections Queue<? extends Number> add() offer() Java Basics - Anfänger-Themen 13
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
B Queue problem! Java Basics - Anfänger-Themen 2
R Queue abhören und Message in Browser ausgeben Java Basics - Anfänger-Themen 3
T Erstellung von Queue mit verkketten listen Java Basics - Anfänger-Themen 3
kulturfenster Stack / Queue Implementationen Java Basics - Anfänger-Themen 11
K Priority Queue - wo ist denn jetzt der Vorteil? Java Basics - Anfänger-Themen 7
W Iterator in Queue Java Basics - Anfänger-Themen 5
Q An erste Stelle in eine Queue eintragen Java Basics - Anfänger-Themen 4
H Stack und Queue Java Basics - Anfänger-Themen 6
M Threadsichere Queue in Java 1.5? Java Basics - Anfänger-Themen 2
G Int-Queue in String-Queue umwandeln Java Basics - Anfänger-Themen 5
A Queue erweitern Java Basics - Anfänger-Themen 13
P Queue, Stacks, Listen Java Basics - Anfänger-Themen 7
S Queue als Array implementiert get()? Java Basics - Anfänger-Themen 4
S Queue als verkettete Liste Java Basics - Anfänger-Themen 9
S Queue Java Basics - Anfänger-Themen 30
K Prüfen, ob Queue leer ist Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Neue Themen


Oben