Creating a queue with structs in C

Question

I have a code (at the end of this post) that implements a circular queue system. Everything works perfectly, but as can be seen in the function createQueue the queue is implemented only for integers. I would like to modify this code to accept a struct informed by the user.

I could create a known struct and replace all sites with integer, but this way I would be coupling the code to a known struct. Bad idea...

How could pass to the function createQueue a struct for memory allocation without needing to know the struct previously? The struct Queue should also be changed, in int *elements the value should be changed from integer to void?

#include 
#include 

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;

Queue * createQueue(int maxElements)
{
        /* Create a Queue */
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        /* Initialise its properties */
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}
void Dequeue(Queue *Q)
{
        /* If Queue size is zero then it is empty. So we cannot pop */
        if(Q->size==0)
        {
                printf("Queue is Empty
");
                return;
        }
        /* Removing an element is equivalent to incrementing index of front by one */
        else
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty
");
                exit(0);
        }
        /* Return the element which is at the front*/
        return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full
");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                /* As we fill the queue in circular fashion */
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                /* Insert the element in its rear side */ 
                Q->elements[Q->rear] = element;
        }
        return;
}
int main()
{
        Queue *Q = createQueue(5);
        Enqueue(Q,1);
        Enqueue(Q,2);
        Enqueue(Q,3);
        Enqueue(Q,4);
        printf("Front element is %d
",front(Q));
        Enqueue(Q,5);
        Dequeue(Q);
        Enqueue(Q,6);
        printf("Front element is %d
",front(Q));
}

John Bode · Accepted Answer

How much pain do you enjoy?

Jean-François Fabre's method is a good one, and is a fair approximation of using C++ templates. I have another one that avoids using the preprocessor, but it's a lot more work, and is a poor-to-middling approximation of subclassing. I prefer this method to the preprocessor approach, though, mainly because I'm brain-damaged.

We start with your basic Queue type, but instead of storing an array of int, store an array of void *:

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        void **elements; 
        ...
}Queue;

meaning that your Enqueue prototype is going to look like

void Enqueue( Queue *Q, void *element )

Now, as soon as we use void *, we have problems - we've thrown type safety out the window, and we don't really know what the pointed-to data is supposed to look like. Secondly, we have to create a copy of whatever input data we get (we can't just write element to the elements list). We also can't use a void * to store scalars like int or float values. So we need to add at least the following type-aware helper functions:

copy - allocates and assigns a copy of the input to Enqueue
destroy - destroys an object removed from the queue

So we add these functions to our Queue type as follows:

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        void *elements;
        void *(*copy)(const void *);
        void (*destroy)(const void *);
}Queue;

So, let's say we want to create a queue to store floats. We create the following helper functions:

void *copyFloat( const void *f )
{
  float *p = malloc( sizeof *p );
  if ( p )
  {
    *p = *(float *) f;
  }
  return p;
}

void destroyFloat( const void *f )
{
  free( f );
}

and then create a new Queue object that uses them:

Queue * createQueue(int maxElements, 
                    void *(*copy)(const void *), 
                    void (*destroy)(const void *),
{
  /* Create a Queue */
  Queue *Q;
  Q = malloc( sizeof *Q );
  /* Initialise its properties */
  Q->elements = malloc(sizeof *Q->elements * maxElements);
  Q->size = 0;
  Q->capacity = maxElements;
  Q->front = 0;
  Q->rear = -1;

  Q->copy = copy;
  Q->destroy = destroy;

  /* Return the pointer */
  return Q;
}
...
Queue *floatQueue = CreateQueue( 100, copyFloat, destroyFloat );

Your Enqueue function now looks like

void Enqueue(Queue *Q, void *element)
{
  /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
  if(Q->size == Q->capacity)
  {
    printf("Queue is Full
");
  }
  else
  {
    Q->size++;
    Q->rear = Q->rear + 1;
    /* As we fill the queue in circular fashion */
    if(Q->rear == Q->capacity)
    {
      Q->rear = 0;
    }
    /* Insert the element in its rear side */ 
    Q->elements[Q->rear] = Q->copy( element ); // <--- create a copy of the input
  }
  return;
}

Why do we need to create the copy? Imagine if you called Enqueue like the following:

float f;
...
f = get_new_value();
Enqueue( &queue, &f );

If we just copied the input parameter element to the queue, we'd be writing the same address to every element of the queue - the address of the variable f. Thus, every element of the queue would be pointing to the same (invalid) thing.

Conversely, when we dequeue an object, we now have to make sure we clean up that memory:

void Dequeue(Queue *Q)
{
  /* If Queue size is zero then it is empty. So we cannot pop */
  if(Q->size==0)
  {
    printf("Queue is Empty
");
    return;
  }
  /* Removing an element is equivalent to incrementing index of front by one */
  else
  {
    Q->destroy( Q->elements[Q->front] ); // deallocate the dequeued object
    Q->size--;
    Q->front++;
    /* As we fill elements in circular fashion */
    if(Q->front==Q->capacity)
    {
      Q->front=0;
    }
  }
  return;
}

And your front function now returns a void *:

void *front(Queue *Q)
{
  if(Q->size==0)
  {
    printf("Queue is Empty
");
    exit(0);
  }
  /* Return the element which is at the front*/
  return Q->elements[Q->front];
}

We're not done yet - to make this work, we still need a type-aware front end:

void EnqueueFloat( Queue *floatQueue, float f )
{
  Enqueue( floatQueue, &f );
}

float frontFloat( Queue *floatQueue )
{
  float *p = front( floatQueue );
  return *p;
}

What a mess.

But...

Once you have the basic queue mechanics in place, all you need to do is implement new copy and destroy functions for each new type you want to use, along with a new type-aware front end. You don't have to create a whole new Queue_XXX data type for each data type, nor to you need to create whole new copies of Enqueue_XXX and front_XXX and Dequeue_XXX; you only need to implement a thin, type-aware wrapper for each.

There are doubtless many ways to improve what I've written; there are ways to avoid allocating a deallocating a copy for every input, but then indexing into the queue becomes a little less clean.

Anyway, it's just food for thought.

Creating a queue with structs in C

Answers (2)

Related Questions