Circular Queue Implementation

Question

The below circular queue implementation is from a data structures book.

struct circqueue {
   int front,rear;
   int capacity;
   int *array;
};




struct circqueue *q(int size) {
   struct circqueue *q=malloc(sizeof(struct circqueue));
   if(!q)return NULL;
   q->capacity=size;
   q->front=-1;
   q->rear=-1;
   q->array=malloc(q->capacity*sizeof(int));
   if(!q->array)return NULL;
  return q;
}

int isemptyqueue(struct circqueue *q) {
   return(q->front==-1);
}

int isfullqueue(struct circqueue *q) {
   return((q->rear+1)%q->capacity==q->rear);
}

int queuesize(struct circqueue *q) {
   return(q->capacity-q->rear+q->front+1)%q->capacity;
}


void enqueue(struct circqueue *q,int x) {

   if(isfullqueue(q))
      printf("queue overflow\n");
   else{
      q->rear=(q->rear+1)%q->capacity;
      q->array[q->rear]=x;
      if(q->front==-1) {
         q->front=q->rear;
      }
   }
}

int dequeue(struct circqueue *q) {
   int data=0;

   if(isemptyqueue(q)) {
      printf("queue underflow");
      return 0;
   }
   else {
      data=q->array[q->front];
      if(q->front==q->rear)
         q->front=q->rear=-1;
      else
         q->front=(q->front+1)%q->capacity;
   }

   return data;
}

I have not been able to understand the precise use of struct circqueue *q(int size)? Is it a function to initialize the queue? Also how to invoke it from main()? Can anybody explain it to me.Thanks

Solution 1

struct circqueue* q(int size)
{
    struct circqueue *q=malloc(sizeof(struct circqueue));
    if(!q)
        return NULL;
    q->capacity=size;
    q->front=-1;
    q->rear=-1;
    q->array=malloc(q->capacity*sizeof(int));
    if(!q->array)
       return NULL;
    return q;
}

Taking line by line.

1) function q takes maximum size of queue as parameter and returns a queue object (a C struct).

3) store struct on the heap, set q to reference this memory location

4) if memory allocation fails return a suitable non-success message.

6) populate circqueue capacity with maximum size value used by caller.

7) and 8) internal indices for position of 'push' and 'pop'.

9) allocate heap memory for array which is used internally for storage.

10) A bit like 4)

12) return constructed object to caller.

To create a queue which can hold up to 100 integers do this:

struct circqueue* num_q = q(100);

/* Add an integer */
enqueue(num_q, 3);

Solution 2

Yes, it initializes an instance of the struct circqueue and gives you the pointer:

int main()
{
    struct circqueue *queue = q( 10 );

    // do stuff with queue

    free( queue->array );
    free( queue );
}