C Queue Char Array

Question

I'm trying to create a Queue in C which can take in strings as its value.

I have referenced the code from http://www.thelearningpoint.net/computer-science/data-structures-queues--with-c-program-source-code

I am trying to change the input and output of the functions from int to char array (since i'm storing strings).

However I'm new to C and not able to solve the errors present in 2 parts of the code:

In Enqueue function: strcpy(Q->elements[Q->rear], p);

In Front function: return Q->elements[Q->front];

The error message given was incompatible type char to char*

#include <stdio.h>
#include <stdlib.h>
#include <Windows.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)
  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;
        char **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 = (char**)malloc(sizeof(char*)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}

void Dequeue(Queue *Q)
{
        if(Q->size!=0)
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}

char* front(Queue *Q)
{
        if(Q->size!=0)
        {
                /* Return the element which is at the front*/
                return Q->elements[Q->front];
        }
        return NULL;
}

void Enqueue(Queue *Q,char *element)
{
        //char *p = (char *) malloc(strlen(element)+1);

        /* 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 */ 
                strcpy(Q->elements[Q->rear], element);
        }
        return;
}

int main()
{
        Queue *Q = createQueue(5);
        Enqueue(Q,"test");  // now runtime fails at this line
        Enqueue(Q,"test");
        Enqueue(Q,"test");
        Enqueue(Q,"test");
        printf("Front element is %s\n",front(Q));
        Enqueue(Q,"test");
        Dequeue(Q);
        Enqueue(Q,"test");
        printf("Front element is %s\n",front(Q));
        Sleep(10000);
}

I'm not sure how to change it to store and print out the string. Help appreciated!

Answer 1

U forget to allocate Q->elements[Q->rear]

void Enqueue(Queue *Q , char *element)
{
        //char *p = (char *) malloc(strlen(element)+1);

        /* 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 */ 

                //printf("testing\n");

                Q->elements[Q->rear] = (char *) malloc((sizeof element + 1)* sizeof(char));

                strcpy(Q->elements[Q->rear], element);
        }
        return;
}

Now It is working.

Answer 2

You've implemented a queue that stores char values.

In C, a string is a char *, which is a pointer to a sequence of contiguous char values ending in a \0.

If you want to store strings, your elements array should be a char **, which is a pointer to a pointer to char. This is the normal way in C to refer to dynamically allocated array of pointers.

/* Allocate an array of 10 "char *" values.  NOTE: we're taking sizeof
   a char * NOT a char. */
char **entries = malloc(sizeof(char*) * 10);

For copying the strings, take a look at strdup. It does the same thing as strlen + malloc + strcpy, but using one call instead of 3.

Also, make sure you free the the strings when you're done with them. You could either 1) make Dequeue free the string, in which case the user of the queue must be made aware that the pointer returned by front is invalidated after calling Dequeue, or 2) Leave the responsibility on the end user to free whatever front returns. I tend to prefer my C queues have a pop/dequeue operation that returns the front AND removes it from the queue in a single call, though what you've done approximates the way C++ STL containers work, which may be the goal..