Circular Queue using Array in C Programming

Let us consider a scenario, where the rear pointer is pointing to the last element of the queue and the front pointer is pointing to some element that is not the first element. It clearly says that the queue is not full. But there are some free spaces at the front of the queue. In this context, if a new element needs to be inserted in the conventional queue, all the elements need to be shifted towards to front side, Then the new element can be added to the queue. This shifting is a costly operation (i.e. O(n)). This cost can be reduced in Circular Queue.

---

Implementation of Circular Queue using Array

---

#define SIZE 5

typedef struct Queue {
	int front, rear;
	int data[SIZE];
} queue;

void createQueue(queue *q)
{
	q->front = -1;
	q->rear = -1;
}

int isEmpty(queue *q)
{
	if(q->front == -1)
		return 1;
	else
		return 0;
}

int isFull(queue *q)
{
	if(((q->front == 0) && (q->rear == SIZE - 1))||(q->front == q->rear + 1))
		return 1;
	else
		return 0;
}

void enqueue(queue *q, int data)
{
	if(q->front == -1)
	{
		q->front = q->rear = 0;
	}
	else 
		q->rear = (q->rear + 1) % SIZE;
	q->data[q->rear] = data;
}

int dequeue(queue *q)
{
	int data;
	data = q->data[q->front];
	if(q->front == q->rear)
	{
		q->front = q->rear = -1;
	}
	else
		q->front = (q->front + 1) % SIZE;
	return data;
}

Source code

#include <stdio.h> #include <stdlib.h> #define SIZE 5 typedef struct Queue { int front, rear; int data[SIZE]; } queue; void createQueue(queue *q); int isFull(queue *q); int isEmpty(queue *q); void enqueue(queue *q, int data); int dequeue(queue *q); int main(void) { int choice, data; queue q; createQueue(&q); while(1) { printf("\nChoices:"); printf("\n 1: enqueue"); printf("\n 2: dequeue"); printf("\n 0: exit"); printf("\nEnter your choice:"); scanf("%d", &choice); switch(choice) { case 1: if(isFull(&q)) printf("The queue is full!\n"); else { printf("\nEnter an element:"); scanf("%d", &data); enqueue(&q, data); } break; case 2: if(isEmpty(&q)) printf("The queue is empty!\n"); else { data = dequeue(&q); printf("\nThe dequeued element is :%d", data); } break; case 0: exit(0); default: printf("\nInvalid choice"); } } } void createQueue(queue *q) { q->front = -1; q->rear = -1; } int isEmpty(queue *q) { if(q->front == -1) return 1; else return 0; } int isFull(queue *q) { if(((q->front == 0) && (q->rear == SIZE - 1))||(q->front == q->rear + 1)) return 1; else return 0; } void enqueue(queue *q, int data) { if(q->front == -1) { q->front = q->rear = 0; } else q->rear = (q->rear + 1) % SIZE; q->data[q->rear] = data; } int dequeue(queue *q) { int data; data = q->data[q->front]; if(q->front == q->rear) { q->front = q->rear = -1; } else q->front = (q->front + 1) % SIZE; return data; }

Happy Exploring!