DATA STRUCTURE : QUEUE
In real life we make queue at the Bus Stop or in the bank or somewhere else. Notice that the person entered in the Queue first will leave first so its a FIFO structure. The person standing at the top will leave first (means deletion in a QUEUE always occurs from the front end) . The new person which wants to join the Queue will enter from the back or rear of the QUEUE (means insertion in the QUEUE occurs from the rear part)
 |
#include<stdio.h>
#include<stdlib.h>
// A queue has an Index (Capacity) because we use Array to implement this Data Structure Queue . And a queue has front and rear and an array which points the whole queue
struct QueueADT{
int capacity;
int front;
int rear;
int *arr;
};
// The function will take a paramater cap , cap represent the indexing of queue
struct QueueADT* createQueue(int cap)
{
//we created a queue with the name temp & the return type is struct QueueADT because it returns queue
struct QueueADT *temp;
//the size of temp/queue is given by malloc at run time , malloc reserve a block of memory for queue
temp=(struct QueueADT*)malloc(sizeof(struct QueueADT));
//The indexing of temp is shown by capacity we store capacity in a variable cap
temp->capacity=cap;
//the front of queue is empty(having no elements) in the start and -1 represent the empty queue
temp->front=-1;
//the end of the queue is also empty
temp->rear=-1;
//Array which points the whole queue is created by malloc, the size of array is given by malloc
temp->arr=(int*)malloc(sizeof(int) * temp->capacity);
//return temp will return the whole queue created in this function
return(temp);
#include<stdlib.h>
// A queue has an Index (Capacity) because we use Array to implement this Data Structure Queue . And a queue has front and rear and an array which points the whole queue
struct QueueADT{
int capacity;
int front;
int rear;
int *arr;
};
// The function will take a paramater cap , cap represent the indexing of queue
struct QueueADT* createQueue(int cap)
{
//we created a queue with the name temp & the return type is struct QueueADT because it returns queue
struct QueueADT *temp;
//the size of temp/queue is given by malloc at run time , malloc reserve a block of memory for queue
temp=(struct QueueADT*)malloc(sizeof(struct QueueADT));
//The indexing of temp is shown by capacity we store capacity in a variable cap
temp->capacity=cap;
//the front of queue is empty(having no elements) in the start and -1 represent the empty queue
temp->front=-1;
//the end of the queue is also empty
temp->rear=-1;
//Array which points the whole queue is created by malloc, the size of array is given by malloc
temp->arr=(int*)malloc(sizeof(int) * temp->capacity);
//return temp will return the whole queue created in this function
return(temp);
//To get the capacity of Queue we make a function that will return the capacity or the indexing
of Q
int QueueCapacity(struct QueueADT *Q )
{
return(Q ->capacity);
}
//To enter a value in Queue we will make a function enQueue
means enter a value in Queue. It will take 2 parameters . A queue and the value
which we want to add/enter in the queue
void enQueue(struct QueueADT *Q , int value)
{
// The capacity of Queue must be greater than or equals to 1
if(Q
->capacity<1)
printf("Invalid
capacity");
// there are three conditions when we want to enter a value
in Queue. The first one is A EMPTY QUEUE.
else{
// We will call the
function empty Queue to check if the queue is empty or not . It will take a
parameter Queue
if(IsemptyQueue(Q))
{
// If the Queue is empty , means it has no value then we
will enter the value in the 0th index ( first Index) of our Queue
Q->arr[0]
=value;
// And increase the front from -1 to 0 , which indicate that
the queue is not empty it has a value
Q->front=0;
//Also increase the rear
Q->rear=0;
}
// The second condition when we want to enter a
value inQueue is A FULL QUEUE . Ofcourse the value will not enter in the full
Queue
else
if(IsFullQueue(Q))
{
// And it will print Queue Overflow
printf("Queue
Overflow");
}
else
if(Q->rear==Q->capacity-1)
{
Q->rear=0;
}
// The condition is if the queue has some values but not
full means it has some capacity . We will check this if the last part or rear
part of queue is not equals to the capacity -1 (we use -1 because we assume
that the indexing of queue array starts from 0)
else
{
// Then we will increase the rear part to enter a new value
Q
->rear=Q ->rear+1;
// Then in the rear part
of array of queue , we enter the value
Q->arr[Q->rear]
= value;
}
}
}
// The function Is Empty will tell us . If the queue is
Empty or not? It will take a parameter Queue
int IsemptyQueue(struct QueueADT *Q )
{
// it will analyze by checking if the front part of Queue is
equals to -1 . -1 will indicate that the queue is still empty. Because we give
the front -1 at the time of creation & -1 indicate an empty Queue
if(Q->front==-1)
// Successful
return(1);
else
// Unsuccessful
return(0);
}
// this function will
tell us Is the queue is Full or not . It will also take a parameter to do so it
has a return type int because we use 0 and 1 to indicate the successful &
unsuccessful termination of the function
int IsFullQueue(struct QueueADT *Q)
{
// If the front part has a value means the front part is
equals to 0 and the rear part and capacity are equal then it means the queue is
now FULL
if(Q->front==0
&& Q->rear == Q->capacity-1)
// Successful termination
return(1);
else
if(Q->front==Q->rear+1)
return(1);
else
return(0); }
// To show theQueue we will make a function Show Queue . it
will take a parameter Q
void ShowQueue(struct QueueADT *Q)
{
int i;
// we
use a loop to print the Queue as we use to print an Array this loop will starts
from 0 and ends with rear (0 to rear ) and increase after every itteration
for(i=0;
i<= Q->rear; i++)
{
// We will simply
print the values of queue as given below
printf("\n
Values of Queue is %d \n" ,Q->arr[i]);
}
}
// Deletion in the queue always occur from the front side.
For this we make a function delete Queue . It will take a queue and delete the
first value
void deQueue(struct QueueADT *Q)
{
int i,size=0;
// To delete a queue we have four conditions . First one is
if the queue is empty. We will call the function Is empty to check if the queue
has some value or not
if(IsemptyQueue(Q))
// Obviously if the queue is empty means it has no value to
delete . It will simply print Underflow means the queue has no value
printf("UnderFlow");
// The second
condition is the front and the rear of queue is equal . Means it has only one
value
else
if(Q->front==Q->rear)
Q->front==Q->capacity-1;
else
if(Q->front==Q->capacity-1)
Q->front=0;
else
Q->front=Q->front+1;
if(Q->front>-1){
for(i=Q->front; i!=Q->rear;)
{
size++;
if(i==Q->capacity-1)
i=0;
else
i++;
}
}
}
// The main function will load in the memory first so we
call every function one by one we make above in the main()
void main()
{
// we initialize a variable Q with the data type struct
QueueADT
struct
QueueADT *Q;
int
value;
// Call the function create Queue & give the capacity 4
(hardcoded)
Q=createQueue(4);
// Print the capacity of queue by thefunction QueueCapacity
printf("\n
capacity %d", QueueCapacity(Q));
// Print the Front
& Rear . At first the front & rear part is equals to -1(Empty)
printf("\n
Front =%d, Rear = %d", Q->front, Q->rear);
// Then take a
number from the user which the user
wants to enter in the queue
printf("\n
Enter a number:");
// The variable value will hold the number entered by the
user
scanf("%d",&value);
// Then call the function enterQueue , Pass the parameter .
A queue and the value
enQueue(Q
, value);
// then print the front and rear . Now the Queue is not empty
it has some value (rear=0 , front =0)
printf("\n
Front =%d, Rear = %d", Q->front, Q->rear);
// Repeat the procedure just to display the whole queue
printf("\n Enter a number:");
scanf("%d",&value);
enQueue(Q
, value);
printf("\n
Front =%d, Rear = %d", Q->front, Q->rear);
printf("\n
Enter a number:");
scanf("%d",&value);
enQueue(Q
, value);
printf("\n
Front =%d, Rear = %d", Q->front, Q->rear);
// Now call the function Show Queue . It will show all the
values that are present in the queue and entered by the user
ShowQueue(Q);
deQueue(Q
);
// The value of front
is now decreased but the rear remains the same because the deletion in Queue always occur
from the front end
printf("\n
Front =%d, Rear = %d", Q->front, Q->rear);
ShowQueue();
getch();
}
*****************************************************************
Hope this documentation on QUEUE guides you completely . If you find any difficulty then you are free to ask in the comment section.
THANKS
*****************************************************************
Hope this documentation on QUEUE guides you completely . If you find any difficulty then you are free to ask in the comment section.
THANKS
0 Comments