Какую структуру данных использовать (фиксированная длина)?

Question

Я хотел бы знать, какую структуру данных (очередь) мне следует использовать, если у меня возникла следующая проблема:

• Очередь должна иметь динамически назначаемую длину (скажем, 512).
• Каждое новое значение сохраняется в конце очереди.
• Когда добавляется новое значение, первое отбрасывается, если очередь уже заполнена. Если я добавлю 30 новых значений в полную очередь, первые 30 будут автоматически удалены.
• Тип хранимых данных: массивы или другие простые объекты.
• Мне нужно иметь возможность быстро получать значения с помощью цикла, всегда в порядке (без произвольного доступа).

Цель этого состоит в том, чтобы иметь источник данных фиксированной ширины, который граф будет сканировать, чтобы нарисовать его кривую.

РЕДАКТИРОВАТЬ: Этот график предназначен для отображения в пользовательском представлении Android. Есть ли конкретная длина, которую я мог бы использовать, чтобы сделать цикл более быстрым?

EDIT2: добавлено «При добавлении нового значения первое удаляется , если очередь уже заполнена . Если я добавлю 30 новых значений в полную очередь , 30 первые автоматически удаляются. "

Answer 1

Если емкость стека никогда не изменится, я бы использовал массив.Я бы отслеживал, где находится «первый» узел, и продолжал его оборачивать.

Я также хотел бы отметить, что ваше поведение больше похоже на очередь, чем на стек.Вы уверены, что стек - то, что вы хотите?

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

}

Answer 2

Вам определенно нужен Круговой буфер - очередь на основе массива с модульным доступом.Вы можете легко изменить реализацию, чтобы отбрасывать первые элементы вместо исключения.

Answer 3

Звучит так, как будто тебе нужно ... стек !

Нет, я просто шучу. «Стек» на самом деле не совсем подходящий термин, так как стек является «первым пришел-первым вышел», что означает, что вы добавляете материал в верх, а затем снимаете его в обратном порядке.

Что вам действительно нужно, так это Deque реализация. Это очередь, которая позволяет вставлять и удалять на обоих концах. Я предполагаю, что значения нужно отбрасывать только тогда, когда очередь заполнится. Ваше описание не сделало это полностью ясным. Если вы всегда отбрасываете значения при вставке новых, вы в конечном итоге получите структуру данных, в которой в каждый момент времени есть только один элемент.

Я не знаю реализации, которая автоматически ограничивает количество элементов. ArrayDeque подходит довольно близко, но вам все равно нужно проверить размер на вставках и удалить посторонние элементы с самого начала. Он предлагает типичный iterator метод коллекций Java, который позволяет вам циклически перебирать элементы. Для коллекции этого типа заказ гарантирован.

Answer 4

Я бы порекомендовал LinkedHashSet для уникальных предметов или ArrayList.

Answer 5

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