You are not logged in.

  • Login

Queue mit Zeigern

Abi2010

Trainee

  • "Abi2010" started this thread

Posts: 12

  • Send private message

1

Wednesday, January 28th 2009, 1:20am

Queue mit Zeigern

Hallo
ich wurd krankheitsbedingt in Info zurückgeworfen und hab deshalb ne Menge verpasst. Hab deshalb mein kleines Problem bei dieser Aufgabe: Programmiere einen Queue mit Hilfe einer Klasse Elements und Zeigern. Am Anfang dacht ich erst was ist denn hier los, aber ich habs wenigstens geschafft einen Stack hinzubiegen. Bei der dequeue-Methode des Queues häng ich allerdings fest!

Die Klasse Elements:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10

public class Element
{
    public int value;
    public Element next;
 
    public void show()    // Methode zum anzeigen
    {
        System.out.println("value: " + value);
    }
}


Die Klasse Queue:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class Queue
{
    Element TOS;
    int f;
    int[] b;
 
    public Queue()
    {
        TOS = new Element();
        TOS = null;
        f = -1;
        b = new int[50000];
    }
 
    public void enqueue(int x)          // Element hinzufügen
    {
        Element h = new Element();
        h.value = x;
        h.next = TOS;
        TOS = h;
 
        f++;
        b[f] = h.value;
    }
 
    public void dequeue()   // unterstes Element entfernen
    {
        if (TOS == null)
            return;
 
        TOS = TOS.next;
        f--;
    }
 
    public boolean empty()    // Überprüfung ob der Queue leer ist
    {
        return (TOS == null);
    }
 
    public int front()   // Ausgabe des untersten Wertes
    {
        return b[0];
    }
 
    public void show()   //Queue in Konsole ausgeben
    {   
        while (TOS != null)
        {
            TOS.show();
            TOS = TOS.next;
        }
    }
}


Bisher ist das nur der leicht veränderte Quelltext vom Stack (TOS = Top of Stack).
front hab ich schon angepasst, nur dequeue macht mir Probleme...
Ansonsten dürfte das doch funktionieren, oder?

Ein wenig Hilfe bei dequeue wär nicht schlecht. Bitte!

This post has been edited 1 times, last edit by "Abi2010" (Jan 28th 2009, 2:36pm)

Marcus Gnaß

Professional

Posts: 217

  • Send private message

2

Wednesday, January 28th 2009, 12:57pm

Was soll diese Methode denn machen? Alle Elemente ins Nirvana schicken? Ein Element an einer bestimmten Position ausklinken? Alle Elemente mit einem bestimmten Wert rausschmeißen? Hier wäre vieles denkbar.

Java Quellcode

 
1
2
3
4
5
6
7
8

public void show()
    {   
        while (TOS != null)
        {
            TOS.show();
            TOS = TOS.next;
        }
    }

Bist du dir sicher, daß du hier deine Variable TOS verändern willst? Ich glaube nicht, oder? Zudem sollten alle Variablen und Eigenschaften mit einem kleinen Buchstaben beginnen, also tOS oder besser tos, vielleicht aber auch topOfStack. Zudem solltest du dir angewöhnen deinen Code zu kommentieren. Dann weißt du auch übermorgen noch was für eine geniale Idee du hattest. ;)

Java Quellcode

 
1

int[] b;

Wofür brauchts du das Array? Du hast doch bereits alle Werte in deiner Queue!

Abi2010

Trainee

  • "Abi2010" started this thread

Posts: 12

  • Send private message

3

Wednesday, January 28th 2009, 2:29pm

Meinst du jetzt die show oder die dequeue Methode? Ich denke mal show...
show soll mir die Werte in einer Konsole ausgeben was beim Stack funktionierte. Einziges Manko war, dass nach dem Ausführen von show der Stack unbrauchbar wurde. Is aber nicht schlimm.
dequeue soll halt das unterste Element entfernen (also das welches als erstes hinzugefügt wurde).

Das Array ist noch ein Überbleibsel vom Stack. Dadurch wurde die top Methode recht kurz.

Abi2010

Trainee

  • "Abi2010" started this thread

Posts: 12

  • Send private message

4

Wednesday, January 28th 2009, 2:38pm

Hier ist der Stack:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class Stack
{
    Element TOS;
    int f;
    int[] b;
 
    public Stack()
    {
        TOS = new Element();
        TOS = null;
        f = -1;
        b = new int[50000];
    }
 
    public void push(int x)   // Element hinzufügen
    {
        Element h = new Element();
        h.value = x;
        h.next = TOS;
        TOS = h;
 
        f++;
        b[f] = h.value;
    }
 
    public void pop()   // oberstes Element entfernen
    {
        if (TOS == null)
            return;
 
        TOS = TOS.next;
        f--;
    }
 
    public boolean empty()   // Überprüfung ob der Stack leer ist
    {
        return (TOS == null);
    }
 
    public int top()   // Anzeigen des obersten Elementes
    {
        return b[f];
    }
 
    public void show()   // Anzeigen
    {   
        while (TOS != null)
        {
            TOS.show();
            TOS = TOS.next;
        }
    }
}


Der Stack funktioniert soweit.
Problem ist jetzt nur die dequeue Methode des Queue. Den Rest kann ich doch fast so übernehmen.

Rondrer

Professional

Posts: 306

  • Send private message

5

Wednesday, January 28th 2009, 3:27pm

also erstmal find ich das Array unnötig und Speicherintensiv. Dazu setzt es eine wiilkürliche Grenze wie groß ein Stack (oder Queue) werden kann. Die top() Methode lässt sich doch auch ohne relativ einfach implementieren

Java Quellcode

 
1
2
3
4

public int top()
    {
        return TOS.value;
    }


außerdem:

Java Quellcode

 
1
2

TOS = new Element();
TOS = null;

die erste Zeile im Konstruktor ist komplett überflüssig. Du erzeugst ein Element und löschst es quasi direkt wieder, weil du jede Referenz zu diesem Objekt entfernst (und damit ist es Futter für den Garbage-Collector). Die Zeile kannst du dir somit auch sparen.

Allgemein sollte man aus objektorienterter sicht nicht direkt auf die Atribute eines Objektes zugreifen (können). Das sollte über get/set Methoden geschehen. Aber vieleicht habt ihr das noch nicht gelernt, oder sollt es so machen, spielt jetzt eigentlich nicht so die große Rolle.

So, jetzt zu deiner eigentlichen Frage:
Wenn du die dequeue() Funktion zu deiner Queue, so wie sie im Moment ist, implementieren willst, müsstest du erstmal durch alle Elemente durchiterieren um den Anfang der Queue zu finden. Das ist auch kein großes Problem, nur ein wenig unschön.
Ich würde an deiner Stelle noch einen Zeiger auf das erste Element in der Queue erzeugen um den Anfang einfach finden zu können. Allerdings müsstest du dann auch die "Speicher-Richtung" der Elemente ändern: Im Moment kennt jedes Element seinen Vorgänger, in einer Queue wäre es aber sinnvoller wenn jedes Element seinen Nachfolger kennen würde. Sonst kann man das erste Element nicht entfernen, weil man nicht weiß was das 2. Element ist, auf den ja der Anfangs-Zeiger nach dem entfernen des 1. Elementes zeigen muss.

Marcus Gnaß

Professional

Posts: 217

  • Send private message

6

Thursday, January 29th 2009, 11:00am

Quoted from "Abi2010"

Meinst du jetzt die show oder die dequeue Methode? Ich denke mal show...

Ich meinte die deQueue()-Methode. ;)

Quoted from "Abi2010"

show soll mir die Werte in einer Konsole ausgeben was beim Stack funktionierte. Einziges Manko war, dass nach dem Ausführen von show der Stack unbrauchbar wurde. Is aber nicht schlimm.

Doch! Damit hast du dann nämlich eine Art EinwegQueue entwickelt! ;)

Quoted from "Abi2010"

dequeue soll halt das unterste Element entfernen (also das welches als erstes hinzugefügt wurde).

Genau das war die Info die ich brauchte ...

Quoted from "Rondrer"

also erstmal find ich das Array unnötig und Speicherintensiv. Dazu setzt es eine wiilkürliche Grenze wie groß ein Stack (oder Queue) werden kann.

Völlig richtig, also raus damit!

Quoted from "Rondrer"

Die top() Methode lässt sich doch auch ohne relativ einfach implementieren

Java Quellcode

 
1
2
3
4

public int top()
    {
        return TOS.value;
    }

Besser noch:

Java Quellcode

 
1
2
3
4

public Element top()
    {
        return TOS;
    }


Quoted from "Rondrer"

Allgemein sollte man aus objektorienterter sicht nicht direkt auf die Atribute eines Objektes zugreifen (können). Das sollte über get/set Methoden geschehen.

So nicht ganz richtig. Es gibt Szenarien in denen Getter & Setter sinnvoll, sogar zwingend sind, so z.B. bei Beans. Diese Anforderung generell zu stellen ist aber nicht nötig. Die Java API ist voll von Klassen mit Attributen ohne Getter oder Setter.

Quoted from "Rondrer"

Sonst kann man das erste Element nicht entfernen, weil man nicht weiß was das 2. Element ist, auf den ja der Anfangs-Zeiger nach dem entfernen des 1. Elementes zeigen muss.

Kann man schon, aber eben nur mit Iterieren. Aus Performance-Gründen ist eine doppelt verkettete Liste absolut sinnvoll. Zur Veranschaulichung:

This post has been edited 1 times, last edit by "Marcus Gnaß" (Jan 29th 2009, 11:15am)

Rondrer

Professional

Posts: 306

  • Send private message

7

Thursday, January 29th 2009, 9:59pm

Quoted from "Marcus Gnaß"


Kann man schon, aber eben nur mit Iterieren. Aus Performance-Gründen ist eine doppelt verkettete Liste absolut sinnvoll.

Find ich für ne Queue unnötig, da man idR NUR auf das unterste (bzw erste) element zugreift... Dafür ist es ja ne Queue und keine Liste ;) Wobei es bis auf ein wenig mehr Speicher natürlich nicht schadet.

Quoted from "Marcus Gnaß"


So nicht ganz richtig. Es gibt Szenarien in denen Getter & Setter sinnvoll, sogar zwingend sind, so z.B. bei Beans. Diese Anforderung generell zu stellen ist aber nicht nötig. Die Java API ist voll von Klassen mit Attributen ohne Getter oder Setter.

Ich halte die Datenkapselung schon für sehr wichtig. Insbesondere für datenhaltende Klassen, wie wohl auch die hier verwendete. Denn was passiert, wenn du irgendwann auf die Idee kommst, die Daten intern auf ne andere weiße zu speichern? Du müsstest dann auch alle Klassen ändern, die in irgendeinerweise die geänderte Klasse "benutzen" ändern. Wenn die Daten aber gekapselt sind, muss man nur die Getter/Setter ändern und muss sich über die anderen Klassen keine Sorgen machen.
Außerdem reicht es zum verwenden der Klasse die Methodenrümpfe zu kennen, und man muss nicht wissen wie intern die Attribute heißen. Das sind jetzt nur 2 Gründe, es gibt natürlich noch mehr .
Aber letztendlich ist es wohl ne Glaubensfrage, ich bleib auf jedenfall bei der streng gekapselten Datenhaltung ;)

Marcus Gnaß

Professional

Posts: 217

  • Send private message

8

Friday, January 30th 2009, 7:24am

OK, überzeugt! ;)

Abi2010

Trainee

  • "Abi2010" started this thread

Posts: 12

  • Send private message

9

Monday, February 2nd 2009, 5:47pm

So, endlich geschafft!

Element:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10

public class Element
{
   public int value;
   public Element next;
 
   public void show()
  {
    System.out.println("value: " + value);
  }
}


Stack:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Stack
{
    Element TOS;
 
    public Stack()
    {
        TOS = new Element();
    }
 
    public void push(int x)
    {
        Element h = new Element();
        h.value = x;
        h.next = TOS;
        TOS = h;
    }
 
    public void pop()
    {
        if (TOS == null)
            return;
 
        TOS = TOS.next;
    }
 
    public boolean empty()
    {
        return (TOS == null);
    }
 
    public Element top()
    {
        return TOS;
    }
 
    public void show()
    {   
        while (TOS != null)
        {
            TOS.show();
            TOS = TOS.next;
        }
    }
}


Queue:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class Queue
{
    private Element First;
    private Element Last;
 
    public Queue()
    {
        First = Last = new Element();
    }
 
    public void enqueue(int x)
    {        
        Element h = new Element();
        h.value = x;
        Last.next = h;
        Last = h;
    }
 
    public void dequeue()
    {
        if(!empty())
        {
            First = First.next;
        }
    }
    public boolean empty()
    {
        return Last == First;
    }
 
    public Object front()
    {
        if(!empty())
        {
            return First.next.value;
        }
        return null;
    }
}


Das funktioniert!!!
Jetzt muss ich das Gleiche nur noch mit einem "Dictionary" machen...

Danke für die Hilfe!!!!!!!!!!!!!

Marcus Gnaß

Professional

Posts: 217

  • Send private message

10

Tuesday, February 3rd 2009, 11:55am

Was hältst du denn von folgendem Code:

Java Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/** Ein Element.
 */
public class Element {
 
	public int value;
	public Element next = null;
 
	/** Erzeugt ein Element.
	 */	
	public Queue(int value) {
		this.value = value;
	}
 
	/** Gibt den Wert eines Elementes auf der Konsole aus.
	 */	
	public void show() {
		System.out.println("value: " + value);
	}
 
}
 
/** Eine Queue.
 */
public class Queue {
 
	private Element firstElement;
	private Element lastElement;
 
	/** Erzeugt eine Queue.
	 */	
	public Queue() {
		firstElement = lastElement = null;
	}
 
	/** Prüft ob die Queue Elemente enthält.
	 */	
	public boolean empty() {
		return lastElement == null && firstElement == null;
	}
 
	/** Fügt ein Element der Queue hinzu.
	 */	
	public void enqueue(Element element) {        
		element.next = firstElement;
		firstElement = element;
		if (null==lastElement)
			lastElement = element;
	}
 
	/** Fügt einen Wert der Queue hinzu.
	 */	
	public void enqueue(int x) {        
		enqueue(new Element(x));
	}
 
	/** Entfernt das älteste Element der Queue und gibt dieses zurück.
	 */	
	public Object dequeue() {
		Element element = null;
		if (!empty()) {
			element = firstElement;
			firstElement = element.next;
			if (null==firstElement)
				lastElement = null;
		}
		return element;
	}
 
	/** Gibt das älteste Element der Queue zurück ohne dieses zu entfernen.
	 */	
	public Object front() {
		Element element = null;
		if (!empty())
			element = firstElement;
		return element;
	}
 
}

Abi2010

Trainee

  • "Abi2010" started this thread

Posts: 12

  • Send private message

11

Tuesday, February 3rd 2009, 11:21pm

Mmmmm... Is auch ne Variante.
Zur Bewertung hab ich aber meine genommen. Die tats ja auch. ;-)

Setz mich jetzt demnächst ans Dictionary. Hoffe, dass das ohne größere Probleme abläuft.

Nochmals Danke für die ganzen Tips!

Similar threads

Tagging

Social bookmarks