- Dynamic Circular Array Representation of Queue is extended version of Dynamic Array Representation of Queue , this is an efficient and good representation of Queue,because Array size can be extend as per requirements.
- This representation solve the disadvantages of Dynamic Array representation of Queue as well as Simple Circular Array representation of Queue.
- In This representation we can increase the size of Queue as per requirements and there will be no memory and space will be empty.
- This is an Dynamic Growable representation of Queue.
Whats Problems in the Dynamic Array and Simple Circular Array Representation?
- Simple Circular Array representation is an static implementation of Queue,means when Queue is full and we want to insert more DataElements ,then we can not grow the size of Queue.So this is main problems in Simple Circular Array representation.
- Dynamic Array representation is an Dynamic representation of Queue.but problem is that when left side DataElement has been deleted and (rear=size ) ,then we can not insert the DataElement at left side. So ,if we apply Circular condition rear=(rear+1)%size in Dynamic Array ,it will work as Circular Dynamic Array.
In above figure Initial two spaces are empty be DeQueue operation,because first we filled the whole Queue,and then delete the two DataElements,So now rear is pointing to last index.and initial two spaces will be wasted.
Problems of Simple Circular Array and Dynamic Array representations are solved in Dynamic Circular Array representation of Queue.
- In Dynamic 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 Dynamic Array representation is ready ,then we can apply following Operations :
1- EnQueue & DeQueue(Insertion & Deletion Operation)
Working process of EnQueue and DeQueue in Dynamic 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 2 // Define the Array Size
struct DynamicCircularArrayQueue // 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 *DynamicCircularArray; // Array to store the DataElement.
};
struct DynamicCircularArrayQueue* CreateDynamicCircularArrayQueue() //Function to Create an Queue and initilize all the required Variables
{
struct DynamicCircularArrayQueue* NewQueue = (struct DynamicCircularArrayQueue*)malloc(sizeof(struct DynamicCircularArrayQueue));
if (!NewQueue) // if Memory is not initilized for NewQueue
return NULL;
NewQueue->front = -1;
NewQueue->rear = -1;
NewQueue->size = SIMPLE_ARRAY_SIZE;
NewQueue->DynamicCircularArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
if (!NewQueue->DynamicCircularArray) //if Array is not initilized
return NULL;
else
return NewQueue;
}
bool DoubleArraySize(struct DynamicCircularArrayQueue* Q)
{
Q->size = Q->size * 2; // Double the Array Size..
//Re-Allocation of Memory by double Size..
Q->DynamicCircularArray = (int*)realloc(Q->DynamicCircularArray, Q->size * sizeof(int));
if (!Q->DynamicCircularArray)
return false;
else
return true;
}
bool IsFullQueue(struct DynamicCircularArrayQueue* Q) //Method for checking the Full state of Queue
{
bool IsDouble = false;
if ((Q->rear+1)%Q->size == Q->front)
{
IsDouble = DoubleArraySize(Q); // Double the Array Size when Queue is Full.
if (IsDouble)
{
printf("\nQueue size has been doubled Now....\n");
return !IsDouble;
}
}
return IsDouble; //if Queue is full then return true else false
}
void EnQueue(struct DynamicCircularArrayQueue* 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->DynamicCircularArray[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 DynamicCircularArrayQueue* 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 DynamicCircularArrayQueue* 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->DynamicCircularArray[Q->front]);
Q->DynamicCircularArray[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 DynamicCircularArrayQueue* MyQueue = CreateDynamicCircularArrayQueue(); //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 DynamicCircularArrayQueue* TempQueue = MyQueue; // Temp Variable to print the Queue
int i = TempQueue->front;
if (i<= TempQueue->rear) //
{
while (i<= TempQueue->rear)
{
printf("%d ", TempQueue->DynamicCircularArray[i]);
i++;
}
}
else
{
while (i<= TempQueue->size-1)
{
printf("%d ", TempQueue->DynamicCircularArray[i]);
i++;
}
i = 0;
while(i<=TempQueue->rear)
{
printf("%d ", TempQueue->DynamicCircularArray[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).