pointersdata-structurescircular-queue

Any idea why this function is defined like this in a circular queue?


I am currently studying circular cues. I came across these functions while studying using the textbook.

int NextPosIdx(int pos)
{
    if (pos == QUE_LEN -1)
        return 0;
    else
        return pos +1;
}

Looking at the algorithm, I wrote these functions first.

int NextPosIdx(Queue* pq)
{
    if (pq == QUE_LEN -1)
        return 0;
    else
        return pq +1;
}

Personally, I think I still lack understanding of pointers. May I ask you to explain why that doesn't work?


Solution

  • There are more than one ways to actually implement a circular queue (or any other data structures).

    The 1st function seems to find the next element based on array index, so here the pos argument indicates the index of the current element.
    if (pos == QUE_LEN -1) means if we are already at the end of the queue, we need to return the 1st element (i.e. array index = 0), as this is circular queue. So what is returned here is just the index of the next element (not the actual data).

    int NextPosIdx(int pos)
    {
        if (pos == QUE_LEN -1) //check if this is the last index of the queue
            return 0;
        else
            return pos +1;
    }
    

    On the 2nd function however, circular queue seems to be implemented using Queue struct and pointer. In this case, you cannot do the same logic as pq is not an index, but rather a pointer to a Queue structure (i.e. memory address). Therefore the statement if (pq == QUE_LEN -1) will theoretically never be evaluated to true.
    Unfortunately you have not provided any information about the Queue structure, so cannot comment on how to fix this. If this is circular queue, then accessing next element should not be a problem, usually there is a member element of Queue struct providing this information.