GenericQueue / Implementierung als Ringspeicher

Diskutiere GenericQueue / Implementierung als Ringspeicher im Java Basics - Anfänger-Themen Bereich.
I

iris_anfänger

Java:
import java.util.*;

/*
* Queue - am rechten Ende werden neue Elemente hinzugefügt,
* am linken Ende werden Elemente entnommen
*/

class QueueException extends Exception {
    public QueueException() { super(); }
    public QueueException(String message) { super(message); }
}

public class GenericQueue <T> {

    private int anz = 0, max = 0;
    private ArrayList <T> data = null;

    public GenericQueue(int max) {
        if (max <= 0)
        max = 3;
        this.max = max;
        data = new ArrayList <T> (max);
    }

    public void queue(T e) throws QueueException {
        if (anz < max ) {
            if (anz < data.size())
            data.set(anz, e); // ersetzt das Element an der angegebenen Position in der Liste durch das angegebene Element
            else data.add(e); //hängt das angegebene Element an das Ende dieser Liste an
            anz++;
        }
        else
            throw new QueueException("Stack is full!");
    }
    
    // ENTFERNEN
    public T dequeue() throws QueueException  {
        if (anz > 0) {// min. ein Element vorhanden werden soll, um den zu löschen
        data.remove(0); // entfernt das Element an der angegebenen Position in der Liste
        return data.get(anz);
        } else
            throw new QueueException("Stack is empty!");
    }

    public String toString() {
        String s = "";
        for (int k = 0; k < anz; k++)
            s = s + data.get(k) + "  ";
        return s + '\n';
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        GenericQueue <Integer> st = new GenericQueue<Integer>(3);
        try {
            st.queue(new Integer(3)); System.out.println(st);
            st.queue(new Integer(4)); System.out.println(st);
            st.queue(new Integer(5)); System.out.println(st);
            st.dequeue(); System.out.println(st);
            st.dequeue(); System.out.println(st);
            st.dequeue(); System.out.println(st);
        } catch(QueueException e) {
            System.out.println(e.getMessage());
        }
        try {
            st.queue(new Integer(3)); System.out.println(st);
            st.queue(new Integer(4)); System.out.println(st);
            st.queue(new Integer(5)); System.out.println(st);
            st.queue(new Integer(6)); System.out.println(st);
        } catch(QueueException e) {
            System.out.println(e.getMessage());
        }
    }
}
Hallo zusammen,
in Analogie zur vorgegebenen Klasse (ArrayList) soll ich eine Datenstruktur GenericQueue, eine Warteschlange entwerfen.
Das Problem, dass die Elemente können nur links (am Anfang) entfernt werden. Elemente hinzufügen hat bei mir geklappt, aber ENTFERNEN (dequeue) leider …... Hat jemand eine Idee?
 
H

httpdigest

Du darfst nicht wirklich ein Element aus der ArrayList entfernen, also nicht `List.remove(0)` aufrufen. Das einzige, was du bei einem Ringpuffer/-speicher machen musst, ist dir zu merken, welches die Position für das nächste zu entfernende Element und welches die Position für das nächste hinzuzufügende Element ist und entsprechend diese Positionen inkrementieren/dekrementieren (mit Modulo).
 
I

iris_anfänger

Oracle Docs:
public E remove(int index)

Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
Specified by: remove in interface List<E> Overrides: remove in class AbstractList<E> Parameters: index - the index of the element to be removed Returns: the element that was removed from the list Throws: IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())


Warum darf man nicht dann ein Elemant aus der ArrayList entfernen?
 
H

httpdigest

Vielleicht nochmal zurück an den Anfang: Was genau ist das Problem? Wenn du in die ArrayList per add() Elemente am Ende hinzufügst und per remove(0) am Anfang entfernst, dann hast du doch eine Queue gebaut und du willst doch dann nur am Anfang Elemente entfernen...
Allerdings ist das dann noch kein Ringspeicher (wie im Betreff genannt).

Dein Problem ist eher, dass deine dequeue() Methode falsch ist, weil sie eben nicht das am Anfang entfernte Element zurückliefert und auch nicht anz dekrementiert. Sie sollte wohl eher so aussehen:
Java:
public T dequeue() throws QueueException {
  if (anz == 0)
    throw new QueueException("Stack is empty!");
  anz--;
  return data.remove(0);
}
 
I

iris_anfänger

Vielleicht nochmal zurück an den Anfang: Was genau ist das Problem? Wenn du in die ArrayList per add() Elemente am Ende hinzufügst und per remove(0) am Anfang entfernst, dann hast du doch eine Queue gebaut und du willst doch dann nur am Anfang Elemente entfernen...
Allerdings ist das dann noch kein Ringspeicher (wie im Betreff genannt).

Dein Problem ist eher, dass deine dequeue() Methode falsch ist, weil sie eben nicht das am Anfang entfernte Element zurückliefert und auch nicht anz dekrementiert. Sie sollte wohl eher so aussehen:
Java:
public T dequeue() throws QueueException {
  if (anz == 0)
    throw new QueueException("Stack is empty!");
  anz--;
  return data.remove(0);
}

Super. Vielen vielen Dank!!!! :) Jetzt habe ich verstanden und dazu noch ein passendes Thema gefunden. https://www.java-forum.org/thema/algorithmus-warteschlange-ringpuffer-wirklich-fehlerfrei.184549/
 
Thema: 

GenericQueue / Implementierung als Ringspeicher

Passende Stellenanzeigen aus deiner Region:
Anzeige

Anzeige

Anzeige
Oben