ern said:
What would a circular array queue look like ?
It's not an assignment !!! arghhhhhh
<OT>
It seems that I missed your post on my default server.
I saw it on a different server at work. I'm now curios to
see whether it will eventually show up on the default
server
</OT>
I learned about it as a "circular array queue", or "queue implemented
using a circular array". I also found it under the name of "circular queue".
It's, basically, a way to implement fixed length queues using arrays (not
only fixed length, but it's usually used when either the number of total
elements is small or you know that you will fill a large part of it all
the time
otherwise it can be a waste of space, if you have no idea how many objects
you can have in the queue at any given time).
A circular array is the one where the first element follows the last
element and
a position is calculated using modulo size of queue. You need two pointers
(meaning indices, not real pointers) to indicate the position of the
head and of
the tail. The problem is determining when the queue is empty and when it's
full as both cases would be indicated by both head and tail indices
pointing to
the same position in the array. This is solved either by using an extra
element
in the array or by keeping a counter. I was taught that the "right" way
to do it is
to keep an extra element in the queue, though the counter implementation
may faster to write. It's not difficult to implement in either cases.