Simple Array Representation of Queue is very simple , but this is 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 array representation of Queue is the Static 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 for EnQueue
/*Structure Implementations*/
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<malloc.h>
#include<conio.h>
#define SIMPLE_ARRAY_SIZE 5 // Define the Array Size
struct SimpleArrayQueue // 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 *SimpleArray; // Array to store the DataElement.
};
struct SimpleArrayQueue* CreateSimpleArrayQueue() //Function to Create an Queue and initilize all the required Variables
{
struct SimpleArrayQueue* NewQueue = (struct SimpleArrayQueue*)malloc(sizeof(struct SimpleArrayQueue));
if (!NewQueue) // if Memory is not initilized for NewQueue
return NULL;
NewQueue->front = -1;
NewQueue->rear = -1;
NewQueue->size = SIMPLE_ARRAY_SIZE-1;
NewQueue->SimpleArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
if (!NewQueue->SimpleArray) //if Array is not initilized
return NULL;
else
return NewQueue;
}
bool IsFullQueue(struct SimpleArrayQueue* Q) //Method for checking the Full state of Queue
{
return (Q->rear == Q->size-1); //if Queue is full then return true else false
}
void EnQueue(struct SimpleArrayQueue* 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->SimpleArray[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 SimpleArrayQueue* MyQueue = CreateSimpleArrayQueue(); //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->SimpleArray[MyQueue->front]);
MyQueue->front++;
}
printf("%d ", MyQueue->SimpleArray[MyQueue->front]);
_getch();
return 0;
}
2- DeQueue(Deletion Operation)
Working process of DeQueue is following :
Code Implementation for DeQueue
/*Structure Implementation*/
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<malloc.h>
#include<conio.h>
#define SIMPLE_ARRAY_SIZE 6 // Define the Array Size
struct SimpleArrayQueue // 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 *SimpleArray; // Array to store the DataElement.
};
struct SimpleArrayQueue* CreateSimpleArrayQueue() //Function to Create an Queue and initilize all the required Variables
{
struct SimpleArrayQueue* NewQueue = (struct SimpleArrayQueue*)malloc(sizeof(struct SimpleArrayQueue));
if (!NewQueue) // if Memory is not initilized for NewQueue
return NULL;
NewQueue->front = -1;
NewQueue->rear = -1;
NewQueue->size = SIMPLE_ARRAY_SIZE;
NewQueue->SimpleArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
if (!NewQueue->SimpleArray) //if Array is not initilized
return NULL;
else
return NewQueue;
}
bool IsEmptyQueue(struct SimpleArrayQueue* Q) //Method for checking the Empty state of Queue
{
return (Q->front > Q->rear || Q->front == -1 || Q->rear == -1) ; // if Queue is empty then return true else false.
}
void DeQueue(struct SimpleArrayQueue* 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->SimpleArray[Q->front]);
Q->SimpleArray[Q->front] = NULL;
Q->front++;
}
else
{
printf("Queue is in Underflow Condi......\n");
Q->front = Q->rear = -1; //When Underflow occures then we have to make front and rear as -1.
}
}
int main()
{
int choice, DataElement;
struct SimpleArrayQueue* MyQueue = CreateSimpleArrayQueue(); //Create one Queue
//Manually Insert the 5 DataElement into Queue.
if (!MyQueue)
printf("\nSorry Your Queue is not ready....\n");
else
{
MyQueue->SimpleArray[0] = 10;
MyQueue->SimpleArray[1] = 20;
MyQueue->SimpleArray[2] = 30;
MyQueue->SimpleArray[3] = 40;
MyQueue->SimpleArray[4] = 50;
MyQueue->front = 0;
MyQueue->rear = 4;
}
printf("Data Element before DeQueue Operation---> ");
if (MyQueue->front != -1 || MyQueue->rear != -1)
{
int frontTemp = MyQueue->front;
while (frontTemp != MyQueue->rear)
{
printf("%d ", MyQueue->SimpleArray[frontTemp]);
frontTemp++;
}
printf("%d ", MyQueue->SimpleArray[frontTemp]);
}
do
{
DeQueue(MyQueue);
printf("\nPress 0 for more DeQueue Operation :");
std::cin >> choice;
} while (choice == 0);
printf("\nData Element after DeQueue Operation---> ");
if (!IsEmptyQueue(MyQueue))
{
while (MyQueue->front != MyQueue->rear)
{
printf("%d ", MyQueue->SimpleArray[MyQueue->front]);
MyQueue->front++;
}
printf("%d ", MyQueue->SimpleArray[MyQueue->front]);
}
else
printf("Sorry Queue is Empty....");
_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).