Templates in C++:
Template Functions in C++
Suppose we want to write a function that finds the maximum of two objects. To find the maximum of two integers we would write:
int maximal(int a, int b)
{
if (a > b)
return a;
else
return b;
}
Find the maximum of two doubles using templates in C++
double maximal(double a, double b)
{
if (a > b)
return a;
else
return b;
}
and so on. You can imagine that we would have to write a separate function for every data type (chars, strings, dates, etc.), but notice that the body of each function is exactly the same!!!
Template Function Definition
The definition of a template function depends on an underlying data type.
Example on template function definition program in C++
template <class Item>
Item maximal(Item a, Item b)
{
if (a > b)
return a;
else
return b;
}
The first line is the template prefix, which tells the compiler that Item is a data type that will be filled in later. The "unspecified type" Item is called the template parameter. When a template function is called, the compiler examines the types of the arguments and at that point determines the data type of Item.
Using Template Functions
Template functions are used (called) in exactly the same way as regular functions. For example, if we want to output the maximum of the integers 1000 and 2000, we would write:
cout << maximal(1000, 2000) << endl; //will print 2000
The maximal function is said to be instantiated with the data type Item set to int. Similarly, we could do:
cout << maximal('a', 'z') << endl; //will print 'z'
string s1("foo");
string s2("bar");
cout << maximal(s1, s2) << endl; //will print "foo"
Template Classes in C++
A template class is a class that depends on an underlying data type in the same way a template function depend on an underlying data type.
Template Class Definition
template <class Item>
class Bag
{
...
};
Functions for the Template Class
All member functions of a template class are dependent upon the Item type. Within the template class definition, the compiler knows about this dependency. Outside the template class definition (after the semicolon of the definition) some rules must be followed to tell the compiler about the dependency on the Item data type:
The template prefix template <class Item> is placed immediately before each function prototype and implementation, for example:
template <class Item>
void Bag<Item>::insert(const Item& entry);
Each use of the class name (such as Bag) as the name of a class is changed to the template class name (such as Bag<Item>), for example:
template <class Item>
Bag<Item>::Bag(size_t initial_capacity);
Each use of the complete underlying type name (such as Bag item) may now be shortened to just the type name (such as Item), for example
Item Bag<Item>::grab() const;
Usage
To declare a Bag, you write the class name followed by the name of the data type for the template parameter. For example:
Bag<char> letters; //template parameter is instantiated to char
Bag<double> scores; //template parameter is instantiated to double
Another example :
List <int> list;
list.insert(10); //insert node containing integer 10
STACKS AND QUEUES
One of the most common forms of data organization in computer programs is the ordered or linear list, which is often written as a = (a1, a2, ….., an). A stack is an ordered list in which all insertions and deletions are made at one end, called the top. A queue is an ordered list in which all insertions take place at one end, the rear, whereas all deletions take place at the other end, the front.
The operations of a stack imply that if the elements A, B, C, D and E are inserted into a stack, in that order, then the first element to be removed must be E. Equivalently we say that the last element to be inserted into the stack is the first to be removed. For this reason stacks are sometimes referred to as Last In First Out (LIFO) lists. The operations of a queue require that the first element that is inserted into the queue is the first one to be removed. Thus queues are known as First In First Out (FIFO) lists
Above figure shows the examples
of a stack and queue each containing the same five elements inserted in the
same order.
The simplest way to represent a stack is by using a one-dimensional array, say stack[0 : n-1], where n is the maximum number of allowable entries. The first or bottom element in the stack is stored at stack[0], the second at stack[1], and ith at stack[i-1]. Associated with the array is a variable, typically called top, which points to the top element, to test whether the stack is empty, we ask “if (top<0)”. If not, the topmost element is at stack[top]. Checking whether the stack is full can be done by asking “if (top ³ n-1)”. Two more substantial operations are inserting and deleting elements. The corresponding algorithms are Add and Delete.
1)Write C++ programs to implement the Stack ADT using an array?
#include<iostream.h>
#include<conio.h>
class
stack
{
int m;
int
top;
int
*s;
public
:
stack(int);
void
push(int);
int
pop();
int
isempty();
int
isfull();
void
display();
~stack();
};
stack::stack(int
maxsize)
{
m=maxsize;
top=-1;
s=new
int(m);
}
void
stack::push(int x)
{
if(isfull())
cout<<"Stack
is full"<<endl;
else
{
top++;
s[top]=x;
}
}
int
stack ::pop()
{
if(isempty())
return
-1;
else
{
int
x=s[top];
top--;
return
x;
}
}
int
stack::isempty()
{
if(top==-1)
return
1;
else
return
0;
}
int
stack :: isfull()
{
if(top==m-1)
return
1;
else
return
0;
}
void
stack::display()
{
if(isempty())
cout<<"Empty
list"<<endl;
else
{
for(int
i=top;i>=0;i--)
cout<<s[i]<<"
";
cout<<endl;
}
}
stack::~stack()
{
delete
[] s;
}
void
menu()
{
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Exit"<<endl;
}
void
main()
{
clrscr();
int
ch;
int
x,r;
stack
st(10);
menu();
cin>>ch;
while(ch<4)
{
switch(ch)
{
case
1:
cout<<"Enter
element"<<endl;
cin>>x;
st.push(x);
break;
case
2:
r=st.pop();
if(r==-1)
cout<<"Element
cannot be deleted as stack is empty"<<endl;
else
cout<<"Deleted
element is "<<r<<endl;
break;
case
3:
st.display();
break;
}
menu();
cin>>ch;
}
getch();
}
2) Write a program to implement QUEUE using array?
AbstractDataType queue
{
instances ordered list of elements; one end is called the front; the other is the back;
operations
empty( ) : return true if the queue is empty, return false otherwise;
size( ) : return the number of elements in the queue
front ( ) : return the front element of the queue
back( ) : return the back element of the queue
pop( ) : remove the top element from the queue
push(x) : add element x at the top of the queue
}
#include<iostream.h>
#include<conio.h>
template <class T>
class queue
{
int m;
int f,r;
T *q;
public:
queue();
void insert(T);
T del();
int isfull();
int isempty();
void display();
T first();
T last();
};
template <class T>
queue<T>::queue()
{
f=0;
r=-1;
q=new T(10);
m=10;
}
template <class T>
int queue<T>::isempty()
{
if(r==-1)
return 1;
else
return 0;
}
template <class T>
int queue<T>::isfull()
{
if(r==m-1)
return 1;
else
return 0;
}
template <class T>
void queue<T>::insert(T x)
{
if(isfull())
cout<<"queue full"<<endl;
else
{
r++;
q[r]=x;
}
}
template <class T>
T queue<T>::del()
{
T x;
if(isempty())
return -1;
else
if(r==f)
{
x=q[f];
r=-1;
f=0;
return x;
}
else
{
x=q[f];
f++;
return x;
}
}
template <class T>
T queue<T>::first()
{
if(isempty())
return -1;
else
return q[f];
}
template <class T>
T queue<T>::last()
{
if(isempty())
return -1;
else
return q[r];
}
template <class T>
void queue<T>::display()
{
if(r==-1)
cout<<"Empty queue"<<endl;
else
{
for(int i=f;i<=r;i++)
cout<<q[i]<<" ";
cout<<endl;
}
}
void menu1()
{
cout<<"1.Interger stack"<<endl;
cout<<"2.Float stack"<<endl;
cout<<"3.Character stack"<<endl;
}
void menu2()
{
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.display first elemant"<<endl;
cout<<"5.display last element"<<endl;
cout<<"6.Exit"<<endl;
}
template <class T>
void queueop(queue<T> q)
{
int ch;
T x,r;
menu2();
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:
cout<<"Enter element"<<endl;
cin>>x;
q.insert(x);
break;
case 2:
r=q.del();
if(r==-1)
cout<<"Element cannot be deleted as stack is empty"<<endl;
else
cout<<"Deleted element is "<<r<<endl;
break;
case 3:
q.display();
break;
case 4:
r=q.first();
if(r==-1)
cout<<"Empty queue"<<endl;
else
cout<<"first element is"<<r<<endl;
break;
case 5:
r=q.last();
if(r==-1)
cout<<"Empty queue"<<endl;
else
cout<<"last element is"<<r<<endl;
break;
}
menu2();
cin>>ch;
}
}
void main()
{
clrscr();
int ch;
menu1();
cin>>ch;
if(ch<4)
{
switch(ch)
{
case 1:
{
queue<int> q;
queueop(q);
break;
}
case 2:
{
queue<float> q;
queueop(q);
break;
}
case 3:
{
queue<char> q;
queueop(q);
break;
}
default :
break;
}
}
getch();
}
For Stack single linked list : click here
For Queue with Doubly Linked Lists - Circular queues : click here
For Binary search tree : click here
For Graphs ,BFS , DFS , Kruskal’s Algorithm , Sorting's : click here
For B-Trees , AVL trees : click here
No comments:
Post a Comment