Array-based queue implementation using C

Question

I wrote this header for generic use of a queue. The one thing I'm wondering is if I understood the usage of void*. I hope that if somebody teach me some conventions when coding in C.

/*
*   array-based queue implementation by using void*
*   written by kidkkr
*   May 6 '16
*/

#ifndef QUEUE_H
#define QUEUE_H
#define QUEUE_CAPACITY 10
#include <stdio.h>

typedef struct {
    void* data[QUEUE_CAPACITY];
    int head;
    int tail;
    int size;
} Queue;

void initQueue(Queue* pQueue)
{
    pQueue->head = 0;
    pQueue->tail = -1;
    pQueue->size = 0;
}

void enqueue(Queue* pQueue, void* item)
{
    if (pQueue->size == QUEUE_CAPACITY) // when queue is full
    {
        printf("Queue is full\n");
        return;
    }
    else
    {
        (pQueue->tail)++;
        (pQueue->tail) %= QUEUE_CAPACITY;
        (pQueue->data)[pQueue->tail] = item;
        (pQueue->size)++;
    }
}

void* dequeue(Queue* pQueue)
{
    // Return NULL when queue is empty
    // Return (void*)item at the head otherwise.
    void* item = NULL;
    if (isEmpty(&pQueue))
    {
        printf("Queue is empty\n");
    }
    else
    {
        item = (pQueue->data)[pQueue->head];
        (pQueue->head)++;
        (pQueue->head) %= QUEUE_CAPACITY;
        (pQueue->size)--;
    }
    return item;
}

int isEmpty(Queue* pQueue)
{
    return pQueue->size == 0;
}

#endif

Answer 1

Your code looks nice and nifty. However, I have a couple of suggestions.

1 I would change the type of head, tail and size from int to size_t.

2

void initQueue(Queue* pQueue)
{
    pQueue->head = 0;
    pQueue->tail = -1;
    pQueue->size = 0;
}

The semantics is that you first update the value of tail and then use it as an index at which you enqueue a new data item. If you specify that you first insert at tail and only after that update it, you effectively get rid of negative value range, i.e., size_t will do just fine.

3 In all functions operating on the queue you should have a sanity check that the input queue pointer is not NULL.

4

void enqueue(Queue* pQueue, void* item)
{
    if (pQueue->size == QUEUE_CAPACITY) // when queue is full
    {
        printf("Queue is full\n");
        return;
    }
    else
    ...

I would #include <stdbool.h> and return true if the enqueuing for successful and false otherwise. Also, it is not funky to print to standard output in a data structure function/algorithm.

5 For debugging purposes you could roll a separate function that neatly prints the contents of your queue.

Summa summarum

All in all, I had this in mind:

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdbool.h>
#include <stdio.h>

#define QUEUE_CAPACITY 10

typedef struct {
    void* data[QUEUE_CAPACITY];
    size_t head;
    size_t tail;
    size_t size;
} Queue;

bool initQueue(Queue* pQueue)
{
    if (!pQueue)
    {
        return false;
    }

    pQueue->head = 0;
    pQueue->tail = 0;
    pQueue->size = 0;
    return true;
}

int isEmpty(Queue* pQueue)
{
    return pQueue && pQueue->size == 0;
}

bool enqueue(Queue* pQueue, void* item)
{
    if (!pQueue || pQueue->size == QUEUE_CAPACITY) // when queue is full
    {
        return false;
    }

    pQueue->data[pQueue->tail] = item;
    pQueue->tail = (pQueue->tail + 1) % QUEUE_CAPACITY;
    pQueue->size++;
    return true;
}

void* dequeue(Queue* pQueue)
{
    // Return NULL when queue is empty
    // Return (void*)item at the head otherwise.
    void* item;

    if (!pQueue || isEmpty(pQueue))
    {
        return NULL;
    }

    item = pQueue->data[pQueue->head];
    pQueue->head = (pQueue->head + 1) % QUEUE_CAPACITY;
    pQueue->size--;
    return item;
}

void debugPrint(Queue* pQueue)
{
    size_t index;
    size_t tmp;

    if (!pQueue)
    {
        printf("null");
        return;
    }

    printf("[");

    if (pQueue->size >= 1)
    {
        printf("%d", (int) pQueue->data[pQueue->head]);
    }

    for (index = 1; index < pQueue->size; ++index)
    {
        tmp = (pQueue->head + index) % QUEUE_CAPACITY;
        printf(", %d", (int) pQueue->data[tmp]);
    }

    printf("]");
}

#endif

main.c

#include "queue.h"

int main(int argc, const char * argv[]) {
    int i;
    Queue q;

    initQueue(&q);

    for (i = 0; i < QUEUE_CAPACITY; ++i)
    {
        debugPrint(&q);
        puts("");
        enqueue(&q, (void*) i);
    }

    for (i = QUEUE_CAPACITY; i < 3 * QUEUE_CAPACITY; ++i)
    {
        debugPrint(&q);
        puts("");
        dequeue(&q);
        enqueue(&q, (void*) i);
    }

    for (i = 0; i < QUEUE_CAPACITY; ++i)
    {
        debugPrint(&q);
        puts("");
        dequeue(&q);
    }

    while (!isEmpty(&q))
    {
        debugPrint(&q);
        dequeue(&q);
    }

    debugPrint(&q);
    return 0;
}

Answer 2

if (isEmpty(&pQueue)) is wrong. It should be pQueue. You also need to have the prototype in scope before you use it. Put int isEmpty(Queue* pQueue) at the top of your file.

Answer 3

If this queue header is to be used in multiple source files, then you should mark all the functions static to avoid multiple-definition errors from the linking stage.

Another option would be to put the functions in a .c file and have just the function prototypes in the header. Then you can use it in multiple places but have only one copy of the functions in the final executable.