# Queue Implementierung



## Wippi11223 (10. Jul 2018)

Hallo,

Ich bin auf der Suche nach einer einfachen limitierten Queue auf Basis FIFO.
Dieser Datenspeicher soll x Elemente halten wenn ich das x+1 hinzufüge fliegt das erste aus der Queue. Die Queues die ich gefunden habe sind aber alle speziell und meiner Meinung nach nicht dafür geeignet:


ConcurrentLinkedQueue

DelayQueue

ArrayBlockingQueue

LinkedBlockingQueue

PriorityQueue

PriorityBlockingQueue
Wie kann ich dies umsetzen?

Vielen Dank


----------



## VfL_Freak (10. Jul 2018)

Moin,

hier mal zwei Links, die Dir weiterhelfen sollten:
https://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java
https://commons.apache.org/proper/c...ons/collections4/queue/CircularFifoQueue.html

VG Klaus


----------



## httpdigest (10. Jul 2018)

Was du suchst, nennt sich "Ring Buffer". Solche Datenstrukturen können gut als FIFO eingesetzt werden.
Ich habe dir mal schnell eine Beispielimplementierung gebaut:

```
import java.lang.reflect.Array;
import java.util.NoSuchElementException;
class RingBuffer<T> {
    private T[] array;
    private int size, write;
    public RingBuffer(int capacity) {
        array = createGenericArray(capacity);
    }
    @SafeVarargs
    @SuppressWarnings("unchecked")
    private T[] createGenericArray(int capacity, T... _dummy) {
        return (T[]) Array.newInstance(_dummy.getClass().getComponentType(), capacity);
    }
    public void add(T value) {
        array[write] = value;
        write = (write + 1) % array.length;
        size = Math.min(size + 1, array.length);
    }
    public int size() {
        return size;
    }
    public T get() {
        if (size == 0)
            throw new NoSuchElementException();
        return array[Math.floorMod(write - size--, array.length)];
    }
}
public class RingBufferTest {
    public static void main(String[] args) {
        RingBuffer<Integer> rb = new RingBuffer<>(4);
        rb.add(1);
        rb.add(2);
        rb.add(3);
        rb.get();
        rb.add(4);
        rb.add(5);
        while (rb.size() > 0) {
            System.out.println(rb.get());
        }
    }
}
```


----------



## Wippi11223 (10. Jul 2018)

super vielen Dank!! genau das was ich suche...eine Frage noch:
Ich habe folgende Anforderung: ich bekomme kontinuierlich (also jede Sekunde eine 0 oder 1).
Ich möchte mir die Ratio ausrechnen von einem gewissen Zeitraum. Meine Idee wäre hier einen Queue zu implementieren wo ich mir 15 Werte speichere und mir die Ratio berechne: Summe aller Werte/Queue Size

Oder gibt es dafür eine einfachere Implementierung?


----------



## httpdigest (10. Jul 2018)

Es ist immer interessant, wenn Leute ihren tatsächlichen Use-Case nennen, nachdem dann Fragen zu einer Lösung diskutiert wurden, die eher dafür ungeeignet ist. 
Wenn du also nur Bits hast, dann kannst du dafür wunderbar ein Bitset (in Form eines einfachen ints) nehmen:

```
public class RunningBits {
    private final int bitmask;
    private final int capacity;
    private int bits;
    private int size;
    RunningBits(int capacity) {
        if (capacity < 1 || capacity > 32)
            throw new IllegalArgumentException();
        this.bitmask = (1 << capacity) - 1;
        this.capacity = capacity;
    }
    public void add(int bit) {
        bits = bits << 1 & bitmask | bit & 1;
        size = Math.min(size + 1, capacity);
    }
    public float ratio() {
        return (float) Integer.bitCount(bits) / size;
    }
    public static void main(String[] args) {
        RunningBits bits = new RunningBits(15);
        bits.add(1);
        bits.add(0);
        bits.add(1);
        bits.add(1);
        bits.add(0);
        bits.add(0);
        System.out.println(bits.ratio());
    }
}
```


----------



## Wippi11223 (10. Jul 2018)

Vielen Dank werde mich bessern 
es sind aber nicht nur bits --> es kann sein dass ich hier auch Timestamps und double drin sind


----------



## mrBrown (10. Jul 2018)

Für so einen gleitenden Mittelwert kann man schon einen RingPuffer nutzen (das Bitset ist ja in dem Beispiel nichts anderes, nur eben für Bits optimiert).

Entweder eine fertige Implementierung (Apache Commons und Google Guava müssten beide passendes haben) oder eben was eigenes, was im Hintergrund einfach ne bestehende Queue/List nutzt.


----------

