Implement a very large queue using java.

Question

I have a question. I was once asked this in the interview --

Suppose you have a queue.A very large queue containing objects. And you cannot fit this queue in the memory. So how do you go about implementing it so that you can add from the end of the queue.And remove from the start of the queue.How is this solution implemented in Java? Any suggestions..??

Answer 1

I suppose one way of doing it would be to serialize your objects onto disk or store them into a database.

Answer 2

There are at least 2 ways, one is to store the data in a flat file and other is to store it in the database.

In case of flat file, you create a file format like:

[current position]<-- here is no new line
[data    1 length][data    1 in serialized format]<-- here is no new line
[data    2 length][data    2 in serialized format]
[data    3 length][data    3 in serialized format]
[data etc. length][data etc. in serialized format]

When you have a :

• push(), you append to the file
• pop(), you use RandomAccess and seek out the element on current [current position], and after that increment [current position] with [data x length].

In case of database, you create a table like:

[id][element data columns]
   1        
   2        
   3        
etc.  

When you have a :

• push(), you append to the database
• pop(), you use query element by it's id at current_item++; what is stored at your class info.

More things to note: If you need to remove elements, then it might be better, if you do not remove items as soon as you pop(), but later and many items at a time. You should get more then one element when you read, and not bother flat file / database each time you need an item.

Answer 3

You can buy a reasonably priced server with 48 Gb of memory. If you are more than 48 GB behind in processing your data, you have a real problem that writing data to disk will only make MUST worse, not better. (writing to disk can be 100,000x slower than writing to memory, not the sort of thing you need if you are behind in your data)

One solution is to use less memory per object/task (more efficient structures or compression) or get more memory. (often much cheaper than developer time)

A better solution is likely to be; slowing the producer, merging tasks, or dropping tasks.