Queue
ØA Queue is a linear list of elements in which
deletions can take place only at one end, called the
‘FRONT’ and insertions can take place only at the
other end, called the ‘REAR’.
Array Representation
Insertion into a Queue
Q_INSERT (QUEUE, N, FRONT, REAR, ITEM)
1.If FRONT = 1 and REAR = N, or
If FRONT =REAR+1, then:
Write: OVERFLOW and Return. [Overflow]
2.If FRONT = NULL, then [Queue initially empty]
Set FRONT = 1 and REAR = 1.
Else if REAR = N, then
Set REAR = 1.
Else:
Set REAR = REAR + 1
[End of if Structure.]
3.Set Queue[REAR] = ITEM.
4.Return.
Deletion in a Queue
Q_DELETE (QUEUE, N, FRONT, REAR, ITEM)
1.If FRONT = NULL, then:
Write: UNDERFLOW and Return.
[Underflow]
2.Set ITEM = QUEUE [FRONT].
3.If FRONT = REAR, then
[Queue has only one element
Set FRONT = NULL and REAR = NULL.
Else if FRONT = N, then
Set FRONT = 1.
Else:
Set FRONT = FRONT + 1.
[End of if Structure.]
4.Return.
Code to implement a Queue using array.
#include<iostream>
#include<stdio.h>
using namespace std;
struct ArrayQueue{
int front,rear;
int capacity;
int *array;
};
ArrayQueue* CreateQueue(int cap)
{
ArrayQueue *temp=new ArrayQueue;
temp->rear=temp->front=-1;
temp->capacity=cap;
int *s=new int[temp->capacity];
temp->array=s;
return temp;
}
int IsQueueFull(ArrayQueue *ptr)
{
if((ptr->rear+1)%ptr->capacity==ptr->front)
{
return 1;
}
else
{
return 0;
}
}
int IsEmptyQueue(ArrayQueue *ptr)
{
if(ptr->front==-1)
{
return 1;
}
else
{
return 0;
}
}
int QueueSize(ArrayQueue *ptr)
{
if(ptr->front==-1)
{
return 0;
}
return((ptr->capacity-ptr->front+ptr->rear+1)%ptr->capacity);
}
void InsertQueue(ArrayQueue *ptr,int item)
{
if(IsQueueFull(ptr))
{
cout<<"Queue is full";
}
else
{
ptr->rear=(ptr->rear+1)%ptr->capacity;
ptr->array[ptr->rear]=item;
if(ptr->front==-1)
{
ptr->front=ptr->rear;
}
}
}
int DeleteQueue(ArrayQueue *ptr)
{
if(IsEmptyQueue(ptr))
{
return -1;
}
else
{
int data=ptr->array[ptr->front];
if(ptr->front==ptr->rear)
{
ptr->front=ptr->rear=-1;
}
else
{
ptr->front=(ptr->front+1)%ptr->capacity;
}
return data;
}
}
void Display(ArrayQueue *ptr)
{
if(IsEmptyQueue(ptr))
{
cout<<"\nThere is no element to display\n";
}
else
{
int temp=ptr->front;
int temp2=ptr->rear;
while(temp!=temp2)
{
cout<<ptr->array[temp]<<endl;
temp=(temp+1)%ptr->capacity;
}
cout<<ptr->array[ptr->rear]<<endl;
}
}
int main()
{
int choice,cap,item;
cout<<"Enter total number of elements";
cin>>cap;
ArrayQueue *queue;
queue=CreateQueue(cap);
while(1)
{
cout<<"\n1. Insert In A queue";
cout<<"\n2. Delete From a Queue";
cout<<"\n3. Size Of The Queue";
cout<<"\n4. Display Queue";
cout<<"\n5. Exit ";
cout<"\n Enter Your Choice\n";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter the value";
cin>>item;
InsertQueue(queue,item);
break;
case 2:
item=DeleteQueue(queue);
if(item==-1)
{
cout<<"Queue is empty";
}
else
{
cout<<"\nDeleted Item is "<<item;
}
break;
case 3:
item=QueueSize(queue);
cout<<"\nTotal Element in Queue is "<<item;
break;
case 4:
Display(queue);
break;
case 5:
exit(0);
}
}
}
0 Comments