Circular Queue implementation in C

A queue is a linear data structure that serves as a collection of elements, with three main operations:

• Enqueue operation, which adds an element to the rear position in the queue.

• Dequeue operation, which removes an element from the front position in the queue.

• Peek or front operation, which returns the front element without dequeuing it or modifying the queue in any way.

The queue is also known as First-In-First-Out (FIFO) data structure considering the order in which elements come off a queue i.e. the first element that is inserted to the queue will be the first one to be removed. Below is simple representation of a FIFO queue –

A queue may be implemented to have a bounded capacity. If the queue is full and does not contain enough space for enqueue operation, then it will result into Queue overflow. When trying to remove an element from an empty queue, Queue underflow will happen.

Circular Queue Implementation using an array –

There are several efficient implementations of FIFO queues. A (bounded) queue can be easily implemented using an array using a five-element structure:

structure queue:
item : array
maxsize : integer
front : integer
rear : integer
size : integer

Since fixed length arrays have limited capacity, we need to convert the array into a closed circle. If n is the size of the array, then computing indices modulo n will turn the array into a circle. Now front and rear can drift around endlessly in that circle that makes it unnecessary to ever move items stored in the array.

C

Output:

Inserting 1 front = 0, rear = 1
Inserting 2 front = 0, rear = 2
Inserting 3 front = 0, rear = 3
Inserting 4 front = 0, rear = 4
Removing 1 front = 1, rear = 4
Removing 2 front = 2, rear = 4
Removing 3 front = 3, rear = 4
Removing 4 front = 4, rear = 4
Inserting 5 front = 4, rear = 0
Inserting 6 front = 4, rear = 1
size = 2
Queue is not empty

The time complexity of enqueue(), dequeue(), front(), isEmpty() and size() operations is O(1).

It is possible to implement a queue that can grow or shrink as much as needed using a dynamic array. For example, using std::vector in C++ or ArrayList in Java.

Applications of a Queue –

1. Breadth First Search (BFS) algorithm

2. Job Scheduling, to maintain a queue of processes in Operating systems (FIFO order)

3. Queue of packets in data communication.

4. Data synchronization, to transfer data asynchronously between two processes

5. Real life applications of queue would be waiting in a line at ticket counter or call waiting for support or vehicles on a one way lane and many more…