Creating a queue with structs in C

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\n");
  }
  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\n");
    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\n");
    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.