Queues
Queue is also a linear data structure involving insertion and deletion of elements from two different ends. The elements entered first into the list are removed first from the list. Therefore, it is also known as the FIFO( Fist in first out) data structure.
We can relate queues with the daily life examples like queue of people in front of a reservation counter. The people who came first in the queue are being served first. After getting the reservation done the person entering the queue first leaves the queue first.
The end where the elements are added is called the tail or the rear end of the queue whereas the end from which the elements are removed is called as the Front end of the queue.
Just like stacks queues are also implemented using arrays or linked list
Enqueue - the process of inserting an element in the queue.
Dequeue- the process of removing an element in the queue.
Data in queue is inserted at last of the list known as REAR end while data removed from the first end known as front end. Therefore, two variables are required to keep track of the front end and rear end.
Data structure queue is applied in various software applications like maintaining the printer queue, list of many system processes are maintained using queues.
Implementing queues using arrays
Initially when the queue is blank, front and rear are initialized with a value -1. -1 index value is not a valid array index therefore, front and rear equal to -1 indicates that the queue is empty.
Addition of first node in the queue:
When first value is added in the queue, both front and rear are initialized as 0 as the one value is the first and rear value in the queue.
Front=rear=0;
Q[rear] = value; //value is the new value added to the queue
Whenever an element is added to the queue, rear gets incremented by 1.
Rear=rear+1;
Whenever an element is deleted it is removed from the front. Therefore, value of front is incremented by 1.
Front = front + 1;
Following program illustrates the implementation of queue using array.
The program declares a class ‘queue’ with following members to maintain a queue of integers:
Data members
Val[10] – an array that has the capacity to store upto 10 elements at a time in the queue.
Front - an integer variable to keep track of the front of the queue from where the element is to be removed.
Rear – an integer variable to mark the end of the queue where the elements are added.
Function members :
Queue() – constructor to initialize the data members. Here, front and rear are initialized with -1.
Add() – the function adds the element at the rear end after incrementing the value of rear.
Remove()- this function removes the first element from the queue
Traverse() – this function displays the elements of the stack.
#include<iostream.h>
class queue
{
int front, rear, val[10];
public :
queue()
{ front=rear=-1; //val=0;
}
void add()
{
if((front==-1) && (rear==-1))
{ cout<<"\n enter the value to be pushed : ";
cin>>val[++rear];
front=0; }
else if((front==0) && (rear<9))
{ cout<<"\n enter the value to be pushed : ";
cin>>val[++rear];
}
else if((front==0)&& (rear==9))
{ cout<<" QUEUE OVERFLOW!!! ";}/
}
void remove()
{
if(front==-1)
cout<<"\n Queue is empty : ";
else
{
cout<<"Value removed is : "<<val[front];
front++;
}
}
void traverse()
{
for(int i=front;i<=rear;i++)
cout<<endl<<val[i];
}
};
void main()
{
queue s;
char ch='y';
int m=0;
while (ch=='y')
{
cout<<"\n Enter your choice :";
cout<<"\n 1.Push \n 2. Pop \n 3.Traverse 4. Exit ";
cin>>m;
switch(m)
{
case 1 : s.add();
break;
case 2 : s.remove();
break;
case 3 : s.traverse();
break;
case 4 : cout<<"\n Exiting....";
break;
default : cout<<"\n Wrong choice :";
}
cout<<"\n Want ot continue ??? ";
cin>>ch;
}
cout<<"\n Bye Bye ";
// getch();
}
Circular queue :
In simple implementation of a queue using array, front as well as rear, both are incremented on removal or insertion of an element in the array. In case, value of rear reaches the maximum value of the array then it is not possible to insert the elements further in the array even though the beginning positions are blank/ vacant). This leads to limitation of general implementation of the queue that even though there is space in the array but no more a values are being added.
Figure below illustrates the limitation :
When first element (12) is added to the queue , status of the array is :
Front =0 rear = 0
If two more elements ( 23 and 56) are added in the queue: front =0, rear =2
Now an element is removed from the front and 5 more elements are added then status of queue is :
Front =1 , rear =7
Consider that three more values are removed and two are inserted at rear end, then status of queue is as follows :
Front=4, rear=9
Observe the above status of queue, we can notice that even though the array locations in the beginning are blank but no more elements can be added as rear has reached the maximum index value supported by the array.
Circular queue overcomes this limitation by shifting rear to the first position and utilizing the blank space.
In above case if a new element is to be added, then it would be added as follow s:
Front =4, rear =0
Imagine the two ends of the array are joined to form a circular array.
Following program implements circular queue using arrays :
#include<iostream.h>
class queue
{
int front, rear, val[10];
public :
queue()
{ front=rear=-1; //val=0;
}
void add()
{
if((front>0)&&(rear==9))
{ rear==0;
cout<<"\n enter the value to be added : ";
cin>>val[rear];
}
else if((front==-1) && (rear==-1))
{ cout<<"\n enter the value to be added : ";
cin>>val[++rear];
front=0; }
else if((front==0) && (rear<9))
{ cout<<"\n enter the value to be added : ";
cin>>val[++rear];
}
else if(((front==0)&& (rear==9))||(rear+1==front))
{ cout<<" QUEUE OVERFLOW!!! ";}
}
void remove()
{
if(front==-1)
cout<<"\n Queue is empty : ";
else if(front==rear)
{ cout<<"\n Value removed is : "<<val[front];
front=rear=-1;
}
else
{
cout<<"Value removed is : "<<val[front];
for(int i=front;i<rear;i++)
val[i]=val[i+1];
rear= rear-1;
}
}
void traverse()
{
for(int i=front;i<=rear;i++)
cout<<endl<<val[i];
}
};
void main()
{
queue s;
char ch='y';
int m=0;
while (ch=='y')
{
cout<<"\n Enter your choice :";
cout<<"\n 1.Add \n 2. Delete \n 3.Traverse 4. Exit ";
cin>>m;
switch(m)
{
case 1 : s.add();
break;
case 2 : s.remove();
break;
case 3 : s.traverse();
break;
case 4 : cout<<"\n Exiting....";
break;
default : cout<<"\n Wrong choice :";
}
cout<<"\n Want ot continue ??? ";
cin>>ch;
}
cout<<"\n Bye Bye ";
getch();
}
Linked queue
Just like stacks, to implement queues using linked list we need to create a node first.
This node should be defined using a class having data and a pointer variable of type node.
class queue
{
queue *front, *rear,*temp, ;
int val;
queue *next;
public:
queue()
{ front=rear=NULL; //val=0;
}
void add();
void remove();
void traverse();
};
In the above example , queue class has
Val – data member to store data part of the node.
*next – it is the pointer variable of type stack only which can store address of next node.
*front- keeps a track of front of the queue elements
*rear – keeps a track of the tail of the queue
* temp – used for creating new nodes.
Add() – function to add elements in the queue
Remove()- to remove elements from the queue
Traverse() – function to display elements of the queue
Front and rear are pointing to null initially
Addition of nodes in a queue : First of all front, rear and temp nodes are created. All these nodes are initialized with a null value.
To add a node first temp is assigned a new memory :
temp = new node;
Now front will point to this node as this is the first and the last node:
Front =temp;
Rear= temp;
Addition of Second node
Next node is added :
Now temp node will be added to the queue :
New node has to be inserted at the rear end therefore, next link of rear will point to temp.
rear ->next=temp;
As a new node has been added at the end therefore it should be designated as the rear node.
Similarly more new nodes are added to the queue.
Deletion of a node : The nodes are removed from the beginning position of the queues. Temp is initialized at the temporary mode will point to the first node(front) :
Temp=front;
Now the next node in sequence is treated as the front node :
front =front -> next;
The command is deleted from the front position and the next nde in sequence becomes the front node in the queue:
delete temp;
Status of queue after deletion of node.
This is how the nodes get removed from the queues .
Now let us tryout the programmes of queues:
#include<iostream.h>
class queue
{
queue *front=NULL, *rear=NULL,*temp=NULL ;
int val;
queue *next;
public:
queue()
{ front=rear=NULL; //val=0;
}
void add()
{ temp=new queue;
cout<<"\n enter the value to be pushed : ";
cin>>temp->val;
temp->next=NULL;
if(front==NULL)
front =rear=temp;
else
rear->next=temp;
}
void remov()
{
if(front==NULL)
cout<<"\n Queue is empty : ";
else
{
temp=front;
front=front->next;
cout<<"\n value deleted is : "; <<temp->val;
delete temp;
if(front==NULL)
rear=NULL;
}
void traverse()
{
for(temp=front;temp!=NULL;temp=temp->next)
cout<<endl<<tmp->val;
}
};
void main()
{
queue s;
char ch='y';
int m=0;
while (ch=='y')
{
cout<<"\n Enter your choice :";
cout<<"\n 1.Push \n 2. Pop \n 3.Traverse 4. Exit ";
cin>>m;
switch(m)
{
case 1 : s.add();
break;
case 2 : s.remov();
break;
case 3 : s.traverse();
break;
case 4 : cout<<"\n Exiting....";
break;
default : cout<<"\n Wrong choice :";
}
cout<<"\n Want to continue ??? ";
cin>>ch;
}
cout<<"\n Bye Bye ";
// getch();
}
Implementation of circular queues using linked lists
Circular linked queue is similar to linked queue but only difference lies in the fact that the next pointer variable of rear node stores the address of the front node
Figure below will make it easier to understand:
Addition of a node :
Front , rear and temp are initialized to null.
To add a node first temp is assigned a new memory :
temp = new node;
Now front will point to this node as this is the first and the last node:
front =temp;
rear= temp;
rear->next=temp;
Since it is a circular queue therefore , next link of this first node will point to itself.
Addition of Second node
Next node is added :
Now temp node will be added to the queue :
New node has to be inserted at the rear end therefore, next link of rear will point to temp.
rear->next=temp;
As a new node has been added at the end therefore it should be designated as the rear node.
rear->next=temp;
temp->next=front;
Similarly more new nodes are added to the queue.
Deletion of a node : The nodes are removed from the beginning position of the queues. Temp is initialized at the temporary mode will point to the first node(front) :
temp=front;
Now the next node in sequence is treated as the front node :
front =front -> next;
The node is deleted from the front position and the next node in sequence becomes the front node in the queue:
delete temp;
Status of queue after deletion.
and next node in sequence becomes the front node.
front = front -> next;
Next node of rear is also changed to front node:
rear-> = temp -> next; //
or rear->next=front;
#include<iostream.h>
#include<process.h>
struct node
{
int rno;
char name[20];
int marks;
node *next;
};
void main()
{
int ch; char ans='y';
node *f, *t, *r ;
f=r=NULL;
t=NULL;
while(ans=='y')
{ cout<<"\n enter your choice : \n1. add \n 2. deletion \n 3. traversal"
<<" \n 4. exit ";
cin>>ch;
switch(ch)
{
case 1 : {
t = new node;
cout<<"\n enter roll number and name";
cin>>t->rno>>t->name>>t->marks;
t->next=f;
if(f==NULL)
f=r=t;
else
{
r->next=t;
r=t;
}
break;
}
case 2: {
if(f==NULL)
cout<<"\n queue is empty ";
else if(f==r)
{ t=f;
f=r=NULL;
delete t;
cout<<"\n value to be deleted is :";
cout<<t->rno<<"\t"<<t->name<<"\t"<<t->marks;
}
else
{
t=f;
r->next=f->next;
f=f->next;
cout<<"\n value to be deleted is :";
cout<<t->rno<<"\t"<<t->name<<"\t"<<t->marks;
delete t;
cout<<"\n NODE deleted :";
}
break;
}
case 3 : { if(f==NULL)
cout<<" Queue is blank : ";
else if (f==r)
cout<<f->rno<<"\t"<<f->name<<"\t"<<f->marks;
else
{
t=f;
cout<<"\n"<<t->rno<<"\t"<<t->name<<t->marks;
for(t=f->next;t!=f ;t=t->next)
cout<<"\n "<<t->rno<<"\t"<<t->name<<t->marks ;
} break;
}
case 4: exit(0); break;
default : cout<<"\n wrong choice";
}
cout<<"\n Want to continue (y/n) ?";
cin>>ans;
}
}
No comments:
Post a Comment