Circular Queue using Linked List

Question

I want to create a circular queue using linked list,also i want to create instance of that data structure(queue) not just one queue, many queues without repeating the code. this is what i came up with...

#include <stdio.h>
#include <stdlib.h>
struct queue
{
    int info;
    struct queue *next;
    struct queue *front;
    struct queue *rear;
};
void create(struct queue **q)
{
    (*q)->next = 0;
    (*q)->front = 0;
    (*q)->rear = 0;
}
struct queue* makenode(int item){
    struct queue* p = (struct queue*)malloc(sizeof (struct queue));
    if (p) p->info = item;
    return p;
}
void addLast(struct queue **q, int item){
    struct queue* p = makenode(item);
    if ((*q)->front == NULL){

        (*q)->front = (*q)->rear = p;
        (*q)->front->next = (*q)->front;
        (*q)->rear->next = (*q)->rear;
    }
    else
    {
        (*q)->rear->next = p;
        p->next = (*q)->front;
        (*q)->rear = p;
    }
}
int delFirst(struct queue **q){

    struct queue *p = (*q)->front;

    if ((*q)->front == 0)
        printf("\nEmpty Queue\n");
    else
    {

        int temp = (*q)->front->info;
        if (((*q)->front->next) != ((*q)->front))
        {
            (*q)->front = (*q)->front->next;
            (*q)->rear->next = (*q)->front;
        }
        else
        {
            (*q)->front = 0;
        }
        return temp;
    }
    free(p);
}
void main()
{
    struct queue *premium, *normal;
    create(&premium);
    create(&normal);
    addLast(&premium, 5);
    addLast(&premium, 10);
    addLast(&normal, 20);
    addLast(&normal, 30);
    printf("%i\n", delFirst(&premium));
    printf("%i\n", delFirst(&premium));
    delFirst(&premium);
    printf("%i\n", delFirst(&normal));
    printf("%i\n", delFirst(&normal));
    delFirst(&normal);
    getch();
}

Is there any good way to do this? I kinda feel my code is complicated. I am new to C programming and I only learned basics about queues and linked list.so i don't know even my code is 100% right or an elegant code. I compiled this code using DevC++ works fine, but when I compile it using MS Visual Studio 2013, it gave me an exception "Access violation writing location....”. so i am very sure my code is not that good. Please help me out. Thanks

Answer 1

Problem 1: data structure

You have one structure that contains both the linked list item (info and next element) and the queue structure (front and rear, which should be the same for all elements.

I'd suggest to use:

struct queue_item
{
    int info;
    struct queue_item *next;
};
struct queue
{
    struct queue_item *front;
    struct queue_item *rear;
};

Problem 2: queue creation

When you call create(), the pointer which address you pass (for example premium) is not yet initialized. It can point anywhere ! Most certainly to an invalid location. It doesn't point to a queue yet. So when you do things like (*q)->next = 0;, you try to overwrite an illegal location.

With the data structure proposed above, I propose the following :

struct queue* create (struct queue *q)  /* q points to a queue already allocated, or it is NULL */ 
{
    if (q==NULL) 
       q = malloc(sizeof (struct queue)); 
    if (q) {
        q->front = 0;
        q->rear = 0;
    }
    return q; 
}

In main() you'd then have the choice:

struct queue *premium, normal;
premium = create(NULL);  /* allocate the queue structure */
create(&normal);         /* use an allocated structure */

Problem 3: Node pointers not initialized at node creation

malloc() does not initialize the memory it returns. If you do'nt initialize the link pointer(s), these may in fact contain something else than NULL.

struct queue_item* makenode(int item){
    struct queue* p = (struct queue_item*)malloc(sizeof (struct queue_item));
    if (p) {
        p->info = item;
        p->next = NULL;   /* There is no link yet, so make it clear to avoid any surprises later. */
    }
    return p;
}

Problem 4: Inconsistencies when adding/deleting items

With the new data structure, you'll have to adapt your addLast() and delFirst(). But it'll be clearer, because front and rear are at the level of the queue, and next is only at the level of the item.

From the signature, it'll be posible to avoid double indirection because the pointer to the queue will never be changed by these operations:

void addLast(struct queue *q, int item);      
int delFirst(struct queue *q);