Implementation of ANSI C queue

Question

I have a code (end of question) that allows manipulation of a queue in ANSI C, my question is as follows: The code declares a data type of its own to store the data of the queue and has a function to create a queue, however it uses in the whole example, but I wanted to use a custom struct. How could I change the code to allow the use of a custom struct?

Remembering that the struct is unknown by the code, I would not like to have to dock this struct in the example, because this way whenever I create a queue for a particular struct I would have to change the queue manipulation code.

I believe that to solve this I need to touch the struct Queue and change the int *elements; for some kind of data (maybe void*) then allow in function Queue * createQueue(int maxElements) allow the passage of my custom struct so that the code can calculate your sizeof for the malloc, but I have no idea how to do that... some light?

#include<stdio.h>
#include<stdlib.h>
/*Queue has five properties. capacity stands for the maximum number of elements Queue can hold.
  Size stands for the current size of the Queue and elements is the array of elements. front is the
 index of first element (the index at which we remove the element) and rear is the index of last element
 (the index at which we insert the element) */
typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;
/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the 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\n");
                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\n");
                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\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] = 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\n",front(Q));
        Enqueue(Q,5);
        Dequeue(Q);
        Enqueue(Q,6);
        printf("Front element is %d\n",front(Q));
}

Answer 1

For the queue to store generic structures, one possibility is to make the array of elements point to a array pointer-type void ** (to allow deference).

To struct is as follows:

typedef struct Queue
{
  int capacity;
  int size;
  int front;
  int rear;
  void **elements; // trocado para void **
} Queue;

As the queue will store only a set of references (pointers) for the data, the pointer size (sizeof(void *)) is constant (e.g.: 4 bytes for a 32bit pointer), so the function createQueue does not need to know the total size of the data that will be stored.

To store and retrieve the elements, a cast for the corresponding data type (void for Elemento and vice versa).

---

Generic structure of example

  typedef struct {
    int elemento1,
    float elemento2,
    double elemento3
  } Elemento;

Function to allocate a structure

  Elemento *alocaElemento(int p1, float p2, double p3)
  {
    Elemento *ret = (Elemento *) malloc(sizeof(Elemento));
    ret->elemento1 = p1;
    ret->elemento2 = p2;
    ret->elemento3 = p3;
    return ret;
  }

Complete implementation with usage examples:

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

/*Queue has five properties. capacity stands for the maximum number of elements Queue can hold.
  Size stands for the current size of the Queue and elements is the array of elements. front is the
 index of first element (the index at which we remove the element) and rear is the index of last element
 (the index at which we insert the element) */

typedef struct Queue
{
    int capacity;
    int size;
    int front;
    int rear;
    void **elements; // trocado para (void **)
} Queue;

/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the Queue. */
Queue * createQueue(int maxElements)
{
    /* Create a Queue */
    Queue *Q;
    Q = (Queue *)malloc(sizeof(Queue));
    /* Initialise its properties */
    // Aqui, o tamanho de cada elemento é o tamanho de um ponteiro void
    Q->elements = (void *)malloc(sizeof(void *)*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\n");
        return;
    }
    else
    {
        /* Removing an element is equivalent to incrementing index of front by one */       
        Q->size--;
        Q->front++;
        /* As we fill elements in circular fashion */
        if(Q->front==Q->capacity)
        {
            Q->front=0;
        }
    }
    return;
}

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

void Enqueue(Queue *Q, void *element) // trocado para aceitar um ponteiro void
{
    /* 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] = element;
    }
    return;
}

// Elemento "generico"
typedef struct {
    int elemento1;
    float elemento2;
    double elemento3;
} Elemento;

// funcao que aloca um elemento 
Elemento *alocaElemento(int p1, float p2, double p3)
{
    Elemento *ret = (Elemento *) malloc(sizeof(Elemento));
    ret->elemento1 = p1;
    ret->elemento2 = p2;
    ret->elemento3 = p3;
    return ret;
}

int main()
{
    Queue *Q = createQueue(5);
    Elemento *e;

    e = alocaElemento(1, 1.5, 1.5e10);
    Enqueue(Q, (void *) e); // efetua o cast de (Elemento *) para (void *)

    e = alocaElemento(2, 2.5, 2.5e20);
    Enqueue(Q, (void *) e);

    e = alocaElemento(3, 3.5, 3.55e9);
    Enqueue(Q, (void *) e);

    e = alocaElemento(4, 4.5, 4.5e12);
    Enqueue(Q, (void *) e);

    // efetua o cast "contrario" de (void *) para (Elemento *)
    printf("Front element is %f\n",((Elemento *) front(Q))->elemento2); 

    Dequeue(Q); // Retira um elemento da fila

    // efetua o cast "contrario" de (void *) para (Elemento *)
    printf("Front element is %f\n",((Elemento *) front(Q))->elemento2); 

    e = alocaElemento(5, 5.5, 3.112121);
    Enqueue(Q, (void *) e); // insere um novo elemento

    Dequeue(Q); // retira um elemento da fila

    e = alocaElemento(6, 6.0, 2.0);

    Enqueue(Q, (void *) e);

    printf("Front element is %f\n",((Elemento *) front(Q))->elemento3);

    Dequeue(Q); // retira um elemento da fila
    Dequeue(Q); // retira um elemento da fila

    printf("Front element is %f\n",((Elemento *) front(Q))->elemento3);
}

Result after execution:

Front element is 1.500000
Front element is 2.500000
Front element is 3550000000.000000
Front element is 3.112121

---

Obs: it is important to free all the allocated memory during the process (free(...)).

_{Tested with gcc version 6.2.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)}