1
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Marc-Andre
    Apr 19, 2016 at 13:05
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 20, 2016 at 0:06

1 Answer 1

1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.