• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Create a queue from scratch?

 
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Ranch Hand
Posts: 326
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 904
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks for the great reply.
 
Tell me how it all turns out. Here is a tiny ad:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic