Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Create a queue from scratch?

m brown
Ranch Hand
Posts: 57
hi, i was wondering how i would be able to crete a queue from scratch, without using the collections or map classes? i tried looking on the web and in several books, but they didnt seem to help...please help!

Ray Stojonic
Ranch Hand
Posts: 326
1- Decide what features you would like your queue to have. (I'm certain there is information on what a queue should do online)

2- Implement the features in step 1 with Java.

Svend Rost
Ranch Hand
Posts: 904
Hi,

Yes, and in fact it's not that hard as you might think.

The queue ADT supports the two following methods:

void enqueue(Object o) - Insert object o at the rear
Object dequeue() - Remove and return the first object

Other methods are:
size(), isEmpty() and front()

There are more than one way to implement the queue. Lets take a look at an array-based implementation:

You need an array, Q, with capacity N and two variables f and r, which point to the first (f) element of the queue and the rear (r), which is where the next element will be removed. Since we'r making an array implementation you wish to use the array Q in a circular fashion.

How do you increment r and f, using a circular approach ?
Simple - f, for instance, gets computed by (f+1) % N

How do I know, that the queue is empty?
r=f

Lets continue to the methods:

Are there any good or bad things about this implementation? The insertions are inserted in constant time ( = O(1) ). However, since the above mentioned implementation doesn't do anything if the queue gets filled up we have to set N to a large number, which isn't good in a real world application.

What to do ?
- if you havea good estimate of the numer of elements that will be in the queue at the same time, then the implementation will be quite efficient.
- You can increase (e.g. double) the array size if you run out of space in the array. This, ofcause, costs time.
- choose another implementation. In a linked list approach for instance you can en-/dequeue in constant time - all the time, and the space usage is kept at a minimum.

If you still lacks information, then feel free to reply to this thread.

/Svend Rost

m brown
Ranch Hand
Posts: 57