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.