Very basic Integer queue in C

Question

I've never written a queue before and literally just took the concepts and tried to code something up. I decided to write a basic integer queue and as an example/driver I use a queue of size 5 which implements insert(), delete(), and display().

Please critique these implementations and comment if there should be any additions or modifications. The reason for the simplicity is that I'm mostly concerned that I got the concepts correct at this point. This is not the most robust queue by any means.

#include <stdio.h>
#include <stdlib.h>

#define ERR(msg) fprintf(stderr, "%s\n", msg)
#define QUEUE_SIZE 5

static size_t const front = 0;
static size_t rear = 0;

int queue[QUEUE_SIZE];

int insert(int num);
int delete(void);
void display(void);

int main(void)
{
    insert(5);
    insert(8);
    insert(58);
    insert(9);
    insert(10);
    display();
    delete();
    display();
    delete();
    display();
    delete();
    display();
    delete();
    display();

    return EXIT_SUCCESS;
}

int insert(int num)
{
    if((rear + 1) > QUEUE_SIZE)
    {
        ERR("Queue full, cannot insert item.");
        return -1;
    }
    queue[rear++] = num;
    return 0;
}

int delete(void) // Deletes the front one
{
    if(rear == front)
    {
        ERR("Cannot delete from empty queue.");
        return -1;
    }

    size_t i;

    for(i = front; (i+1) < QUEUE_SIZE; i++)
    {
        queue[i] = queue[i+1];
    }
    rear--;
    return 0;
}

void display(void)
{
    size_t i;
    for(i = front; i < rear; i++)
    {
        printf("%d\t", queue[i]);
    }
    putchar('\n');
    return;
}

Answer 1

The delete function is not right. It is very non-optimal to shift every item by one index after each deletion. Imagine the queue has 1 million items and the deletion of front element is needed.

From Wikipedia:

Fixed length arrays are limited in capacity, but it is not true that items need to be copied towards the head of the queue. The simple trick of turning the array into a closed circle and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in the array. If n is the size of the array, then computing indices modulo n will turn the array into a circle.

So, you should use a Circular buffer.

This video has a good explanation of queue and circular buffer: Data structures: Array implementation of Queue.

Answer 2

Algorithm
As @MinMax pointed out there are limitations to Queue implementations using arrays.

I would personally use a linked list to implement a queue rather than an array. The only size limit on the queue implemented with a linked list is how much memory can be allocated. The front of a queue implemented using a linked list can be deleted. There doesn't have to be a rear variable for a linked list, although it does speed up adding items to the queue.

Rather than using the terms insert and delete you might want to use enqueue and dequeue.

Global Variables
This implementation of a queue uses global variables for everything. As programs get larger and more complex global variables make writing and modifying the code more error prone and they are harder to debug because one has to find every instance of the use of the global variable. Global variables can also cause linking problems when the variables are declared in multiple files and used differently in those files.

A better practice would be to declare the variable in a function and then pass the variable by reference to any other functions that need to modify it.

Answer 3

Possibly unneeded variable

I don't think this variable is needed:

static size_t const front = 0;

Just using the constant 0 may or may not be clearer.

Slight refactoring of comparisons

Instead of doing:

if((rear + 1) > QUEUE_SIZE)

I suggest

if(rear >= QUEUE_SIZE)

and similarly for:

(i+1) < QUEUE_SIZE

which can be replaced by:

i < (QUEUE_SIZE-1)

This is clearer and easier to read.

delete is a reserved keyword in C++

If you plan on this library being used in C++, you may want to know that delete is a reserved keyword. You can change this function name to something like unqueue or something that's not reserved. However, I strongly suggest you don't use this in C++; std::queue is a better, faster option.

Faster copying

Instead of using this construct:

size_t i;

for(i = front; (i+1) < QUEUE_SIZE; i++)
{
    queue[i] = queue[i+1];
}

you could probably use memmove:

memmove(queue, queue+1, sizeof(*queue)*(QUEUE_SIZE-1));

This could probably provide a minimal speed benefit.

Some good things that you have done

Good job on not using printf where you don't need it. I find a lot of programmers unnecessarily using printf("\n"); when they could've just used putchar('\n').