Circular Queue using Linked List

Question

I want to create a circular queue using a linked list. I also want to create many instances of that data structure (queue) 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 a better way to do this? I feel that my code is complicated. I am new to C programming and I only learned basics about queues and linked list. I don't know even my code is 100% right or an elegant code.

I compiled this code using DevC++ and it works fine, but when I compile it using MS Visual Studio 2013, it gave me an exception:

Access violation writing location....

I am very sure my code is not that good.

Answer 1

Here are some things that may help you improve your code.

Fix the return type for main

Unless you're working on an "unhosted" system (e.g. an embedded microcontroller), main should be declared as returning int and not void.

Update: As pointed out by @TimČas in a comment:

Actually, main should be declared as int even in freestanding/unhosted (the C99 standard demands that compiler supports it; they are free to allow others, but the int version must be allowed")

The implication, of course, is that even if you're writing for an embedded system, unless you have a very old or noncompliant compiler, you should still use int as the return type for main.

Prefer standard functions

The main() function uses getch() but that's not actually standard. Instead, you could use getchar() which is standard and will allow this code to work on any platform.

Always return an appropriate value

Your delFirst() routine has control paths that cause it to end without returning any int value. This is an error and should be fixed.

Be careful with memory pointers

This code declares two pointers, premium and normal and then calls create which dereferences those uninitialized pointers. That is not going to work. Whenever you dereference a pointer, you should ask yourself "can this pointer possibly be NULL?" and "is this pointer actually pointing to something?" In this case, the pointers are not pointing to anything because they have not been set to any particular value. Instead, you should call your makenode function instead, which actually allocates memory, and then initialize the members.

Combine allocation and initialization

The code currently has two separate functions: makenode and create both of which do part of the job of allocation and initialization. Better would be to combine the two so that the a node is both allocated and initialized. In C++ this is typically called RAII which stands for "Resource Acquisition Is Initialization" and it simply means that once you have a thing (a struct in this case), it's fully usuable.

Use single pointers where practical

In both your addLast and delFirst routines, the first parameter should be struct queue *q (with a single *) instead of what it currently has which is a **q. That simplifies the rest of the code where you can replace every instance of (*q) with simply q.

Check for NULL pointers

The code inside makenode correctly avoid dereferencing a NULL pointer if the call to malloc fails, but addLast does not check p before dereferencing it. It should also check q to make sure that's not NULL either.

Consider separating the queue from the linked list

Each of the nodes in a linked list needs a next pointer, but not front or rear pointers. Really, you only need one front and one rear pointer per queue and then just info and next per node. You might consider creating separate node and queue structs for that reason.

Don't mix I/O with data operations

Generally speaking having a printf within a data manipulation function such as delFirst is not a good idea. It makes it harder to reuse the function. It's OK for diagnostics and for troubleshooting, but it would be better to omit it from the final version.

• Mike: i really appreciate your detailed answer. now I understand where I got wrong. thank you very much.
• Tim Čas: Actually, main should be declared as int even in freestanding/unhosted (the C99 standard demands that compiler supports it; they are free to allow others, but the int version must be allowed; C89 doesn't allow others at all, AFAIK). That said some C compilers for embedded systems are not compliant here, and demand void --- not allowing int, even though the standard requires that they do.
• Edward: @TimČas: Thanks! I've updated my answer to include this point.
• Tim Čas: @Edward: Small addition: I've recently started using two compilers which do the opposite things here, so I do a #define MAIN_RETURN_TYPE int and #define MAIN_RETURN return 0 ... then I do MAIN_RETURN_TYPE main() { for(;;) { ... } MAIN_RETURN; }. I originally had just the value (0), but one of the compilers complained about the dead code for return;, so this allows an empty statement. Another alternative would be a thin wrapper (e.g. void app_main() { ... }, where main() is defined in the lib and calls app_main()).