2

I would like to know what kind of data structure (queue) I should use if I have the following problem:

  • The queue must have a dynamically assigned length (say, 512).
  • Every new value is saved at the end of the queue.
  • When a new value is added, the first is dropped if the queue is already full. If I add 30 new values to a full queue, the 30 first are automatically dropped.
  • The kind of data stored be arrays or some other simple object.
  • I need to be able to quickly retrieve the values using a loop, always in order (no random access).

The purpose of this is to have a fixed width data source that a graph will scan to draw its curve.

EDIT: This graph is meant to be shown on an Android custom View. Is there a specific length I could use that would make the looping thru this faster?

EDIT2: Added "When a new value is added, the first is dropped if the queue is already full. If I add 30 new values to a full queue, the 30 first are automatically dropped."

Reno
  • 33,594
  • 11
  • 89
  • 102
AntoineG
  • 1,237
  • 4
  • 15
  • 25
  • is there some constraint that you will never, not even temporarily, exceed the stack size? otherwise what about a Map? just add and remove appropriately? – Randy Oct 31 '11 at 21:11
  • possible duplicate of [Is there a fix sized queue which removes excessive elemets?](http://stackoverflow.com/questions/1963806/is-there-a-fix-sized-queue-which-removes-excessive-elemets) – slayton Oct 31 '11 at 21:11
  • @Randy a map won't have order. Perhaps a linked hashset, but again there's no need for random access. – corsiKa Oct 31 '11 at 21:11

5 Answers5

4

If the capacity of the stack is never going to change, I would use an array. I would keep track of where the "first" node is and keep wrapping it around.

I'd also like to point out that you're behavior seems more like a queue than a stack. Are you sure the stack is what you want?

class RotatingQueue<E> {
    Object[] data; // can't do E[]
    final int maxSize;
    int size = 0; // starts empty
    int first = 0; // starts at the front, why not?

    RotatingQueue(int size) {
        this.maxSize = size;
        data = new Object[size];
    }

    E add(E e) {
        E old = (E)(data[first]);
        old[first++] = e;
        if(size < maxSize) size++;
        return old;
    }

}
corsiKa
  • 81,495
  • 25
  • 153
  • 204
1

You definitelly need a Circular buffer - array based queue with modular access. You can easily modify the implementation to drop first elements instead of throwing an exception.

malejpavouk
  • 4,297
  • 6
  • 41
  • 67
0

See the ArrayBlockingQueue: http://download.oracle.com/javase/1,5.0/docs/api/java/util/concurrent/ArrayBlockingQueue.html

slayton
  • 20,123
  • 10
  • 60
  • 89
0

I would recommend LinkedHashSet for unique items or an ArrayList.

Mechkov
  • 4,294
  • 1
  • 17
  • 25
0

It sounds like you need... a stack!

No, I'm just kidding around. "Stack" isn't really the right term here, since a stack is "last-in-first-out", meaning that you add stuff to the top and then take it off in reverse order.

What you really need is a Deque implementation. It's a queue that allows insertion and removal at both ends. I'm gonna assume values only need to be dropped when the queue gets full. Your description didn't make this entirely clear. If you'd always drop values when inserting new ones, you'll end up with a data structure that only has one element in it at any time.

I don't know of an implementation that automatically limits the number of items. ArrayDeque comes pretty close, but you'd still need to check the size on insertions and remove extraneous elements from the start. It offers the typical iterator method of Java collections that allows you to loop over the items. For a collection of this type the order is guaranteed.

G_H
  • 11,739
  • 3
  • 38
  • 82