enqueue/dequeue per veketteter liste

[mar]

guten abend.

aufgabe ist das enqueue/dequeue prinzip mit hilfe einer einfach verketteten liste umzusetzen.

vorgegebener code:

public void enqueue(int e) throws IllegalStateException {
if ( count >= SIZE ) throw new IllegalStateException("full");
a[upper] = e;
upper = (upper+1)%SIZE; ;
count++;
}

public int dequeue() throws IllegalStateException {
if ( count <= 0 ) throw new IllegalStateException("empty");
int res = a[lower];
lower = (lower+1)%SIZE; ;
count--;
return res;
}

hier mein versuch mit jener liste.
newListElem enthält den von eclipse erzeugten konstruktor, sprich die zuweisungen this.nf = nf und this.wert = wert.
ich konnte das programm selbst noch nicht testen.

ich bin einfach noch verunsicherheit über die funktionsweise dieser listen. enthält bspw. newCurrent nach der zuweisung in remove(int count); den letzten wert der warteschlange? zeigt newListElem.nf nach der prüfung auf != null auf die nächste nicht belegte speicherzelle (null)?

public void add()
{
	while (newListElem.nf != null)
	{
		count++;
	newListElem = newListElem.nf;
}
	count = (count + 1) % SIZE; ;
}

public ListElem remove(int count)
{ 
	if (newListElem.nf != null)
{
	count--;
newCurrent = newListElem.nf;
}
count = (count + 1) % SIZE; ;
return newCurrent;
}

public void enqueue(int e) throws IllegalStateException 
{
if (count >= SIZE) 
	throw new IllegalStateException("full");
if (first == null)
	first = newListElem;
newListElem.wert = e;
add();
}

public int dequeue() throws IllegalStateException {
	if (count <= 0) throw new IllegalStateException("empty");
	remove(count);
	int res = newCurrent.wert;
	return res;
 }

 

[Spacerat]

Ich hatte da mal so etwas kreiert...

package somepackage.bigcollections;

import java.io.Serializable;

public class BigQueue<V>
implements Serializable
{
    private static final long serialVersionUID = -4995075002229630425L;
    private Multiplex<V> first = null, last = null;

    public synchronized boolean enqueue(V value)
    {
        if(value == null) throw new NullPointerException();
        if(first == null) {
            first = last = new Multiplex<V>(value, null);
        }
        first = new Multiplex<V>(value, first);
        return true;
    }

    public boolean isEmpty()
    {
        return first == null;
    }

    public synchronized V dequeue()
    {
        if(last == null) return null;
        V rc = last.getValue();
        last = last.getLower();
        if(last == null) first = null;
        return rc;
    }

    private final class Multiplex<VV>
    implements Serializable
    {
        private static final long serialVersionUID = -6841412173677792593L;
        private final Multiplex<VV> lower;
        private final VV value;

        private Multiplex(VV value, Multiplex<VV> lower)
        {
            this.value = value;
            this.lower = lower;
        }

        private Multiplex<VV> getLower()
        {
            return lower;
        }

        private VV getValue()
        {
            return value;
        }
    }
}

mfg Spacerat

 

[mar]

du hast zusätzlich typparameter verwendet. die lasse ich noch aus.

wie könnte man das problem mit einer doppelt verketteten liste lösen? auf dein exemplar bezogen (im ansatz):

while (lower != last)
{
lower.vorletztes = lower;
}

 

[Spacerat]

Darüber habe ich mir noch gar keine Gedanken gemacht, weil eine doppelt verkettete Liste für eine Queue wohl kaum in Frage kommt. Zur "BigQueue" existieren noch zwei (ok... drei) weitere Klassen, die anders als die Java-Collections, unendlich viele Elemente aufnehmen können. Da wären "BigStack" (einfach verkettet), "BigList" (doppelt verkettet) und eine Klasse "ObjectStore" , welche eine "BigList" für iterativen Zugriff auf die Elemente gestattet, die in einer Baumstruktur abgelegt werden. Als einziges Exemplar wäre für dich also noch die "BigList" interessant. Mich interessiert dabei eigentlich nur, wie man doppelt verkettete Listen schnell und einfach sortiert. Was "BigList" nun von "BigStack" und "BigQueue" unterscheidet, ist die Tatsache, das der Multiplexer der "BigList" statt nur einem Verweis eben beide Verweise (nächstes bzw. voheriges Element) aufnimmt.

private final class Multiplex<VV>
{
    private final Multiplex<VV> higher, lower;
    private final VV value;

    private Multiplex(VV value, Multiplex<VV> lower, Multiplex<VV> higher)
    {
        this.value = value;
        this.higher = higher;
        this.lower = lower;
    }

    private VV getValue()
    {
        return value;
    }

    private Multiplex<VV> getHigher()
    {
        return higher;
    }

    private Multiplex<VV> getLower()
    {
        return lower;
    }
}

BTW.: Wenn man sich entschliesst, die Typparameter wegzulassen, sollte man die Multiplex als Memberklasse statisch machen. Das spart unheimlich Speicher zur Laufzeit.

mfg Spacerat

 

[Gast]

das collections framework ist erstmal zweitrangig. aber für die hinweise, weil ich mich damit noch befasse. wichtig ist eben dieses verhalten der listen selbst zu programmieren und keine bestehenden implementationen zu nehmen.

 

[Spacerat]

@Gast: Da mach dir mal keine Gedanken... Der von mir veröffentlichte Code besteht nur hier und auf meiner Festplatte im Entwicklungs-Ordner. Die Collections hatte ich nur erwähnt, weil meine Implementationen nicht wie diese in ihrer Kapazität durch "Integer.MAX_VALUE" begrenzt sind. Ausserdem haben sie mit dem Collection-API, bis auf die Tatsache, das sie parametrisier- und serialisierbar sind und irgendwelche Objekte speichern, wirklich nichts gemeinsam.

mfg Spacerat