Friday, 15 December 2017

Write C++ programs to implement the Double Ended Queue (DEQUE) using array.

Implementation of above problem using C++:
#include <iostream>
using namespace std;
#define MAX 10
int front=-1,rear=-1,c,i;
template<class t>
class dqueADT
{
public:
virtual void addqatbeg()=0;
virtual void addqatend()=0;
virtual void delqatbeg()=0;
virtual void delqatend()=0;
virtual void display()=0;
};
template <class t>
class dque: public dqueADT<t>
{
public:
t q[MAX],item;
dque()
{
front=rear=-1;
for(i=0;i<MAX;i++)
q[i]=0;
}
void addqatbeg()
{
cout<<"Enter an element:";
cin>>item;
if (front==0&&rear==MAX-1)
{
cout<<"\nDeque is full"<<endl;
return ;
}
if(front==-1)
{
front=rear=0;
q[front]=item;
return;
}
if(rear!=MAX-1)
{
c=count();
int k=rear+1;
for(i=1;i<=c;i++)
{
q[k]=q[k-1];
k--;
}
q[k]=item;
front=k;
rear++;
}
else
{
front--;
q[front]=item;
}
}
void addqatend()
{
cout<<"Enter an element:";
cin>>item;
if(front==0&&rear==MAX-1)
{
cout<<"\nDeque is full"<<endl;
return;
}
if(front==-1)
{
rear=front=0;
q[rear]=item;
return;
}
if(rear==MAX-1)
{
int k=front-1;
for(i=front-1;i<rear;i++)
{
k=i;
if(k==MAX-1)
q[k]=0;
else
q[k]=q[i+1];
}
rear--;
front--;
}
rear++;
q[rear]=item;
}
void delqatbeg()
{
if(front==-1)
{
cout<<"\nDeque is empty"<<endl;
return;
}
item=q[front];
q[front]=0;
if(front==rear)
front=rear=-1;
else
front++;
cout<<"Deleted item is:"<<item;
}
void delqatend()
{
if(front==-1)
{
cout<<"\nDeque is empty"<<endl;
return;
}
item=q[rear];
q[rear]=0;
rear--;
if(rear==-1)
front=-1;
cout<<"Deleted item is: "<<item;
}
void display()
{
cout<<endl<<"front-> ";
for(i=0;i<MAX;i++)
cout<<" "<<q[i];
cout<<" <-rear";
}
int count()
{
int c=0;
for(i=0;i<MAX;i++)
{
if(q[i]!=0)
c++;
}
return c;
}
};
main()
{
int ch;
dque<int> s1;
do
{
cout<<"\n****Menu****";
cout<<"\n1. Insert at Beginning\n2. Insert at End\n3. Delete from Beginning\n4. Delete from End\n5. Display\n6. Exit";
cout<<"\nEnter ur choice:";
cin>>ch;
switch(ch)
{
case 1: s1.addqatbeg();
break;
case 2: s1.addqatend();
break;
case 3: s1.delqatbeg();
break;
case 4: s1.delqatend();
break;
case 5: s1.display();
break;
case 6: exit(1);
}
}
while(1);
return 0;
}


Thanks
Mukesh Rajput
Write a C++ program to implement the Queue ADT using singly linked list.

Queue is an ordered collection of data such that the data is inserted at one end and deleted from other end. It is a collection of items to be processed on a First-In-First-Out(FIFO) or First Come First Served(FCFS) basics.

Implementation of the above problem in C++:
#include<iostream>
using namespace std;
template<class t>
class node
{
public:
t info;
node *link;
};
template<class t>
class QueueADT
{
virtual void Insert()=0;
virtual void Delete()=0;
virtual void Display()=0;
};
template <class t>
class QueueLinkImp: public QueueADT<t>
{
public:
t item;
node<t> *temp,*front,*rear;
QueueLinkImp()
{
front=rear=NULL;
}
void Insert()
{
temp=new node<t>;
cout<<"Enter an element to be inserted in to queue:";
cin>>item;
temp->info=item;
temp->link=NULL;
if(front==NULL)
{
front=rear=temp;
cout<<item<<" inserted Successfully";
return;
}
rear->link=temp;
rear=rear->link;
cout<<item<<" inserted Successfully";
}
void Delete()
{
if(front==NULL)
cout<<"Queue is empty";
else
{
item=front->info;
front=front->link;
cout<<"Deleted Element is: "<<item;
}
}
void Display()
{
if(front==NULL)
cout<<"Queue is empty";
else
{
cout<<"The elements in the queue are:";
for(temp=front;temp!=NULL;temp=temp->link)
cout<<temp->info<<" ";
}
}
};
void main()
{
int ch;
QueueLinkImp<int> q1;
do
{
cout<<"\n****MENU****";
cout<<"\n1. Insert\n2. Delete\n3. Display\n4. Exit";
cout<<"\nEnter ur choice:";
cin>>ch;
switch(ch)
{
case 1: q1.Insert();
break;
case 2: q1.Delete();
break;
case 3: q1.Display();
break;
case 4: exit(1);
default: cout<<”Entered Wrong Choice”;
}
}
while(1);
return 0;
}


Thanks
Mukesh Rajput
Write a C++ program to implement the Stack ADT using singly linked list.

A stack is an ordered collection of data items into which new items may be inserted and from which data items may be deleted at one end. Stack are also called Last-In-First-out (LIFO) lists.

Implementation of the above problem:
#include<iostream>
using namespace std;
template<class t>
class node
{
public:
t info;
node *link;
};
template <class t>
class StackADT
{
virtual void Push()=0;
virtual void Pop()=0;
virtual void Top()=0;
virtual void Display()=0;
};
template<class t>
class StackLinkImp : public StackADT<t>
{
public:
t item;
node<t> *temp, *top;
StackLinkImp()
{
top=NULL;
}
void Push()
{
temp=new node<t>;
cout<<"Enter the itemto be insrted on to the stack:";
cin>>item;
if(top==NULL)
temp->link=NULL;
else
temp->link=top;
temp->info=item;
top=temp;
cout<<"Insertion Completed Successfully";
}
void Pop()
{
if(top==NULL)
cout<<"Stack is empty";
else
{
item=top->info;
top=top->link;
cout<<"The deleted element is:"<<item;
}
}
void Top()
{
if(top==NULL)
cout<<"Stack is empty";
else
cout<<"The top element is:"<<top->info;
}
void Display()
{
if(top==NULL)
cout<<"Stack is empty";
else
{
temp=top;
cout<<"The elements in the stack are:";
while(temp!=NULL)
{
cout<<temp->info<<" ";
temp=temp->link;
}
}
}
};
int main()
{
int ch;
StackLinkImp<int> s1;
do
{
cout<<"\n****Menu****";
cout<<"\n1. Push\n2. Pop\n3. Top\n4. Display\n5. Exit";
cout<<"\nEnter ur choice:";
cin>>ch;
switch(ch)
{
case 1: s1.Push();
break;
case 2: s1.Pop();
break;
case 3: s1.Top();
break;
case 4: s1.Display();
break;
case 5: exit(1);
default: cout<<”Entered Wrong Choice”;
}
}
while(1);
return 0;
}


Thanks
Mukesh Rajput

Thursday, 14 December 2017

Write an algorithm to implement the Queue ADT using arrays.

Definition of Queue ADT: Queue is an ordered collection of data such that the data is inserted at one end and deleted from other end. It is a collection of items to be processed on a First-In-First-Out(FIFO) or First Come First Served(FCFS) basics.

Basic Operation Associated on Queues:
1) Insert an item into the Queue.
2) Delete an item into the Queue.

a) Algorithm to insert an item into a Queue Q:
Procudure Insert(Q, SIZE, F, R, ITEM)
Q Array
SIZE Queue size
F front Pointer
R rear pointer
ITEM: information to be inserted at the rear of queue.
Step 1: {Check for Queue overflow}
If R>=SIZE then
Prints(‘Queue overflow’)
Return
Step 2: {Increment rear pointer}
R=R+1
Step 3: {Insert new element at rear end of queue}
Q[R]=ITEM
Step 4: {If initially the queue is empty adjust the front pointer}
If F=0, then F=1

b) Algorithm to delete an item from a Queue Q:
Procedure Delete(Q, F, R)
Q Array
F front Pointer
R rear pointer
ITEM: information to be inserted at the rear of queue.
Step 1: {Check for Queue underflow}
If F=0 then
Prints(‘Queue underflow’)
Return
Step 2: {Delete the queue element at front end and store it into item}
ITEM=Q[F]
Step 3: {If queue is empty after deletion,set front and rear pointers to 0}
If F=R then
F=0
R=0
{Otherwise increment front pointer}
Else
F=F+1
Return(ITEM)

c) Algorithm to display the items from the Queue Q
Procedure Dispaly(Q)
Q Array
Step1: {Check queue values}
If F<0
Prints(‘Queue is empty’)
Step 2: {display Queue values}
For I value F to R
Prints(Q[I])
I=I+1


Thanks
Mukesh Rajput
Write a C++ program to implement the Stack ADT using arrays.

Definition of Stack ADT: A stack is an ordered collection of data items into which new items may be inserted and from which data items may be deleted at one end. Stack are also called Last-In-First-out (LIFO) lists.

Basic terminology associated with stacks:
1) Stack Pointer (TOP): Keeps track of the current position the stack.
2) Overflow: Occurs when we try to insert (push) more information on a stack than it can hold.
3) Underflow: Occurs when we try to delete (pop) an item off a stack, which is empty.
Basic Operation Associated with Stacks:
1) Insert (Push) an item into the stack.
2) Delete (Pop) an item from the stack.

Implementation of the above problem using C++:
#include<iostream>
using namespace std;
#define MAX 10
int top=-1,ch,i;
template <class T>
class StackADT
{
public:
virtual void Push()=0;
virtual void Pop()=0;
virtual void Top()=0;
virtual void Display()=0;
};
template <class T>
class Stack: public StackADT<T>
{
T stk[MAX],ele;
public:
void Push();
void Pop();
void Top();
void Display();
};
template <class T>
void Stack<T>::Push()
{
if(top==(MAX-1))
cout<<"\nThe stack is full";
else
{
cout<<"\nEnter an element:";
cin>>ele;
top++;
stk[top]=ele;
cout<<"\nElement pushed successfully\n";
}
}
template <class T>
void Stack<T>::Pop()
{
if(top==-1)
cout<<"\nThe stack is empty";
else
{
ele=stk[top];
top--;
cout<<"The deleted element is:"<<ele;
}
}
template <class T>
void Stack<T>::Top()
{
if(top==-1)
cout<<"\nThe stack is empty";
else
cout<<"The top element of the stack is:"<<stk[top];
}
template<class T>
void Stack<T>::Display()
{
if(top==-1)
cout<<"\nThe stack is empty";
else
{
cout<<"\nThe elements in the stack are:";
for(i=top;i>=0;i--)
cout<<"\n"<<stk[i];
}
}
int main()
{
Stack<int> s1;
do
{
cout<<"\n****MENU****";
cout<<"\n1. Push\n2. Pop\n3. Top\n4. Display\n5. Exit";
cout<<"\nEnter ur Choice:";
cin>>ch;
switch(ch)
{
case 1: s1.Push();
break;
case 2: s1.Pop();
break;
case 3: s1.Top();
break;
case 4: s1.Display();
break;
case 5: exit(1);
default: cout<<"Enter correct Choice";
}
}
while(true);
return 0;
}


Thanks
Mukesh Rajput