Stack and Queue as ADT in C++

Stack as ADT

The functions associated with stack are:
empty() – Returns whether the stack is empty

size() – Returns the size of the stack
top() – Returns a reference to the top most element of the stack
push(g) – Adds the element ‘g’ at the top of the stack
pop() – Deletes the top most element of the stack

Example:

#include <iostream>

#include <stack>

using namespace std;

void showstack(stack <int> s)

{

    while (!s.empty())

    {

        cout << '\t' << s.top();

        s.pop();

    }

    cout << '\n';

}

int main ()

{

    stack <int> s;

    s.push(10);

    s.push(30);

    s.push(20);

    s.push(5);

    s.push(1);

    cout << "The stack is : ";

    showstack(s);

    cout << "\ns.size() : " << s.size();

    cout << "\ns.top() : " << s.top();

    cout << "\ns.pop() : ";

    s.pop();

    showstack(s);

    return 0;

}

Output:

The stack is :       1      5      20     30     10

s.size() : 5

s.top() : 1

s.pop() :     5      20     30     10

Queue As ADT

The functions supported by queue are :

1.      empty() – Returns whether the queue is empty.

2.      size() – Returns the size of the queue.

3.      queue::swap() in C++ STL: Exchange the contents of two queues but the queues must be of same type, although sizes may differ.

4.      queue::emplace() in C++ STL: Insert a new element into the queue container, the new element is added to the end of the queue.

5.      queue::front() and queue::back() in C++ STL– front() function returns a reference to the first element of the queue. back() function returns a reference to the last element of the queue.

6.      push(g) and pop() – push() function adds the element ‘g’ at the end of the queue. pop() function deletes the first element of the queue.

#include <iostream>

#include <queue>

using namespace std;

void showq(queue <int> q1)

{

    while (!q1.empty())

    {

        cout << '\t' << q1.front();

        q1.pop();

    }

    cout << '\n';

}

int main()

{

    queue <int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    cout << "The queue is : ";

    showq(q);

    cout << "\nsize() : " << q.size();

    cout << "\nfront() : " << q.front();

    cout << "\nback() : " << q.back();

    q.pop();

    cout << "\nThe queue after pop() : ";

    showq(q);

    return 0;

}

Output:

The queue is :       10     20     30

size() : 3

front() : 10

back() : 30

The queue after pop() :    20     30

Create a binary Tree and show level wise traversing in C++

Create a Binary Tree  and show level wise traversing in C++

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

class Node
{
char data[10];
Node *left;
Node * right;
friend class Tree;
};
class Tree
{
public:
Node *temp,*root;
Tree();
void create();
void insert(Node *root,Node *New);
void display();
};
Tree::Tree()
{
temp=NULL;
root=NULL;
}
void Tree::create()
{
temp=new Node;
temp->left=temp->right=NULL;
cout<<"\nEnter the Data: ";
cin>>temp->data;
if(root==NULL)
{
root=temp;
}
else
{
insert(root,temp);
}
}
void Tree::insert(Node *root,Node *temp)
{
char ans;
cout<<"Where to insert "<<temp->data<<" at Left(L) OR Right(R) "<<root->data<<"? ";
cin>>ans;
if(ans=='L'||ans=='l')
{
if(root->left==NULL)
root->left=temp;
else
insert(root->left,temp);
}
else
{
if(root->right==NULL)
root->right=temp;
else
insert(root->right,temp);
}
}
void Tree :: display()
{
queue<Node *> q;
if(root==NULL)
{
cout<<"NULL Tree";
return;
}
q.push(root);
while(!q.empty())
{
Node *temp = q.front();
q.pop();
cout <<temp->data<<"\t" ;
if(temp->left){  q.push(temp->left); }
if(temp->right){  q.push(temp-> right); }
}
}
int main()
{
Tree tr;
int i=0;
do
{
if(i==0)
{
cout<<"\n***Chapter Data***";
tr.create();
i++;
}
if(i==1||i==2)
{
cout<<"\n***Section Data***";
tr.create();
i++;
}
if(i==3||i==4||i==5||i==6)
{
cout<<"\n***Sub-Section Data***";
tr.create();
i++;
}
if(i==7)
{
cout<<"\nLevel wise Tree is:";
tr.display();
break;
}
}while(1);
}


Output:

***Chapter Data***
Enter the Data: 10

***Section Data***
Enter the Data: 5
Where to insert 5 at Left(L) OR Right(R) 10? L

***Section Data***
Enter the Data: 7
Where to insert 7 at Left(L) OR Right(R) 10? R

***Sub-Section Data***
Enter the Data: 1
Where to insert 1 at Left(L) OR Right(R) 10? L
Where to insert 1 at Left(L) OR Right(R) 5? L

***Sub-Section Data***
Enter the Data: 12
Where to insert 12 at Left(L) OR Right(R) 10? R
Where to insert 12 at Left(L) OR Right(R) 7? L

***Sub-Section Data***
Enter the Data: 14
Where to insert 14 at Left(L) OR Right(R) 10? L
Where to insert 14 at Left(L) OR Right(R) 5? R

***Sub-Section Data***
Enter the Data: 66
Where to insert 66 at Left(L) OR Right(R) 10? L
Where to insert 66 at Left(L) OR Right(R) 5? R
Where to insert 66 at Left(L) OR Right(R) 14? L

Level wise Tree is:10 5 7 1 14 12 66

Program for Binary Search Tree in C++

Program for Binary Search Tree in C++

#include"iostream"
#include<string.h>
using namespace std;

class node
{
public:
int data;
class node  *left;
class node * right;
};

class dict
{
public:
node *root;
void create();
void disp_asc(node *);
void insert(node * root,node *temp);
int search(node *,int);
node* del(node *,int);
node * min(node *);
};

void dict :: create()
{
class node *temp;
int ch;

do
{
temp = new node;
cout<<"\nEnter Data:";
cin>>temp->data;

temp->left = NULL;
temp->right = NULL;

if(root == NULL)
{
root = temp;
}
else
{
insert(root, temp);
}
cout<<"\nDo u want to add more (y=1/n=0):";
cin>>ch;
}
while(ch == 1);

}

void dict ::  insert(node * root,node *temp)
{
if(temp->data < root->data)
{
if(root->left == NULL)
root->left = temp;
else
insert(root->left,temp);
}
else
{
if(root->right == NULL)
root->right = temp;
else
insert(root->right,temp);
}

}

void dict:: disp_asc(node * root)
{
if( root != NULL)
{
disp_asc(root->left);
cout<<"\n Data :"<<root->data;

disp_asc(root->right);
}
}

int dict :: search(node * root,int k)
{
int c=0;
while(root != NULL)
{
c++;
if(k == root->data)
{
cout<<"\nNo of Comparisons:"<<c;
return 1;
}
if(k < root->data)
root = root->left;
if(k > root->data)
root = root->right;
}

return -1;
}
node* dict :: del(node * root,int k)
{
node *temp;

if(root == NULL)
{
cout<<"\nElement No Found";
return root;
}

if (k < root->data)
{
root->left = del(root->left, k);
return root;
}
if (k > root->data)
{
root->right = del(root->right, k);
return root;
}

if (root->right==NULL&&root->left==NULL)
{
temp = root;
delete temp;
return NULL;
}
if(root->right==NULL)
{
temp = root;
root = root->left;
delete temp;
return root;
}
else if(root->left==NULL)
{
temp = root;
root = root->right;
delete temp;
return root;
}
temp = min(root->right);
root->data=temp->data;
root->right = del(root->right, temp->data);
return root;
}

node * dict :: min(node *q)
{
while(q->left != NULL)
{
q = q->left;
}
return q;
}



int main()
{
int ch;
int k;
dict d;
d.root = NULL;
do
{
cout<<"\n \t \t \t \t MENU ";
cout<<"\n \t \t \t \t ==== ";

cout<<"\n1.Create Tree \n2.Display Tree \n3.Search Data \n4.Delete Data \nEnter your choice:";
cin>>ch;

switch(ch)
{
case 1: d.create();
break;
case 2: if(d.root == NULL)
{
cout<<"\nNo any data";
}
else
{
d.disp_asc(d.root);
}
break;
case 3:
if(d.root == NULL)
{
cout<<"\nTree is Empty. First add data then try again ";
}
else
{
cout<<"\nEnter data which u want to search:";
cin>>k;
if( d.search(d.root,k) == 1)
cout<<"\nData Found";
else
cout<<"\nData Not Found";
}
break;
case 4:
if(d.root == NULL)
{
cout<<"\nTree is Empty. First add data then try again ";
}
else
{
cout<<"\nEnter data which u want to delete:";
cin>>k;
if(d.root == NULL)
{
cout<<"\nNo any data";
}
else
{
d.root = d.del(d.root,k);
}
}
}
}
while(ch<=5);
return 0;
}


Output:


  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:1

Enter Data:40

Do u want to add more (y=1/n=0):1

Enter Data:13

Do u want to add more (y=1/n=0):1

Enter Data:50

Do u want to add more (y=1/n=0):1

Enter Data:5

Do u want to add more (y=1/n=0):0

  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:2

 Data :5
 Data :13
 Data :40
 Data :50
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:3

Enter data which u want to search:5

No of Comparisons:3
Data Found
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:4

Enter data which u want to delete:40

  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:2

 Data :5
 Data :13
 Data :50
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice: