logic of array based queue in C

Question

I happen to come across the implementation of an array based queue while reading through the internet:

#include <stdio.h>
#include <stdlib.h>

typedef int item_t;
typedef struct {item_t *base; 
                int    front; 
                int     rear; 
                int     size;} queue_t;

queue_t *create_queue(int size)
{   queue_t *qu;
    qu = (queue_t *) malloc( sizeof(queue_t) );
    qu->base = (item_t *) malloc( size * sizeof(item_t) );
    //printf("q->base address %p\n",qu->base);
    qu->size = size;
    qu->front = qu->rear = 0;
    return( qu );
}

int enqueue( item_t x, queue_t *qu)
{   
    printf("modulo result %d\n",((qu->rear +2)% qu->size));
    if ( qu->front != ((qu->rear +2)% qu->size) )
    {   qu->base[qu->rear] = x; 
        qu->rear = ((qu->rear+1)%qu->size);  
        return( 0 );
    }
    else
       return( -1 );
}

Here is the create queue and enqueue logic from the code. Initially front and rear is zero.qu->front and ((qu->rear +2)% qu->size) is not equal so the item will be enqueued. I am unable to understand why is 2 used in this logic- ((qu->rear +2)% qu->size) ?

If i select the size of the array based queue as 4 , then with the above logic I could only enqueue 2 elements? — Arnold
– Arnold, Commented Feb 2, 2015 at 2:40
I haven't examined the algorithm that closely. It may be that the last couple of elements are never allocated. But it's typical of queue algorithms to "wrap". The alternatives would be to either run out of new elements entirely when hitting the top or to stop and copy the elements down whenever one was removed from the bottom. — Hot Licks
– Hot Licks, Commented Feb 2, 2015 at 3:22
With a queue of this sort the check to see if a queue has "overrun" itself and is about to "swallow its tail" can be pretty tricky. It's probably the most error-prone part of the design. There are ways to allow all elements to be used, but if not using the last couple simplifies the checks then it's probably a good trade-off. — Hot Licks
– Hot Licks, Commented Feb 2, 2015 at 3:27
If I use ((qu->rear +1)% qu->size) instead of ((qu->rear +2)% qu->size) , I would be able to enqueue 3 items for an array based queue of size 4. So why wrapping is not done using 1 and instead 2 is used? — Arnold
– Arnold, Commented Feb 2, 2015 at 3:44

Arijan · Accepted Answer · 2015-02-02 02:40:59Z

1

Because if (qu->rear+1) % qu->size were used, and an element would be enqueued on a almost full queue, then q->rear would be incremented (this is done in line "qu->rear = ((qu->rear+1)%qu->size);") and you would get a situation where full queue would be indistinguishable from empty queue.

Say queue size it 4 elements, and then you add 4 actual elements, you would end up with "front" pointing to 0th element (as front never changed) and "rear" would again point to 0th element as "rear" was incremented 4 times and at the last increment it wrapped back to 0. As in this case front and rear point to 0th element which is the same as at the beginning when queue was empty you cannot tell if queue is full or empty, which is a problem (sometimes).

This code could be changes slightly to reflect the fact that queue size parameter when setting up the queue does not mean that you created a queue of size N but rather a queue of size N-1....

answered Feb 2, 2015 at 2:40

Arijan

1731 silver badge6 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Arnold Over a year ago

Thanks, So with above logic I could enqueue 3 items for size of 4? if yes , when my second item is enqueued the rear value is 2 , now if I go on to insert 3 item , this condition will not be satisfied - if ( qu->front != ((qu->rear +2)% qu->size) ) , thus only 2 elements could be added, I am right?

Collectives™ on Stack Overflow

logic of array based queue in C

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related