Какие-либо библиотеки Java обеспечивают реализацию Очереди произвольного доступа?

Seems like a task for a Circular Buffer - as long as it's okay if the queue has a fixed capacity. I don't know of any standard implementation though. But here is a nice recipe to roll your own.

If you have a large enough array you can implement a queue with a basic array, and just use an index as to the head of the list, and use the mod operator so you can wrap around if needed.

So, you basically have a circular array that supports the insert and remove functions.

UPDATE:

It is a quick operation to copy an array to a larger array, so just double in size, perhaps, when getting close to the end, and just copy the array, as a step in doing insert. Overall you will still have very fast access, as the norm should not be to increase and copy.

How fast are the events coming in and out of this queue?

On the one hand, you can have a "sufficiently large" circular buffer.

While it is technically "bounded", you can make it "unbounded" by growing it as necessary.

By the same token, you can "shrink" it down in terms of overall capacity when it's "quiet".

But, for many applications a 100, 1000, or even 10000 item capacity circular buffer is effectively unbounded.

If it truly must be unbounded, then something like ConcurrentSkipListMap may be useful, if you assign an incrementing sequence to each event to use as the key in the map. It provided methods such as pollFirst/LastEntry. If you can sacrifice the unbounded nature of it, then a ring buffer maybe what you need.

The only library I can think of that would implement such an interface would be a LinkedList but frankly I'm not sure what the performance characteristics are.

Просто выбросить это в качестве альтернативы собственному катанию, поэтому, пожалуйста, отнеситесь к этому с долей скептицизма: в зависимости от того, как часто вам нужен произвольный доступ get (i) и какая производительность вам нужна (и насколько большой будет размер вашей очереди), вы всегда можете использовать ArrayDeque.toArray () [i] , когда вам нужно получить доступ к элементу. toArray () использует систему . arraycopy () , что должно быть довольно быстрым для небольших очередей и периодического использования. Помогло бы понять, зачем вам нужен произвольный доступ к очереди и как часто он нужен - возможно, есть другой способ реализовать ваш алгоритм без этого.

Биномиальная куча может иметь амортизированную вставку O (1) и амортизированное удаление O (log n) мин; Я считаю, что он также может иметь амортизированный произвольный доступ O (log ** 2 n). Queue-push будет вставлять элемент в кучу с последовательными целыми числами в качестве ключей.

С помощью rbtree вы можете делать queue-push с пессимистическим O (log n) для всех вставок, удалений min и произвольного доступа. Это потому, что дерево будет иметь непрерывный набор целых чисел в качестве ключей, а k-й элемент очереди будет элементом в дереве с k-м ключом.