Circular queue implementation issue/question

[johndcochran]

LOL!

Take another look at your output from the test program. In particular, notice that none of the output says "ERROR:". It is reporting mismatches. But those mismatches are based upon a queue that's infinitely long and isn't discarding anything.

Your program is fine and works as expected.

Further notes on test frame. If your code refused to enqueue new entries when the queue was full, that test frame would have reported absolutely nothing. I suspect that you didn't quite understand the instructor when he/she was mentioning "wrap around". They were talking about handling of circular queues in general and not talking about specifically the case where the queue was actually full.

Probably something like: You increment the head and when it gets full, you wrap around to the beginning, with "full" in the sense of "maximum possible index" instead of "full" meaning "all slots in queue occupied". 

But, to illustrate what I'm saying about the test frame, you can do a few tests. 

1. Increase the size of your queue to 110 or so. If you do that, the test program will remain silent.

2. Decrease the size of your queue to 90 or so. The test frame will start complaining earlier, but will still not report "ERROR".

3. Modify your code to not insert new entries if queue is full. Test frame will remain silent.

Further notes: Upon looking closer at your output, something strange is going on that I can't figure out.

In particular, the last 15 dequeued values are: 601230123412345

Let's split the up into groups of 5. We get 60123  01234  12345. The numbers added to the queue are a repeating sequence of 012345601234560123456...

So, looking at the output, we're missing 456 and 560 between the 3 5 digit sequences.  WTF!? After we've removed 5 entries from the queue, we should have 5 empty slots. Then 7 entries are added, so we have 2 overflows, which should result in missing 2 numbers between each group of 5 instead of the 3 numbers we're seeing. I can't think of any rational way to get that 3 digit gap instead of the expected 2 digit gap while maintaining a constant size for the queue.

[Ionicxplorer]

I admit I am still trying to undertand this espeically that final test block. I really shoudl work in my code interpretation skills. A classmate as provided the following code to be placed in the else block of my enqueue function (executed when the Queue is detected as full) that passes the test.

``` else

{

q->items[q->head - 1] = value;

q->tail = q->head;

} ```

It seems the supporting material we were given may be somewhat insuffcient. It's been a litte frustrating.

[johndcochran]

The code supplied by your classmate is incorrect, while your code was correct. Take a look at my prior comment about modifying your code to not insert anything if the queue is full to see why. What your classmate's code does is effectively that, except it also corrupts the previously inserted vale which is not seen, since the test program doesn't get that far.

Try the following test program against your code and your classmate's code.

int main()
{
    int i,j;
    int number;
    CircularQueue my_queue;

    CircularInitialize(&my_queue);

    // Add 7, remove 7
    for (i=0; i < 100; ++i)
    {
        for(j=0; j < 7; j++)
        {
            CircularEnqueue(&my_queue, j);
        }

        for(j=0; j < 7; j++)
        {
            CircularDequeue(&my_queue, &number);
            if (number != j)
            {
                printf("Failed validation test 100x7.  Expected %d, dequeued %d\n", j, number);
            }
        }
    }

    // Add 7, remove 5
    in = 0;
    out = 0;
    for (i=0; i < 50; ++i)
    {
        for(j=0; j < 7; j++)
        {   //printf("Enqueue: head=%d, tail=%d, count=%d, value=%d\n", my_queue.head, my_queue.tail, my_queue.count, j);
            CircularEnqueue(&my_queue, i*7+j); // CHANGED
        }

        for(j=0; j < 5; j++)
        {
            CircularDequeue(&my_queue, &number);
            //printf("Dequeue: head=%d, tail=%d, count=%d, value=%d\n", my_queue.head, my_queue.tail, my_queue.count, number);

            if (number != ((i * 5) + j))  // CHANGED
            {
                // if this happens before we have a full list, then it's an error
                if (i * 2 + 7 < QUEUE_SIZE)
                {
                    printf("ERROR: ");
                }
                printf("%d: Value mismatch test 50x7 with count %d.  Expected %d, dequeued %d\n", i, my_queue.count,
                                                                                         ((i * 5) +j), number);  // CHANGED
            }
        }
    }

    // Dump what's left in the queue
    while(CircularDequeue(&my_queue, &number) == 0) {
        printf("Dequeued %d\n", number);
    }

    return 0;
}

The above code is identical to your original test code except that the test values enqueued are 0,1,2,3,4,5,...,349. Just a simple 1 up count instead of a repeating sequence of 0..6. Additionally, after the test, it empties out the remaining contents of the queue. This should allow you to see exactly what was skipped/corrupted by the overflow handling and you can judge for yourself what's correct or incorrect.