> We know that in an circular array implementation of Queue initially pointers Front and Rear will point to same location
> Overflow Condition: If (Rear+1) mod n = Front
> Underflow Condition: If Front and Rear pointers were pointing to same location (This also indicates that the queue is empty)
1. Initially our array will look like this
Pointer | F,R | | | | | | |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | | | | | | | |
After running
for(x=1;x<=6;x++)
q.enqueue(x);
we will end up with an array looking like this
Pointer | F | | | | | | R |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | | 1 | 2 | 3 | 4 | 5 | 6 |
Please note that Rear pointer will be incremented before insertion
2.) Now the below steps will occur
for (int k = 1; k <= 3; k++) { q.dequeue(); q.enqueue(q.dequeue()); }
I will show you the state of our array and the pointer after each iteration please bear with me
i.) x=1; first dequeue() is called so the pointer 'F' will be incremented and the value pointed by it will be returned, alas we have no use for the value returned by it so simply increment the pointer when ever you see this statement
Pointer | | F | | | | | R |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | | 1 | 2 | 3 | 4 | 5 | 6 |
ii.) q.enqueue(q.dequeue());
Now this is where things get really interesting we are enqueing the dequeued value, let me break it down for you
a.) Increment the 'F' pointer pop the value pointed by it
Pointer | | | F | | | | R |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | | 1 | 2 | 3 | 4 | 5 | 6 |
pop will return 2
b.) Increment the 'R' pointer and insert the value popped previously
Pointer | R | | F | | | | |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
At the end of running for x=2 our array will look like
Pointer | | R | | | F | | |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | 2 | 4 | 2 | 3 | 4 | 5 | 6 |
At the end of running for x=3 our array will look like
Pointer | | | R | | | | F |
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Value | 2 | 4 | 6 | 3 | 4 | 5 | 6 |
This where our little program will stop.
We are asked for the value stored in the index 1 and that will be 4.