• Post Reply Bookmark Topic Watch Topic
  • New Topic

Implementing custom Queue FIFO, crosspost  RSS feed

 
Mike Anna
Ranch Hand
Posts: 117
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear all,

After no help from another forum, I thought Id post this question here. Id be really glad if someone could offer some suggestions
One of my friends asked this, and I was trying to figure out how I would do this.
He wants implement a queue, FIFO, without using any of the custom implementations in java.
Heres what I thought :

I will use a class Queue :


Now the problem is, the int would overflow some day. I decided to use double. yet again, one day even that will overflow.
Then I thought of keeping a flag, where it will check for the maximum overflow limit of the double. and once it is about to reach it, have another class "index" the entire collection. Like if objects with keys 1 and 2 are removed, and there are MAXLIMITOFDOUBLE-2 elements, I will have to ensure that the objects are shuffled and start again based on 0.

Am I overlooking something really simple ?

I am wondering if there is a way where I can maintain the FIFo logic ?
May be a completely new solution.

I would appreciate any help on understanding this.


Thanks
 
Nitesh Kant
Bartender
Posts: 1638
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can simply use an array to store the elements and always return the first element.
The problem that you will get is to choose a length for the array.
Since, the size of array, once created can not be altered, so, once it is full, you have to create a new array with the capacity as the (old capacity + increment factor) and copy all the elements from the old array to the new one.

I dont think using a Hashmap here is giving you anything as a HashMap is used when data is in the form of a key and a value.
[ May 19, 2008: Message edited by: Nitesh Kant ]
 
Campbell Ritchie
Marshal
Posts: 56227
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
More of a beginner's question . . .

Nitesh Kant is correct. If you use an array you have a preset maximum size of queue; you use [index++ % size] for your insertion and a very similar syntax for removal. You don't actually have to delete elements; they will simply be overwritten. That has the advantage of rapid performance, but you will have to throw an exception if the two indices catch up with each other.

Another way to do it is to create a linked list.
 
Campbell Ritchie
Marshal
Posts: 56227
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nitesh Kant is correct that you can copy your entire array into a larger array if you overflow your capacity. Quicker to copy the "active" part, maybe. That is how the fastest Queue implementation works, ArrayDeque.

But a linked list will never have a capacity problem. You might still need an EmptyQueueException however.
 
Mike Anna
Ranch Hand
Posts: 117
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Nitesh and Campbell.
However, if I use an array, I will still not be able to enforce the FIFO logic. well... just thinking of it, I think I can. Out of the box ? I dont think so. i will have to probably give it a layer of abstraction, and give my custom method for removal of elements, and in that method, I will have to check if the given element corresponds with a least number of index.
((n,Object) where n is the smallest).
LinkedList will give an overhead of performance, especially when we are talking about running out of the max limit of a double.
What do you say ?
 
Nitesh Kant
Bartender
Posts: 1638
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike:
and give my custom method for removal of elements, and in that method, I will have to check if the given element corresponds with a least number of index.
((n,Object) where n is the smallest).


If you always store the new item at the first available index, then you can always return the item at index 0 of the array as it will always be the first element to be added to the queue.


Mike:
LinkedList will give an overhead of performance, especially when we are talking about running out of the max limit of a double.
What do you say ?

Well not really. Since, you always add at the end and remove the first, so you will not have any overhead, in fact it will be better than using an array as you do not have to deal with an overflow.
 
Campbell Ritchie
Marshal
Posts: 56227
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't use floating point arithmetic for this sort of thing at all.
The array with moving indices and % to keep the indices in the requisite range will give the best performance, but as Nitesh has told you, you have to find some way of copying the "active" part of the array into a larger array when you exceed your present capacity. That is (as far as I know) how ArrayDeque works.

I think you call the array and % combination a circular array.

As you say, a linked list may be easier to implement, and I think the performance overhead will be slight. If you are really running to the limit of a double, you will run out of memory before you run out of index capacity.

I don't understand your point about index(n, Object). Do you mean you have to eliminate duplicates when polling the queue? Difficult. The nearest structure I can think of to that is the LinkedHashSet. That eliminates duplicates on insertion.

It might be courteous to put a post on the "other" forum that you have got replies here.
 
Mike Anna
Ranch Hand
Posts: 117
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Nitesh and Cambell.
I think I atleast have some clarity now.

Cheers..
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!