Data Structures concepts using C++

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

Thanks for visiting this blog. How is the content?. Your comment is great gift to my work. Cheers.

No comments:

Post a Comment