My Queue implementation is correct?

Question

I have read CLRS Introduction to Algorithms book, now I'm on Elementary data structure chapter. I read about queue concept and try to implement in c. I have tested a lot it work fine, but I have a little doubt on its working. Please tell me this implementation is correct or not.

#include <stdio.h>
#include <stdlib.h>
#define MAX 4
struct queue {
 int array[MAX];
 int head;
 int tail; 
};
void ENQUEUE(struct queue* p,int data) {
// error checking for overflow
 if((p->tail == MAX-1 && p->head == 0 ) || (p->head == p->tail+1)) {
 printf("\nQUEUE IS FULL!! ");
 return;
 }
 p->array[p->tail] = data; 
 if(p->tail == MAX-1)
 p->tail = 0;
 else
 p->tail = p->tail+1;
 printf("\n%d data is added",data);
}
int DEQUEUE(struct queue* p) {
 if(p->head == p->tail) {
 printf("\nQUEUE IS EMPTY!!");
 return -1;
 }
 int x = p->array[p->head];
 if(p->head == MAX-1)
 p->head = 0;
 else
 p->head = p->head+1;
 printf("\n%d data is removed",x);
 return x;
}
void SHOWQUEUE(struct queue* p) {
 int i = 0;
 i = p->head;
 printf("p->head = %d & p->tail = %d",p->head,p->tail);
 printf("\nQUEUE ELEMENTS:");
 while(i != p->tail) {
 printf("%d ",p->array[i]);
 if(i == (MAX-1)) 
 i = 0;
 else
 i = i+1;
 }
}
int main() {
 struct queue* Q;
 Q = (struct queue*) malloc(sizeof (struct queue));
 if(Q == NULL) {
 printf("Memory allocation failed");
 return -1;
 }
 Q->head = 1;
 Q->tail = 1; 
/* ENQUEUE(Q,1);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 ENQUEUE(Q,1);
 ENQUEUE(Q,1);
 SHOWQUEUE(Q);
 ENQUEUE(Q,1);
 ENQUEUE(Q,1);
 ENQUEUE(Q,1);
 SHOWQUEUE(Q);
 printf("head = %d & tail = %d ",Q->head,Q->tail);
*/
 ENQUEUE(Q,98);
 ENQUEUE(Q,20);
 ENQUEUE(Q,16);
 ENQUEUE(Q,2);
// ENQUEUE(Q,1);
// ENQUEUE(Q,2);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 ENQUEUE(Q,5);
 SHOWQUEUE(Q);
 ENQUEUE(Q,3);
 SHOWQUEUE(Q);
 ENQUEUE(Q,10);
 SHOWQUEUE(Q); 
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 ENQUEUE(Q,12);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 ENQUEUE(Q,2);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 ENQUEUE(Q,1);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 DEQUEUE(Q);
 SHOWQUEUE(Q);
 return 0;
}

• Marc-Andre: When you say but I have a little doubt on its working what you mean by you doubt it's working ? Is it throwing exceptions ? Is one of the operation failing ? Normally broken code is off-topic for Code Review.
• Eric Lippert: If you have doubts about its correctness then maybe you should write two or three additional test cases. Or two or three million additional test cases; you could write a program that writes test cases. Whatever it takes to make you feel like its correct.

Answer 1

1 It would be more natural to have a field size instead of tail:

struct queue {
 int array[MAX];
 int head;
 int tail; 
};

2 If you had size field, checking whether the queue is empty or full would be a simple one-liner.

 if((p->tail == MAX-1 && p->head == 0 ) || (p->head == p->tail+1)) {
 printf("\nQUEUE IS FULL!! ");
 return;
 }

3 It's not cool to print from algorithms unless debugging.

int DEQUEUE(struct queue* p) {
 if(p->head == p->tail) {
 printf("\nQUEUE IS EMPTY!!");
 return -1;
 }

4 Can make the output of this more pretty.

void SHOWQUEUE(struct queue* p) {
 ...
}

5 The convention is not to prepend malloc with a type.

Q = (struct queue*) malloc(sizeof (struct queue));

Instead, do this

Q = malloc(sizeof(struct queue));

6 Don't do this:

Q->head = 1;
Q->tail = 1; 

Instead, you should write the function that initializes your queue.

7 Above, it's funny that you start indexing from 1.

Summa summarum

You could consider something like the following:

queue.h:

#ifndef QUEUE_H
#define QUEUE_H
#include <stdbool.h>
#include <stdlib.h>
#define CAPACITY 10
typedef struct queue {
 int storage[CAPACITY];
 size_t head;
 size_t size;
} queue;
void queue_init(queue* q);
bool queue_enqueue(queue* q, int element);
int queue_dequeue(queue* q);
void queue_print(queue* q);
#endif

queue.c

#include "queue.h"
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
void queue_init(queue* q)
{
 if (!q) 
 {
 return;
 }
 q->head = 0;
 q->size = 0;
}
bool queue_enqueue(queue* q, int element)
{
 if (!q || q->size == CAPACITY)
 {
 return false;
 }
 q->storage[(q->head + q->size++) % CAPACITY] = element;
 return true;
}
int queue_dequeue(queue* q)
{
 if (!q || q->size == 0)
 {
 return 0;
 }
 int ret = q->storage[q->head];
 q->head = (q->head + 1) % CAPACITY;
 q->size--;
 return ret;
}
void queue_print(queue* q)
{
 if (!q)
 {
 printf("null");
 return;
 }
 printf("[");
 for (size_t i = 0, index = q->head; i < q->size; ++i)
 {
 printf("%d", q->storage[index]);
 if (i < q->size - 1)
 {
 printf(", ");
 }
 index = (index + 1) % CAPACITY;
 }
 printf("]");
}

main.c:

#include "queue.h"
#include <stdio.h>
int main() {
 queue q;
 queue_init(&q);
 for (int i = 0; i < 5; ++i)
 {
 queue_enqueue(&q, i);
 }
 for (int i = 0; i < 10; ++i)
 {
 queue_print(&q);
 puts("");
 queue_enqueue(&q, queue_dequeue(&q));
 }
 return 0;
}

Hope that helps.

• chux: #2 unclear: Why not simply (with size field) if(p->tail == MAX-1) { printf("\nQUEUE IS FULL!! ...?
• chux: #5 IMO: Q = malloc(sizeof *Q); is even more idiomatic, easier to code and maintain.
• chux: A test of if (!q) in queue_init(queue* q) would make it symmetric with other functions. Unclear why missing here and used in the other 3.