Circular Queue theory

Question

I'm need help understanding the Circular Queue concept. I read a couple post on stackoverflow and none of the answers are answering a mental block I'm having.

For example say I have 8 cells in a Circular Queue.

        Head                              Tail
 empty|U    |   I  |   S  |   K  |   M  |   empty  |   empty 

Say I insert two characters F & P, which will make the queue change to.

  Tail  Head                                
 empty|U    |   I  |   S  |   K  |   M  |   F  |   P 

Now lets make things interesting , what if I remove 3 entries.

  Tail                                  Head                
 empty|  empty  |  empty   |  empty   |   K  |   M  |   F  |   P 

Clearly my Head and Tail has now changed and I have 3 new available spots. But for good measures I wanted to add two more entries.

            Tail                Head                
 A|  B  |  empty   |  empty   |   K  |   M  |   F  |   P 

Here is my questions

Did I implement this right? LOL What happens when you fill the queue up completely as in the Tail and Head are in the same position i.e "K"? If some one can explain this concepts a little more detail and clarity I would appreciated it.

Thanks!

Answer 1

It looks to me like you have it right. You could make you diagram more clear by showing the integer values for head and tail

There are many explanations and examples on circular queues. I have found no better explanation than the one I posted in an answer that I offered some time ago here. It explains how head and tail show if the queue is empty, has room, or is full.

In the last row of your diagram, the queue has room for 2 more items. Adding a third would make tail = head, and would overwrite K, which you don't want to do.

When tail = head, the queue is empty. Testing for a full queue is slightly more complicated. See the link for a full explanation.

Answer 2

Did I implement this right?

Yes, indeed you did.

What happens when you fill the queue up completely as in the Tail and Head are in the same position i.e "K"?

K will be overwritten. This overflow condition can be checked by the condition TAIL == HEAD.

If some one can explain this concepts a little more detail and clarity I would appreciated it.

What you have to understand that in a traditional linear FIFO queue, the elements needed to be shifted continuously whenever the maximum size is reached. For example, if the queue has size of 5, then after 5 (numbers 1-5) consecutive inserts and then a delete (number 1 gets deleted), the queue becomes [null, 2, 3, 4, 5]. You can see here that although there is place for 1 more element, you cannot insert unless you shift all the elements up by one. This is why circular queue is used. It doesn't need element-shifting.

However, if your queue is constantly being overflown, the entire purpose of queue is lost. I would recommend using linked list (linear or circular) as it dynamically adds and deletes elements.

Remember that queue is used practically when there is a limitation on memory. E.g. Input/Output stream is a queue. When memory is plenty and data overriting is not prefered, linked lists are used.