# My Queue implementation is correct?

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 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;
}

int DEQUEUE(struct queue* p) {
printf("\nQUEUE IS EMPTY!!");
return -1;
}
else
printf("\n%d data is removed",x);
return x;
}
void SHOWQUEUE(struct queue* p) {
int i = 0;
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->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);
*/
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;
}

• 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. – Marc-Andre Apr 19 '16 at 13:05
• 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. – Eric Lippert Apr 20 '16 at 0:06

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

struct queue {
int array[MAX];
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) {
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));


Q = malloc(sizeof(struct queue));


6 Don't do this:

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


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 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->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;
}

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.

• #2 unclear: Why not simply (with size field) if(p->tail == MAX-1) { printf("\nQUEUE IS FULL!! ...? – chux - Reinstate Monica Apr 19 '16 at 13:27
• #5 IMO: Q = malloc(sizeof *Q); is even more idiomatic, easier to code and maintain. – chux - Reinstate Monica Apr 19 '16 at 13:29
• 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. – chux - Reinstate Monica Apr 19 '16 at 13:33