Unendlicher Ringbuffer (Queue)

[yascod]

Hallo Miteinander,

ich versuche gerade eine Aufgabe für die Uni zu lösen. Am besten Stelle ich die Komplette Aufgabe mal hier rein, dann wisst ihr bescheid was ich lösen muss.


Ich habe schon die Klasse QueueImpl programmiert und komme nicht weiter bei der Aufgabe a) wo ich die Methode push für die Klasse RingImpl machen muss. Leider verstehe ich nicht ganz was ein unendlicher Ringpuffer sein soll (Den normalen Ringpuffer verstehe ich). Außerdem wie soll ich denn die Objekte überprüfen ob sie schon im Ringpuffer drinnen sind für die Methode push? Ich würde mich um eure Hilfe freuen. Wenn ihr möchtet kann ich meinen Code zur QueueImpl noch posten, vielleicht wird es dadurch verständlicher (Sie funktioniert zumindest).

 

[mihe7]

Leider verstehe ich nicht ganz was ein unendlicher Ringpuffer sein soll

Was an der Erklärung in der Aufgabenstellung hast Du nicht verstanden?

Außerdem wie soll ich denn die Objekte überprüfen ob sie schon im Ringpuffer drinnen sind für die Methode push?

Beispielsweise könntest Du über die Elemente im Ringpuffer iterieren und mit dem einzufügenden Element vergleichen.

 

[yascod]

Was an der Erklärung in der Aufgabenstellung hast Du nicht verstanden?


Beispielsweise könntest Du über die Elemente im Ringpuffer iterieren und mit dem einzufügenden Element vergleichen.

Das mit "unendlich" verstehe ich nicht ganz. Muss das alles in einer endlos Schleife laufen? Hatte bevor ich hier gepostet habe, in google mal gesucht. Alle Codes die ich gefunden habe basieren auf den normalen ringpuffer und es wurde zum Beispiel in den Methoden einfügen so gemacht, dass eine if Bedingung vorhanden ist die überprüft ob der ringbuffer voll ist. Da hier aber unendlich fällt das ja weg..

Und iterieren könnte ich mit einer foreach Schleife richtig? Wie müsste der Inhalt in den klammern aussehen?

 

[mihe7]

Der endliche Ringpuffer kann eine maximale Zahl an Elementen aufnehmen. Dies lässt sich sehr einfach mit einem Array implementieren, z. B. Object buf = new Object[10];

Der unendliche Rinpuffer hat keine fixe Größe, sondern wächst mit den Elementen einfach mit. Daher fällt die von Dir genannte Prüfung, ob der Ringpuffer voll ist, weg. Hierzu könnte man z. B. eine java.util.List-Implementierung verwenden - vermutlich sollt ihr das aber selbst implementieren.

Und iterieren könnte ich mit einer foreach Schleife richtig? Wie müsste der Inhalt in den klammern aussehen?

Ob Du das mit einem foreach-Konstrukt machen kannst, hängt von den von Dir verwendeten Datenstrukturen ab. Wenn Du foreach verwenden kannst:

public boolean contains(Object o) {
    for (Object elem : buffer) {
        if (elem.equals(o)) { // **
            return true;
        }
    }
    return false;
}

(** der Vergleich könnte theoretisch auch mit o == elem erfolgen, je nachdem, ob nur das selbe Objekt nicht doppelt eingefügt werden darf oder ob dies auch für gleiche Objekte gilt)

 

[yascod]

Der endliche Ringpuffer kann eine maximale Zahl an Elementen aufnehmen. Dies lässt sich sehr einfach mit einem Array implementieren, z. B. Object buf = new Object[10];

Der unendliche Rinpuffer hat keine fixe Größe, sondern wächst mit den Elementen einfach mit. Daher fällt die von Dir genannte Prüfung, ob der Ringpuffer voll ist, weg. Hierzu könnte man z. B. eine java.util.List-Implementierung verwenden - vermutlich sollt ihr das aber selbst implementieren.



Ob Du das mit einem foreach-Konstrukt machen kannst, hängt von den von Dir verwendeten Datenstrukturen ab. Wenn Du foreach verwenden kannst:

public boolean contains(Object o) {
    for (Object elem : buffer) {
        if (elem.equals(o)) { // **
            return true;
        }
    }
    return false;
}

(** der Vergleich könnte theoretisch auch mit o == elem erfolgen, je nachdem, ob nur das selbe Objekt nicht doppelt eingefügt werden darf oder ob dies auch für gleiche Objekte gilt)

Bei QueueImpl benutze ich die ArrayList kann ich die unendlichkeit damit machen?

hier mein Code zur QueueImpl:

import java.util.ArrayList;

@SuppressWarnings("serial")
public class QueueImpl extends ArrayList<Object> {
    int pos = 0;

    public void enqueue(Object item){
            add(pos, item);
            pos++;
    }

    public Object dequeue() throws QueueIsEmptyException {
        if (this.isEmpty()) {
            throw new QueueIsEmptyException("Queue ist leer");
        } else {
            if (pos > 0)
                pos--;
            return remove(0);
        }
    }

    public Object front() throws QueueIsEmptyException {
        if (this.isEmpty()) {
            throw new QueueIsEmptyException("Queue ist leer");
        } else {
            Object o = dequeue();
            add(0, o);
            pos++;
            return o;
        }
    }

    public boolean isEmpty() {
        return (pos == 0);
    }
}

Ich habe die Methode contains mal übernommen nur muss ich jetzt wie gesagt eine unendliche Liste zu Verfügung stellen am besten über QueueImpl, vielleicht da eine idee mit ArrayList? Und vielen vielen Dank für die schnellen Antworten.

 

[mihe7]

Bei QueueImpl benutze ich die ArrayList kann ich die unendlichkeit damit machen?

Vergiss mal einen Moment den Ringpuffer.

Wenn Du ein Array hast, ist die Zahl der Elemente fix. Wenn Du ein Array mit 10 Elementen erzeugst, kannst Du in dieses Array keine 11 Elemente einfügen. Das Array ist also endlich.

Bei einer List hingegen ist das Hinzufügen der Elemente praktisch unbeschränkt. Du fängst mit einer leeren Liste an und fügst einfach eins nach dem anderen hinzu. Die Liste wird nie voll. Die Liste ist also "unendlich".

Eine ArrayList ist eine List, die zur Verwaltung der "unendlich vielen" Elemente endliche Arrays verwendet. Davon bekommst Du nach außen nichts mit. Intern kann das z. B. so realisiert werden, dass das aktuell verwendete Array ggf. durch ein neues Array mit größerer Kapazität ersetzt wird.

Ich habe die Methode contains mal übernommen nur muss ich jetzt wie gesagt eine unendliche Liste zu Verfügung stellen am besten über QueueImpl, vielleicht da eine idee mit ArrayList?

Die QueueImpl erweitert ArrayList, d. h. QueueImpl ist eine ArrayList" und damit bereits eine "unendliche Liste".

Das List-Interface bietet bereits contains an, da QueueImpl eine ArrayList ist, kannst Du einfach auf das bereits vorhandene contains zurückgreifen.

Vielleicht mal ein wenig Code als Startpunkt; ist natürlich nicht vollständig.

public class RingImpl {
    private QueueImpl queue = new QueueImpl();
    private int pos;

    public boolean contains(Object o) { return queue.contains(o); }
    public void push(Object o) { queue.add(pos, o); }
    public Object actual() { return queue.get(pos); }
    public void next() { pos = (pos + 1) % size(); }
    public boolean isEmpty() { return queue.isEmpty(); }
    public Object pop() { return queue.remove(pos); }
}

 

[yascod]

Vergiss mal einen Moment den Ringpuffer.
Die QueueImpl erweitert ArrayList, d. h. QueueImpl ist eine ArrayList" und damit bereits eine "unendliche Liste".

Das List-Interface bietet bereits contains an, da QueueImpl eine ArrayList ist, kannst Du einfach auf das bereits vorhandene contains zurückgreifen.

Vielleicht mal ein wenig Code als Startpunkt; ist natürlich nicht vollständig.

public class RingImpl {
    private QueueImpl queue = new QueueImpl();
    private int pos;

    public boolean contains(Object o) { return queue.contains(o); }
    public void push(Object o) { queue.add(pos, o); }
    public Object actual() { return queue.get(pos); }
    public void next() { pos = (pos + 1) % size(); }
    public boolean isEmpty() { return queue.isEmpty(); }
    public Object pop() { return queue.remove(pos); }
}

Ich habe aber kein contains in QueueImpl. Ich habe jetzt in QueueImpl eine

ArrayList<Object> buffer;

eingefügt. Und ich habe ja schon ein int pos = 0 in QueueImpl, ist es also noch nötig die int pos in die RingImpl reinzuschreiben? Ich habe hier mal weiter gemacht, weiß aber nicht genau ob mein push, pop und next richtig ist bzw. fällt dir vielleicht was anderes auf?

public class RingImpl extends QueueImpl {
    private QueueImpl queue = new QueueImpl();
    private int pos;

  
    public boolean contains(Object index){
        for (Object elem : buffer) {
            if (elem.equals(index)) {
                return true;
            }
        }
        return false;
    }
  
  
    public void push(Object index) throws QueueIsEmptyException {
        if (this.isEmpty()) {
            throw new QueueIsEmptyException("Ringbuffer ist leer");
        } else {
            if (!contains(index)) {
            queue.enqueue(index);
            }
        }
    }

    public Object pop() throws QueueIsEmptyException {
        if (queue.isEmpty()) {
            throw new QueueIsEmptyException("Ringbuffer ist leer");
        } else {
            Object index = queue.dequeue();
            return index;
        }

    }

    public Object actual() throws QueueIsEmptyException {
        if (queue.isEmpty()) {
            throw new QueueIsEmptyException("Stack ist leer");
        } else {
            return queue.front();
        }
    }

     public void next() {
         queue.pos = (queue.pos + 1) % size();
       
     }
  
    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) throws QueueIsEmptyException {

    }
}

 

[yascod]

Hab es mal in der Main getestet funktioniert nicht . Nullpointer Exception bei der Methode contains und der pusht auch gar nix rein, ich mache irgendwas an den Objekten falsch, glaube ich zumindest.

 

[Xyz1]

Ich bringe mal etwas Licht hier rein.
Ein "unendlicher" Ringpuffer kann auch ein Array mit fester Länge sein, das nicht vergrößert wird.

Am besten Stelle ich die Komplette Aufgabe mal hier rein, dann wisst ihr bescheid was ich lösen muss.

Das ist schön aber gleichzeitig so mies zu erkennen das Du Dir das auch sparen hättest können.

 

[yascod]

Ich bringe mal etwas Licht hier rein.
Ein "unendlicher" Ringpuffer kann auch ein Array mit fester Länge sein, das nicht vergrößert wird.


Das ist schön aber gleichzeitig so mies zu erkennen das Du Dir das auch sparen hättest können.

Wenn das jetzt wegen der Qualität gemeint ist auf dem PC ist es leserlich genug, sollte eigentlich keinen Problem darstellen.

 

[Xyz1]

Hääääää???? Verstehst Du nicht was ich sagte? Die Qualität ist unter aller sau das kannst Du behalten.

 

[mihe7]

Ich habe aber kein contains in QueueImpl.

Nochmal: QueueImpl erweitert ArrayList, damit erbt QueryImpl die contains-Methode von ArrayList.

Und ich habe ja schon ein int pos = 0 in QueueImpl, ist es also noch nötig die int pos in die RingImpl reinzuschreiben?

Ja. Das eine ist die Position, die zur Verwaltung der Queue benötigt wird, das andere die Position für den Ringpuffer. Du kannst das Feld aber gerne umbenennen:

public class RingImpl {
    private QueueImpl queue = new QueueImpl();
    private int pointer;

    public boolean contains(Object o) { return queue.contains(o); }
    public void push(Object o) { queue.add(pointer, o); }
    public Object actual() { return queue.get(pointer); }
    public void next() { pointer = (pointer + 1) % size(); }
    public boolean isEmpty() { return queue.isEmpty(); }
    public Object pop() { return queue.remove(pointer); }
}

Ich habe es nicht getestet, aber für die meisten Fälle sollte diese Implementierung funktionieren, die Sonderfälle solltest Du aber schon noch selbst behandeln.

 

[mihe7]

Und gleich noch einen hinterher:

public class RingImpl extends QueueImpl {

Das Erweitern von QueueImpl widerspricht der Anforderung lt. Aufgabenstellung, dass RingImpl ein Objekt der Klasse QueueImpl aggregieren soll.

 

[yascod]

Hääääää???? Verstehst Du nicht was ich sagte? Die Qualität ist unter aller sau das kannst Du behalten.
Manchmal denke ich ich rede mit einem Toastbrot....

Dann wird es mal Zeit eine Brille zu benutzen, deine Hilfe und Kommentare kannst du dir sparen du "Foren-Gangster"! Und zum Toastbrot würde ich jetzt noch was sagen aber hey ich kann wohl besser denken als du, ist es nicht wert

 

[yascod]

Nochmal: QueueImpl erweitert ArrayList, damit erbt QueryImpl die contains-Methode von ArrayList.



Ja. Das eine ist die Position, die zur Verwaltung der Queue benötigt wird, das andere die Position für den Ringpuffer. Du kannst das Feld aber gerne umbenennen:

public class RingImpl {
    private QueueImpl queue = new QueueImpl();
    private int pointer;

    public boolean contains(Object o) { return queue.contains(o); }
    public void push(Object o) { queue.add(pointer, o); }
    public Object actual() { return queue.get(pointer); }
    public void next() { pointer = (pointer + 1) % size(); }
    public boolean isEmpty() { return queue.isEmpty(); }
    public Object pop() { return queue.remove(pointer); }
}

Ich habe es nicht getestet, aber für die meisten Fälle sollte diese Implementierung funktionieren, die Sonderfälle solltest Du aber schon noch selbst behandeln.

Hey danke für die Hilfe ich schaue mir das nochmal an und melde mich. Vielen Dank für deine Hilfe und Verständnis!

 

[Xyz1]

Ich find es immer gut zu sehen wie jemand denkt er sei besser als ich.

Dann wird es mal Zeit eine Brille zu benutzen, deine Hilfe und Kommentare kannst du dir sparen

Gern.

 

[Thallius]

Ich finde ein unendlicher Ring buffer ist irgendwie en paradoxum. Ein Ring buffer ist immer unendlich das sagt ja schon der Name...

 

[yascod]

Ich find es immer gut zu sehen wie jemand denkt er sei besser als ich.


Gern.

Brauchst du eine Bestätigung dafür? Oder musst du dir das jedes Mal dir selber beweisen, dass du besser als andere bist? Ich habe echt Mitleid mit dir. Das Traurige dabei ist, bestimmt bist du als Mensch so ein hoffnungsloser Fall, soviel Ego und Selbstliebe, da kann weder ein anderer noch du selbst dich glücklich machen .

Auf nimmer Wiedersehen !

 

[yascod]

Ich finde ein unendlicher Ring buffer ist irgendwie en paradoxum. Ein Ring buffer ist immer unendlich das sagt ja schon der Name...

Ja finde ich auch, ich finde das ähnelt mehr einem Stack irgendwie, da unendlich

 

[Xyz1]

Brauchst du eine Bestätigung dafür? Oder musst du dir das jedes Mal dir selber beweisen, dass du besser als andere bist? Ich habe echt Mitleid mit dir. Das Traurige dabei ist, bestimmt bist du als Mensch so ein hoffnungsloser Fall, soviel Ego und Selbstliebe, da kann weder ein anderer noch du selbst dich glücklich machen .

Schon ziemlich viele Unterstellungen für jemanden der den Rat meiner Person oder des Forums sucht....

Du hältst Dich nicht ernsthaft für was Besseres

 

[yascod]

Schon ziemlich viele Unterstellungen für jemanden der den Rat meiner Person oder des Forums sucht....

Du hältst Dich nicht ernsthaft für was Besseres

Um deinen Rat habe ich nicht gebeten, nochmal anscheinend hast du es ja nicht verstanden, behalte deine Ratschläge und Kommentare. Und meine Unterstellungen sind schon gut begründet, lern du erstmal wie man mit seinem Gegenüber zu sprechen hat. Und nein ich halte mich nicht was für besseres nur kann ich solche Menschen wie dich nicht für voll nehmen. Tue dir selber einen Gefallen und antworte einfach nicht mehr

 

[Xyz1]

@yascod
Nein, Du hast Deine Position verkannt. Ganz einfach.
Du bist derjenige der eine Frage an uns stellt nicht umgekehrt.
Zudem hast Du anscheinend nicht gelesen, Wie man fragen Richtig stellt, Vor dem ersten Posten usw.
Ich finde Verständnisschwierigkeiten sind nicht schlimm,
aber bei diesen absoluten Anfängerfragen (nachdenk....)
Was wolltest Du nochmal machen? Etwas in richtung Programmieren oder doch besser etwas anderes (Malen, Zeichnen, Singen, Taxifahren etc) was etwas anspruchsvoller wäre?
Nicht jeder kann alles Wissen, aber Lern- und Kritikfähigkeit oder auch nur die Basics, kann ich bei Dir nicht erkennen.

 

[yascod]

@yascod
Nein, Du hast Deine Position verkannt. Ganz einfach.
Du bist derjenige der eine Frage an uns stellt nicht umgekehrt.
Zudem hast Du anscheinend nicht gelesen, Wie man fragen Richtig stellt, Vor dem ersten Posten usw.
Ich finde Verständnisschwierigkeiten sind nicht schlimm,
aber bei diesen absoluten Anfängerfragen (nachdenk....)
Was wolltest Du nochmal machen? Etwas in richtung Programmieren oder doch besser etwas anderes (Malen, Zeichnen, Singen, Taxifahren etc) was etwas anspruchsvoller wäre?
Nicht jeder kann alles Wissen, aber Lern- und Kritikfähigkeit oder auch nur die Basics, kann ich bei Dir nicht erkennen.

Erstens gibt es keine dummen Fragen sondern dumme Antworten. Und es ist kein vergehen wenn man was nicht versteht oder kann, jeder fängt irgendwann und niemand kann alles von Geburt aus. Das Problem ist du bist als Menschliches Wesen anscheinend sehr schwach. Da deine Antwort ganz am Anfang einfach daneben war. Sich über Leute lustig zu machen, zeigt einfach wie Charakterlos du bist. Deswegen jetzt zum dritten Mal hör auf zu schreiben, weder deine Kommentare noch deine Aussagen brauche ich. Der andere Gruppenmitglied konnte auch normal antworten. Hättest du von anfang an nicht so frech geantwortet wäre das nie so in die Länge gekommen. Und ich brauche mir auch nicht anzuhören was du über mich denkst, denn es ist mir so ziemlich egal, der Ton einer kleinen Mücke ist mir sogar mehr recht glaube mir

PS:Und bitte Spam nicht mehr meine Frage voll.

 

[Flown]

@yascod @DerWissende schraubt jetzt beide mal einen Gang herunter. Zurück zum Thema und hört mit den persönlichen Angriffen auf.

 

[Xyz1]

Wo war denn ein persönlicher Angriff meinerseits? Der @yascod bezeichnet die einzig richtige Antwort als Blödsinn. Stattdessen sollte er lieber mal die Schmiererei auf der ersten Seite erklären.

 

[yascod]

Wo war denn ein persönlicher Angriff meinerseits? Der @yascod bezeichnet die einzig richtige Antwort als Blödsinn. Stattdessen sollte er lieber mal die Schmiererei auf der ersten Seite erklären.

Wie war das noch mit Selbstkritik? Deine Aussage zu du hattest als einzig die richtige Antwort zeigt wieder einmal wie erbärmlich du bist und selbstverliebt. Aber soviel Genugtuung soll dir mal reichen jetzt. Der Moderator hat recht, ich habe dir zu viel Aufmerksamkeit geschenkt. Meinerseits Entschuldigung an alle anderen Foren Mitglieder und dem Moderator, dass ich dich nicht ignoriert habe und sachlich beim Thema geblieben bin.

 

[yascod]

Und gleich noch einen hinterher:



Das Erweitern von QueueImpl widerspricht der Anforderung lt. Aufgabenstellung, dass RingImpl ein Objekt der Klasse QueueImpl aggregieren soll.

So zum Thema zurück. Ich glaube ich weiß wie ich das jetzt angehen muss, werde aber Heute nicht mehr dazu kommen. Ich melde mich wenn ich weitergekommen bin. Danke dir nochmal für deine Hilfe.

 

[mihe7]

Ich finde ein unendlicher Ring buffer ist irgendwie en paradoxum. Ein Ring buffer ist immer unendlich das sagt ja schon der Name...

Nö.

 

[Robat]

@yascod man kann User hier auch ignorieren (Auf den Namen des Nutzers klicken -> ignorieren) .. dann geht man solchen nutzlosen Konversationen aus dem Weg

 

[yascod]

@yascod man kann User hier auch ignorieren (Auf den Namen des Nutzers klicken -> ignorieren) .. dann geht man solchen nutzlosen Konversationen aus dem Weg

Danke für die Info. Werde ich mal sofort machen

 

[Xyz1]

Ich habe mein Popcorn vergessen

 

[mrBrown]

Ich finde ein unendlicher Ring buffer ist irgendwie en paradoxum. Ein Ring buffer ist immer unendlich das sagt ja schon der Name...

Dafür würde mich die Begründung interessieren...

 

[Thallius]

Dafür würde mich die Begründung interessieren...

Ein Ring hat kein Anfang und kein Ende. Er ist also unendlich. Es sollte also vielleicht mal genauer definiert werden was in dem Fall der aufgabe das unendlich eigentlich bedeutet? Vielleicht ist ja gemeint, dass der buffer unendlich erweiterbar ist. Dann braucht man aber auch eigentlich keinen Ringbuffer. Einsatzzweck eines Ringbuffers ist es doch in der Regel, das man ein sich selbst überschreibenden Buffer mit einer konstanten Größe hat bei dem, wenn der letzte Platz belegt ist und man ein weiteres Element einfügt, das erste Element überschrieben wird. Alles andere macht in meinen Augen keinen wirklichen Sinn.

Gruß

Claus

 

[mrBrown]

Das hängt dann wohl sehr von der Definition von Unendlich ab...ich würde einen Ring jetzt nicht als unendliche Datenstruktur bezeichnen (vor allem, da sie ja auch laut deiner Definition nur eine endliche Menge an Werten fassen können).
Aber das Verhalten, dass alte Elemente überschrieben werden, ist keineswegs so für einen Ringpuffer definiert - der darf durchaus auch wachsen.

Oder kommt etwa wirklich jemand auf die Idee, ein Array der Länge 0 als unendlich zu bezeichnen? Hat auch kein erstes oder letztes Element

 

[Thallius]

der haupteinsatzzweck für einen ringbuffer liegt für mich z.b. in einem Cache. Hier definiert man i.d.R. Eine Größe und wenn der buffer voll ist, dann wird er halt von vorne überschrieben. Deshalb ringbuffer.
Das man diesen natürlich auch dynamisch größer und kleiner machen kann um eben mehr oder weniger Cache Speicher zu haben ist klar, der buffer wird aber eben nicht dynamisch den benötigten Elementen angepasst und da liegt meiner Meinung nach der Unterschied zu einer klassischen Liste.
Von daher macht für mich ein unendlicher ringbuffer, bei dem unendlich so definiert wird, das er sich unendlich vergrößern kann wenn mehr Elemente benötigt werden, keinen Sinn, denn in dem Fall werde ich nie den eigentlich nutzen eines ringbuffers verwende.

Gruß

Claus

 

[mihe7]

Ringpuffer eignen sich z. B. auch für die Implementierung von Queues. Diese können durchaus dynamisch wachsen (so lange der Puffer voll ist), gleichzeitig wird der Speicher der Elemente wiederverwendet, die der Queue entnommen wurden.

 

[Thallius]

Ringpuffer eignen sich z. B. auch für die Implementierung von Queues. Diese können durchaus dynamisch wachsen (so lange der Puffer voll ist), gleichzeitig wird der Speicher der Elemente wiederverwendet, die der Queue entnommen wurden.

Für sowas für ich immer eine Liste nehmen, einen Vuffer macht da keinen Sinn

Gruss

Claus

 

[mihe7]

Warum sollte das keinen Sinn machen?

 

[Thallius]

Warum sollte das keinen Sinn machen?

Weil Du keinen Vorteil damit generierst. Im Gegenteil. Du must sogar jedesmal nachsehen ob noch Platz in Deinem Buffer ist und wenn nicht, dann must du ihn erweitern. Dann doch lieber gleich eine Liste die immer den neuen Eintrag hinten dran hängt und jeden der bearbeitet wird löscht. Ist doch auch wesentlich einfacher zu verstehen.

 

[mihe7]

Du must sogar jedesmal nachsehen ob noch Platz in Deinem Buffer ist und wenn nicht, dann must du ihn erweitern.

Dynamik gibt es nun einmal nicht kostenlos, auch bei der Liste nicht. Die Liste muss den Speicher ständig verwalten (an einem Ende hinzufügen, am anderen entfernen), der Ringbuffer muss lediglich prüfen, ob er voll ist und nur dann erweitert werden.

 

[Thallius]

Ich glaube Du hast dich nie mit Speicherverwaltung beschäftigt. Bei einer Liste wird einfach ein alloc() gemacht und dann ein Zeiger vom letzten Element der Liste auf das neue Element gesetzt. Der Speicher der Liste kann beliebig im RAM verteilt sein. Da muss nichts "verwaltet" werden.

 

[mihe7]

Speicher anfordern und Zeiger setzen zähle ich auf dieser Ebene durchaus zu "verwalten".

 

[Blender3D]

Bei einer Liste wird einfach ein alloc() gemacht und dann ein Zeiger vom letzten Element der Liste auf das neue Element gesetzt. Der Speicher der Liste kann beliebig im RAM verteilt sein. Da muss nichts "verwaltet" werden.

Das alloc() kümmert sich um das Verwalten des Speichers. --> Es muss verwaltet werden.
Ein Grundgesetzt das nie gebrochen werden kann.
Jeder Vorteil bringt immer einen Nachteil mit sich.
Würde das Gesetzt z.B. bei Arrays und Listen nicht gelten dann bräuchte man die Variante nicht mehr die nur Nachteile hat.

 

[Blender3D]

 

[Thallius]

Generell hast du recht aber gerade bei einer Quque wird ja immer das neue Element and das Ende der Liste gehängt und das erste Element heraus genommen. Damit fallen alle Nachteile der Liste gegenüber dem festen array (was ein buffer ja dann wäre) weg

 

[yascod]

So alles klappt jetzt, hab es doch hinbekommen. Jedoch habe ich ne Frage zu Aufgabe b, ich soll ja eine sinnvolle Exception implementieren, die in mindestens drei Methoden von RingImpl auftreten kann. Habt ihr eine Idee was sinnvoll wäre? Denn Ringpuffer ist leer gibt es ja schon und Ringpuffer ist voll würde ja nicht gehen, da unendlich und was anderes fällt mir ehrlich gesagt nicht ein.

 

[mihe7]

@Thallius Der Unterschied zwischen Deiner Linked List und meinem Ringbuffer besteht im Wesentlichen darin, dass das letzte Element der Linked List keinen Nachfolger hat, während beim Ringbuffer jedes Element einen Nachfolger besitzt. Außerdem gibt es bei der Implementierung einer Queue via RingBuffer einen Head- und einen Tail-Zeiger.

Wir können uns ja mal die Operationen ansehen:

I. Einen Wert in die Queue einstellen auf Basis einer Linked List:
1. Speicher für den neuen Eintrag reservieren
2. Wert des neuen Eintrags setzen
3. Zeiger des letzten Eintrags auf neuen Eintrag setzen

II. Einen Wert aus der Queue entnehmen auf Basis einer Linked List:
1. ergebnis := Wert des ersten Eintrags
2. den Zeiger auf das erste Element der Liste aktualisieren
3. Speicher des vormals ersten Eintrags freigeben

Die Schritte aus I. wären bei einer Implementierung mit Hilfe eines "unendlichen" Ringbuffers auch notwendig - aber nur, wenn der Platz ausgeht. Ansonsten reicht es, die Head- und Tail-Zeiger anzupassen, weil dann die bereits vorhandenen Einträge verwendet werden. Der Speicher dieses Ringbuffers muss erst freigegeben werden, wenn er (Ringbuffer) nicht mehr benötigt wird.

Bei der Linked List muss bei I. und II. Speicher angefordert bzw. freigegeben werden.

 

[mihe7]

@yascod Naja, was ist denn z. B. das nächste/aktuelle Element einer leeren Liste? Und was das Hinzufügen von Objekten betrifft: null ist kein Objekt.

 

[yascod]

@yascod Naja, was ist denn z. B. das nächste/aktuelle Element einer leeren Liste? Und was das Hinzufügen von Objekten betrifft: null ist kein Objekt.

Das deckt aber jeweils nur eine Methode. Es muss aber ein Exception für mindestens drei Methoden gelten..

 

[mihe7]

Das habe ich zwar überlesen, aber der erste Part deckt schon drei Methoden ab.