Thread: Piece of code failed in CodeRunner but not on Cygwin CLion - C

Hey.

This is the code:

Code:

#define QUEUE_CAPACITY 4


typedef struct Queue
{
    size_t head; // The current head index to be dequeued in the next call to dequeue
    size_t tail; // The next element index to be inserted to the queue
    // head and tail range is: [0, ..., QUEUE_CAPACITY -1]
    size_t numOfElems;  // The current amount of elements in the queue
    int data[QUEUE_CAPACITY];
} Queue;


Queue gMyQueue;


// If numOfElems == QUEUE_CAPACITY - enqueue does nothing.
void enqueue(int elem) {
    if (gMyQueue.numOfElems == QUEUE_CAPACITY) {
        return;
    }
    gMyQueue.data[gMyQueue.tail] = elem;
    gMyQueue.tail = ++gMyQueue.numOfElems;
}


// If the queue is empty - dequeue does nothing and returns 0.
int dequeue(void) {
    if (gMyQueue.numOfElems == 0) {
        return 0;
    }
    gMyQueue.numOfElems--;
    gMyQueue.head++;


    return gMyQueue.data[gMyQueue.head - 1];
}


void printQueue()
{
    size_t i = gMyQueue.head, j =0;
    for( ; j < gMyQueue.numOfElems; i = (i + 1) % QUEUE_CAPACITY, ++j)
    {
        printf("%d, ", gMyQueue.data[i]);
    }


    printf("\n");


    printf("head: %lu, tail: %lu\n",
           gMyQueue.head, gMyQueue.tail);
}


int main()
{
    enqueue(3);
    enqueue(4);
    enqueue(5);
    enqueue(6);
    enqueue(7);
    printQueue();


    return 0;
}

Our university's platform is running Code Runner which includes its automatic tests, and my code has failed in one of the tests which runs this main code.

In my CLion cygwin platform the program prints the expected result (which is 4), and in the school test the tail equals somehow to 0...

Does someone have an idea?

Originally Posted by HelpMeC

So, I didn't understand well enough the meaning of tail. If the queue is full, the tail is equal to the head, but it doesn't say that our next insertion is to the head index; Moreover, it doesn't say nothing about the insertion of the next element...

There is no hard and fast "rule". But for a circular queue that is implemented using an array then tail would in general be the index of the element, of the array, where something can be stored. It's not a hard and fast rule; you can do it many ways but based on the rest of the code in your example tail must be one of 0, 1, 2 or 3.

It's a queue, so the next insertion (if space is available) is at the tail, not the head. Queues are first in, first out (FIFO). So If something (or someone) joins a queue they join it at the end (i.e. the tail). I guess nothing is said about that because that's the standard definition of a queue (in contrast to stacks which are last in, first out (LIFO). Think of it as you joining a queue at the supermarket... you go at the end of the queue (i.e. the tail). This is different to stacks -- which can be looked at as kind of like piling boxes on top of each other in a column.

Insertion for a queue should not be at the head; it should be at the tail (the end of the queue).

Personally I think you should be drawing pictures on paper until you get the idea in your head. The concepts of queue and stack are very well established so inserting at the tail (or the head) should not have to be explicitly stated. In fact, because they're abstract data types it doesn't really matter how you implement it as long as a queue is FIFO and a stack is LIFO. But, yes, given the rest of the code in your example I would expect tail to be 0, 1, 2 or 3.

Edit: In your implementation just because head == tail does not mean that the queue is full (it could also be empty). This is fairly typical, but I can't help but think that your teacher (if this is for school) doesn't understand abstract data types at all. E.g. in main() the value of head or tail (for an abstract data type) is kind of meaningless because it depends on how you implement the queue. You should, instead, have functions called isempty() and isfull() and never look at the values of head and tail at all (except in the implementation details which should be considered as opaque and calling functions -- e.g. main() -- should not even directly use the values of head and tail). The fact that your school seems to want you to print the value of tail indicates, to me, that the school/teacher has missed the point of abstract data types (like queues) completely