What type of Blocking Queue should i use?

Question

I want to implement a blocking where I can add element any time, any way. But I must be able to access them sequentially.

For example, consider a queue of x elements where the elements 1,4,8,10 have been added. So 10 can be accessed, but until 9 is added and accessed, 8 cant be. In short, all the elements are interrelated.

Please let me know if java already has such type of collection implemented. So I can use it directly.

Not sure I understand the question; but wouldn't an array of 10 suffice and when you encounter a empty value, within the array you simply stop iterations though it? if I start at 1 I wouldn't be able to go to 2 but what about 10? and if 2 was in your array would I be able to go from 1 to 2 or from 2 to 1 but not from 2 to 3? Sequential access would be controlled by the fact you have a LOOP ascending or descending based on parameter passed into function. — xQbert, Dec 14 '11 at 13:34

score 1 · Answer 1 · edited May 23 '17 at 11:55

You're talking about either a stack or a queue, depending on if you want them to be FIFO or LIFO, combined with inserting the elements in numerical order in the first place - meaning you're sorting the elements upon insertion so they are always in the correct numerical order.

By sorting the elements by numerical order upon sort, it's guaranteed that they'll be in the order you expect when you remove them.

You can use Java's a LinkedList to both insert elements where you want them in the list, and also remove them either form the "back" or "front" of the list, as needed.

Finally, in order to ensure that you cannot remove an item unless it is the next in the sequence, you need to simply do a check on the value before removing it from the list to make sure that it was sequentially the next one after the last element removed. If it doesn't pass that criteria, either return "false" or some other value that indicates that nothing can be removed from the list at this time.

Also, check out this question: Creating a blocking Queue<T> in .NET? - it's not Java, but it's very similar, and may provide some insight.

Small addition: if I understood your explanation properly, you might want to keep a cursor that points to the last valid element (e.g. in [1,2,3,4,6,7,8] it points to 4, since 6 and beyond couldn't be retrieved. Your cursor would only have to be updated when adding elements. — Miquel, Dec 14 '11 at 13:44

score 0 · Answer 2 · answered Dec 14 '11 at 13:38

Wrap Queue with logic that pushes items to it in order. Eg. create a class which implements Queue and BlockingQueue. Most methods (like get) delegates directly to something like an internal ArrayBlockingQueue, but "put" would put stuff onto the internal ArrayBlockingQueue in order. If put is called with an element that should not yet be accessible, you store it in another, intermediate, data structure.

Every time put is called with an element that is "next up", you push it to the queue, and then go through your intermediate data structure and add any elements to the queue that can now be added.

What type of Blocking Queue should i use?

2 Answers2