Dynamic Array Representation of Queue

Dynamic Array Representation of Queue is better than Simple Array Representation , Dynamic Array Representation is something efficient and good representation of Queue,because Array size will be doubled when array size if full. we can say that Dynamic array representation of Queue is the Dynamic representation.

• 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(Insertion Operation)

Working process of EnQueue is following :

Code Implementation of EnQueue

/*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 initial Array Size
struct DynamicArrayQueue       // 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 *DynamicArray;  // Array to store the DataElement.
};
struct DynamicArrayQueue* CreateDynamicArrayQueue()  //Function to Create an Queue and initilize all the required Variables
{
	struct DynamicArrayQueue* NewQueue = (struct DynamicArrayQueue*)malloc(sizeof(struct DynamicArrayQueue));
	if (!NewQueue)       // if Memory is not initilized for NewQueue
		return NULL;
	NewQueue->front = -1;
	NewQueue->rear = -1;
	NewQueue->size = SIMPLE_ARRAY_SIZE;
	NewQueue->DynamicArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
	if (!NewQueue->DynamicArray)  //if Array is not initilized
		return NULL;
	else
		return NewQueue;
}
bool DoubleArraySize(struct DynamicArrayQueue* Q)
{
	Q->size = Q->size * 2; // Double the Array Size..
	//Re-Allocation of Memory by double Size..
	Q->DynamicArray = (int*)realloc(Q->DynamicArray, Q->size * sizeof(int));
	if (!Q->DynamicArray)
		return false;
	else
		return true;
}
bool IsFullQueue(struct DynamicArrayQueue* Q) //Method for checking the Full state of Queue
{
	bool IsDouble=false;
	if (Q->rear == Q->size-1)
	{
	   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 DynamicArrayQueue* Q, int DataElement)   //Method of Inserting the DataElement into Queue
{
	if (!IsFullQueue(Q))              // check the Overflow condition of Queue.
	{
		if (Q->front == -1 && Q->rear == -1)
		{
			Q->front++;
			Q->rear++;
		}
		else
		{
			Q->rear++;
		}
		Q->DynamicArray[Q->rear] = DataElement;
		printf("DataElement %d is inserted from rear in Queue :\n", DataElement);
	}
	else
		printf("Queue is in Overflow Condition......\n");
}
int main()
{
	int choice, DataElement;
	struct DynamicArrayQueue* MyQueue = CreateDynamicArrayQueue(); //Create one Queue
	if (!MyQueue)
		printf("Sorry Your Queue is not ready....\n");
	else
	{
		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);
	}
	printf("Data Element after EnQueue Operation---> ");
	while (MyQueue->front != MyQueue->rear)
	{
		printf("%d ", MyQueue->DynamicArray[MyQueue->front]);
		MyQueue->front++;
	}
	printf("%d ", MyQueue->DynamicArray[MyQueue->front]);
	_getch();
	return 0;
}

2- DeQueue(Deletion Operation)

Working process of DeQueue operation in Dynamic Representation is same to the DeQueue operation in Simple Array Representation of Queue.

---

Time & Space Complexity

• EnQueue Time Complexity will be O(1).
• DeQueue Time Complexity will be O(1).
• DoubleArraySize 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).