3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Did you test whether it works as intended? \$\endgroup\$ – Mast May 12 '16 at 17:06
  • \$\begingroup\$ Im sorry. I didn't try compile it... next time I would. \$\endgroup\$ – kidkkr May 13 '16 at 0:59
1
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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