Queue mit Zeigern

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • 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:

    Quellcode

    1. public class Element
    2. {
    3. public int value;
    4. public Element next;
    6. public void show() // Methode zum anzeigen
    7. {
    8. System.out.println("value: " + value);
    9. }
    10. }


    Die Klasse Queue:

    Quellcode

    1. public class Queue
    2. {
    3. Element TOS;
    4. int f;
    5. int[] b;
    7. public Queue()
    8. {
    9. TOS = new Element();
    10. TOS = null;
    11. f = -1;
    12. b = new int[50000];
    13. }
    15. public void enqueue(int x) // Element hinzufügen
    16. {
    17. Element h = new Element();
    18. h.value = x;
    19. h.next = TOS;
    20. TOS = h;
    22. f++;
    23. b[f] = h.value;
    24. }
    26. public void dequeue() // unterstes Element entfernen
    27. {
    28. if (TOS == null)
    29. return;
    31. TOS = TOS.next;
    32. f--;
    33. }
    35. public boolean empty() // Überprüfung ob der Queue leer ist
    36. {
    37. return (TOS == null);
    38. }
    40. public int front() // Ausgabe des untersten Wertes
    41. {
    42. return b[0];
    43. }
    45. public void show() //Queue in Konsole ausgeben
    46. {
    47. while (TOS != null)
    48. {
    49. TOS.show();
    50. TOS = TOS.next;
    51. }
    52. }
    53. }
    Alles anzeigen


    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!
    Even Homer nods! But if you really want to f*ck up you'll need a computer!

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Abi2010 ()

  • 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.

    Quellcode

    1. public void show()
    2. {
    3. while (TOS != null)
    4. {
    5. TOS.show();
    6. TOS = TOS.next;
    7. }
    8. }

    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. ;)

    Quellcode

    1. int[] b;

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

  • 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.
    Even Homer nods! But if you really want to f*ck up you'll need a computer!

  • Hier ist der Stack:

    Quellcode

    1. public class Stack
    2. {
    3. Element TOS;
    4. int f;
    5. int[] b;
    7. public Stack()
    8. {
    9. TOS = new Element();
    10. TOS = null;
    11. f = -1;
    12. b = new int[50000];
    13. }
    15. public void push(int x) // Element hinzufügen
    16. {
    17. Element h = new Element();
    18. h.value = x;
    19. h.next = TOS;
    20. TOS = h;
    22. f++;
    23. b[f] = h.value;
    24. }
    26. public void pop() // oberstes Element entfernen
    27. {
    28. if (TOS == null)
    29. return;
    31. TOS = TOS.next;
    32. f--;
    33. }
    35. public boolean empty() // Überprüfung ob der Stack leer ist
    36. {
    37. return (TOS == null);
    38. }
    40. public int top() // Anzeigen des obersten Elementes
    41. {
    42. return b[f];
    43. }
    45. public void show() // Anzeigen
    46. {
    47. while (TOS != null)
    48. {
    49. TOS.show();
    50. TOS = TOS.next;
    51. }
    52. }
    53. }
    Alles anzeigen


    Der Stack funktioniert soweit.
    Problem ist jetzt nur die dequeue Methode des Queue. Den Rest kann ich doch fast so übernehmen.
    Even Homer nods! But if you really want to f*ck up you'll need a computer!

  • 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

    Quellcode

    1. public int top()
    2. {
    3. return TOS.value;
    4. }


    außerdem:

    Quellcode

    1. TOS = new Element();
    2. 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.

  • Abi2010 schrieb:

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

    Ich meinte die deQueue()-Methode. ;)

    Abi2010 schrieb:

    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! ;)

    Abi2010 schrieb:

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

    Genau das war die Info die ich brauchte ...

    Rondrer schrieb:

    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!

    Rondrer schrieb:

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

    Quellcode

    1. public int top()
    2. {
    3. return TOS.value;
    4. }

    Besser noch:

    Quellcode

    1. public Element top()
    2. {
    3. return TOS;
    4. }


    Rondrer schrieb:

    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.

    Rondrer schrieb:

    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: [Blockierte Grafik: http://www.pmelms.de/bit/ws/pics/doppelte_listen.gif]

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Marcus Gnaß ()

  • Marcus Gnaß schrieb:


    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.

    Marcus Gnaß schrieb:


    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 ;)

  • So, endlich geschafft!

    Element:

    Quellcode

    1. public class Element
    2. {
    3. public int value;
    4. public Element next;
    6. public void show()
    7. {
    8. System.out.println("value: " + value);
    9. }
    10. }


    Stack:

    Quellcode

    1. public class Stack
    2. {
    3. Element TOS;
    5. public Stack()
    6. {
    7. TOS = new Element();
    8. }
    10. public void push(int x)
    11. {
    12. Element h = new Element();
    13. h.value = x;
    14. h.next = TOS;
    15. TOS = h;
    16. }
    18. public void pop()
    19. {
    20. if (TOS == null)
    21. return;
    23. TOS = TOS.next;
    24. }
    26. public boolean empty()
    27. {
    28. return (TOS == null);
    29. }
    31. public Element top()
    32. {
    33. return TOS;
    34. }
    36. public void show()
    37. {
    38. while (TOS != null)
    39. {
    40. TOS.show();
    41. TOS = TOS.next;
    42. }
    43. }
    44. }
    Alles anzeigen


    Queue:

    Quellcode

    1. public class Queue
    2. {
    3. private Element First;
    4. private Element Last;
    6. public Queue()
    7. {
    8. First = Last = new Element();
    9. }
    11. public void enqueue(int x)
    12. {
    13. Element h = new Element();
    14. h.value = x;
    15. Last.next = h;
    16. Last = h;
    17. }
    19. public void dequeue()
    20. {
    21. if(!empty())
    22. {
    23. First = First.next;
    24. }
    25. }
    26. public boolean empty()
    27. {
    28. return Last == First;
    29. }
    31. public Object front()
    32. {
    33. if(!empty())
    34. {
    35. return First.next.value;
    36. }
    37. return null;
    38. }
    39. }
    Alles anzeigen


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

    Danke für die Hilfe!!!!!!!!!!!!!
    Even Homer nods! But if you really want to f*ck up you'll need a computer!

  • Was hältst du denn von folgendem Code:

    Quellcode

    1. /** Ein Element.
    2. */
    3. public class Element {
    5. public int value;
    6. public Element next = null;
    8. /** Erzeugt ein Element.
    9. */
    10. public Queue(int value) {
    11. this.value = value;
    12. }
    14. /** Gibt den Wert eines Elementes auf der Konsole aus.
    15. */
    16. public void show() {
    17. System.out.println("value: " + value);
    18. }
    20. }
    22. /** Eine Queue.
    23. */
    24. public class Queue {
    26. private Element firstElement;
    27. private Element lastElement;
    29. /** Erzeugt eine Queue.
    30. */
    31. public Queue() {
    32. firstElement = lastElement = null;
    33. }
    35. /** Prüft ob die Queue Elemente enthält.
    36. */
    37. public boolean empty() {
    38. return lastElement == null && firstElement == null;
    39. }
    41. /** Fügt ein Element der Queue hinzu.
    42. */
    43. public void enqueue(Element element) {
    44. element.next = firstElement;
    45. firstElement = element;
    46. if (null==lastElement)
    47. lastElement = element;
    48. }
    50. /** Fügt einen Wert der Queue hinzu.
    51. */
    52. public void enqueue(int x) {
    53. enqueue(new Element(x));
    54. }
    56. /** Entfernt das älteste Element der Queue und gibt dieses zurück.
    57. */
    58. public Object dequeue() {
    59. Element element = null;
    60. if (!empty()) {
    61. element = firstElement;
    62. firstElement = element.next;
    63. if (null==firstElement)
    64. lastElement = null;
    65. }
    66. return element;
    67. }
    69. /** Gibt das älteste Element der Queue zurück ohne dieses zu entfernen.
    70. */
    71. public Object front() {
    72. Element element = null;
    73. if (!empty())
    74. element = firstElement;
    75. return element;
    76. }
    78. }
    Alles anzeigen