CODEWITHSUNDEEP
javadata-structures
AntoineG
AntoineG

Reputation: 1247

What kind of data structure to use (fixed length)?

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

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."

Upvotes: 2

Views: 2719

Answers (5)

malejpavouk
malejpavouk

Reputation: 4445

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.

Upvotes: 1

corsiKa
corsiKa

Reputation: 82579

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;
    }

}

Upvotes: 4

G_H
G_H

Reputation: 12009

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.

Upvotes: 0

Mechkov
Mechkov

Reputation: 4324

I would recommend LinkedHashSet for unique items or an ArrayList.

Upvotes: 0

slayton
slayton

Reputation: 20319

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

Upvotes: 0

Related Questions