Circular Queue Basics

What is Circular Queue?

The Circular Queue is the Extention of a queue that is a linear user-defined data structure. The circular queue is often used in situations where elements can be added to or removed from the queue at any point in a program, rather than following a predetermined enqueue or dequeue order.

A circular queue is often used in embedded systems to manage memory. It is also utilized in the process management of real-time operating systems (RTOS) for scheduling.

A circular queue typically includes four main functions:

1. Checking if the queue is empty
2. Checking if the queue is full
3. Adding an element to the queue (enqueue)
4. Removing an element from the queue (dequeue)

This code is an implementation of a circular queue in C. The circular queue is a data structure that behaves like a queue but has a fixed size and wraps around when the end of the queue is reached.

The circular queue is defined using a struct called CircularQueue, which has an array data to store the elements, and two pointers front and end to keep track of the front and end of the queue. The init_circular_queue function initializes the queue by setting the front and end pointers to -1 and clearing the data array.

The is_queue_full function checks if the queue is full by checking if the front pointer is at the beginning of the array and the end pointer is at the end of the array, or if the end pointer is just before the front pointer (which indicates that the queue has overlapped). The is_queue_empty function checks if the queue is empty by checking if the front pointer is -1.

The add_element_in_queue function adds an element to the queue by first checking if the queue is full. If the queue is not full, it updates the end pointer to the next index (using modulo arithmetic to wrap around to the beginning of the array if necessary) and stores the element at that index. The remove_element_from_queue function removes an element from the queue by first checking if the queue is empty. If the queue is not empty, it updates the front pointer to the next index (using modulo arithmetic to wrap around to the beginning of the array if necessary).

The print_full_queue function is a helper function that prints the entire contents of the queue.

Finally, the main function initializes the circular queue using init_circular_queue and then adds elements to it using add_element_in_queue and prints the full queue using print_full_queue. It adds 14 elements to the queue (the size of the queue is 5), which causes the circular queue to wrap around and overwrite the oldest elements in the queue.

#include <stdio.h>
#include <stdint.h>

/* 
 * Size of Queue in Bytes
 */
#define SIZE_OF_QUEUE_IN_BYTES       5

/*
 * Structure holds the circular queue
 */
typedef struct CircularQueue {
    char data[SIZE_OF_QUEUE_IN_BYTES];
    int front;
    int end;
} CircularQueue;

/*
 * Global variable holding instance of the circular queue
 */
CircularQueue Circular_Queue;

void init_circular_queue(CircularQueue * queue) {
    queue->front = -1;
    queue->end   = -1;
    for(int idx = 0; idx < SIZE_OF_QUEUE_IN_BYTES; idx++) {
        queue->data[idx] = 0;
    }    
}

/*
 * There are two ways to find out if the circular queue is full.
 * 1) If linearly the queue is full with no overlap
 * 2) If the circular queue has overlapped. 
 */
bool is_queue_full(CircularQueue queue) {
    if(((queue.front == 0) && (queue.end == SIZE_OF_QUEUE_IN_BYTES)) ||
        (queue.front == queue.end + 1)) {
        return true;
    }
    return false;
}

/*
 * Simply by making sure with a placeholder value (-1) if the queue is empty. 
 */
bool is_queue_empty(CircularQueue queue) {
    if(queue.front == -1) {
        return true;
    }
    return false;
}

bool add_element_in_queue(CircularQueue * queue, int data) {
    if(is_queue_full(*queue) == false) {
        if(queue->front == -1) {
            queue->front = 0;
        }
        queue->end = (queue->end + 1) % SIZE_OF_QUEUE_IN_BYTES;
        queue->data[queue->end] = data;    
        return true;
    }
    return false;
}

bool remove_element_from_queue(CircularQueue * queue) {
    if(is_queue_empty(*queue) == false) {
        if(queue->front == queue->end) {
            queue->front = -1;
            queue->end   = -1;
        } else {
            queue->front = (queue->front + 1) % SIZE_OF_QUEUE_IN_BYTES;
        }
        return true;
    }
    return false;
}

void print_full_queue(CircularQueue queue) {
    for(int idx = 0; idx < SIZE_OF_QUEUE_IN_BYTES; idx++) {
        printf("%d ", queue.data[idx]);
    }
    printf("\n");
}

int main()
{
    init_circular_queue(&Circular_Queue);
    for(int idx = 1; idx < 15; idx++) {
        add_element_in_queue(&Circular_Queue, idx);
        print_full_queue(Circular_Queue);
    }
    return 0;
}