Simple Circular Array Representation of Queue is extended version of Simple Array Representation of Queue , but this is also not an efficient and good representation of Queue,because Array size will be fixed. and we have to define this array size at beginning ,and we can not change the size of array when we need to store more data elements.means we can say that simple circular array representation of Queue is the Static representation similar to simple array representation.
What’s Problems in the Simple Array Representation of Queue?
- Main problem of Simple Array representation of queue is that at the time of deletion(DeQueue) ,we are incrementing the front value and not shifting the remaining DataElements into left side.So at left side of Queue become empty. and rear value is also equal to the size of Queue.
You can see the above figure. in above figure rear is pointing to the last index ,because we are checking if(rear==size-1) for the knowing the Queue full status.this condition if(rear==size-1) is saying that Queue is full but still index 0,1 are empty, and we can not insert(EnQueue) the more elements using Simple Array Representation with condition if(rear==size-1) .
This problem is solved in Simple Circular Array Representation.
- In Simple Circular Array representation,we assume that last DataElement and first DataElement as a contiguous.
- front will indicate the first element and rear is used to indicate the last element.
- and FULL Queue status condition will be (rear+1)%size==front .
- DataElement will be insert always at index (rear+1)%size.
Now we have to start :
- first we have to initialize the array with specific size limitation.
- Declare two variables : 1 :- front ,2 :- rear.
- initialize the front and rear by -1,-1 indicates that Queue is empty.
Above are the basic requirements ,When Simple Array representation is ready ,then we can apply following Operations :
1- EnQueue & DeQueue(Insertion & Deletion Operation)
Working process of EnQueue and DeQueue in Simple Circular Array representation is following :
Code Implementation
/*Structure Implementations*/
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<malloc.h>
#include<conio.h>
#define SIMPLE_ARRAY_SIZE 3 // Define the Array Size
struct SimpleCircularArrayQueue // Structure for controlling the front ,rear,QueueSize and DataElement of Queue.
{
int front; // pointing to front
int rear; // pointing to rear
int size; // Queue Size
int *SimpleCircularArray; // Array to store the DataElement.
};
struct SimpleCircularArrayQueue* CreateSimpleCircularArrayQueue() //Function to Create an Queue and initilize all the required Variables
{
struct SimpleCircularArrayQueue* NewQueue = (struct SimpleCircularArrayQueue*)malloc(sizeof(struct SimpleCircularArrayQueue));
if (!NewQueue) // if Memory is not initilized for NewQueue
return NULL;
NewQueue->front = -1;
NewQueue->rear = -1;
NewQueue->size = SIMPLE_ARRAY_SIZE;
NewQueue->SimpleCircularArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
if (!NewQueue->SimpleCircularArray) //if Array is not initilized
return NULL;
else
return NewQueue;
}
bool IsFullQueue(struct SimpleCircularArrayQueue* Q) //Method for checking the Full state of Queue
{
return ((Q->rear+1)%Q->size==Q->front); //if Queue is full then return true else false
}
void EnQueue(struct SimpleCircularArrayQueue* Q, int DataElement) //Method of Inserting the DataElement into Queue
{
if (!IsFullQueue(Q)) // check the Overflow condition of Queue.
{
Q->rear = (Q->rear + 1) % Q->size;
Q->SimpleCircularArray[Q->rear] = DataElement;
printf("DataElement %d is inserted from rear in Queue :\n", DataElement);
if (Q->front == -1)
Q->front = Q->rear;
}
else
printf("Queue is in Overflow Condition,So DataElement %d can not be insert..\n",DataElement);
}
bool IsEmptyQueue(struct SimpleCircularArrayQueue* Q) //Method for checking the Empty state of Queue
{
return (Q->front == -1); // if Queue is empty then return true else false.
}
void DeQueue(struct SimpleCircularArrayQueue* Q) //Method of Deletion the DataElement from Queue
{
if (!IsEmptyQueue(Q)) // check the Underflow condition of Queue.
{
printf("\nDataElement %d is deleted from front in Queue :\n", Q->SimpleCircularArray[Q->front]);
Q->SimpleCircularArray[Q->front] = NULL;
if (Q->front == Q->rear)
Q->front = Q->rear = -1;
else
Q->front = (Q->front + 1) % Q->size;
}
else
{
printf("Queue is in Underflow Condi......\n");
}
}
int main()
{
int choice, DataElement , ChooseEnQDeQ;
struct SimpleCircularArrayQueue* MyQueue = CreateSimpleCircularArrayQueue(); //Create one Queue
if (!MyQueue)
printf("Sorry Your Queue is not ready....\n");
else
{
do
{
printf("1 : for EnQueue Operation\n");
printf("2 : for DeQueue Operation\n");
printf("Press 1 or 2 --- : ");
std::cin >> ChooseEnQDeQ;
switch (ChooseEnQDeQ)
{
case 1:
{
do
{
printf("Enter the data for insertion :");
std::cin >> DataElement;
EnQueue(MyQueue, DataElement);
printf("\nPress 0 for more insertion :");
std::cin >> choice;
} while (choice == 0);
break;
}
case 2:
{
do
{
DeQueue(MyQueue);
printf("\nPress 0 for more DeQueue Operation :");
std::cin >> choice;
} while (choice == 0);
break;
}
}
} while (ChooseEnQDeQ==1 || ChooseEnQDeQ==2);
}
printf("\nData Element after EnQueue/DeQueue Operation---> ");
struct SimpleCircularArrayQueue* TempQueue = MyQueue; // Temp Variable to print the Queue
int i = TempQueue->front;
if (i<= TempQueue->rear) //
{
while (i<= TempQueue->rear)
{
printf("%d ", TempQueue->SimpleCircularArray[i]);
i++;
}
}
else
{
while (i<= TempQueue->size-1)
{
printf("%d ", TempQueue->SimpleCircularArray[i]);
i++;
}
i = 0;
while(i<=TempQueue->rear)
{
printf("%d ", TempQueue->SimpleCircularArray[i]);
i++;
}
}
_getch();
return 0;
}
Time & Space Complexity
- EnQueue Time Complexity will be O(1).
- DeQueue Time Complexity will be O(1).
- IsEmptyQueue Time Complexity will be O(1).
- IsFullQueue Time Complexity will be O(1).
- Space Complexity will be O(n).