File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Create a queue from scratch? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Create a queue from scratch?" Watch "Create a queue from scratch?" New topic

Create a queue from scratch?

m brown
Ranch Hand

Joined: Mar 01, 2005
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

Joined: Aug 08, 2003
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

Joined: Oct 23, 2002
Posts: 904

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?

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

Joined: Mar 01, 2005
Posts: 57
thanks for the great reply.
I agree. Here's the link:
subject: Create a queue from scratch?
It's not a secret anymore!