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:

Implement Doubly Linked List in C

Implement Doubly Linked List

#include <stdio.h>
#include <malloc.h>
#include <process.h>
void create();
void insert_at_beg();
void insert_at_end();
void insert_after_pos();
void del();
void display_forward();
void display_backward();
struct node  {
int info;
struct node* next;
struct node* prev;
}*start=NULL;
int data,item,n1,pos,i,m;
int main()
{
int n;
setbuf(stdout, NULL);
printf("\n****Doubly Linked List*****\n");
printf("\n1.Create\n2.Insert at Beginning\n3.Insert at End\n4.Insert After Position\n5.Delete\n6.Display Forward \n7.Display Backward\n8.Exit\n");
while(1)
{
printf("\nEnter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)\n");
scanf("%d",&n);
switch(n)
{
case 1:
create();
break;
case 2:
insert_at_beg();
break;
case 3:
insert_at_end();
break;
case 4:
insert_after_pos();
break;
case 5:
del();
break;
case 6:
display_forward();
break;
case 7:
display_backward();
break;
case 8:
exit(0);
default:
printf("\nWrong Choice !!\n");
}
}
return 0;
}
void create()
{
int data;
struct node *tmp;
printf("\nEnter the first element to be inserted :\n");
scanf("%d",&data);
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->prev=NULL;
tmp->next=NULL;
if(start == NULL)
start = tmp;
display_forward();
}
void insert_at_beg()
{
int data;
struct node *tmp;
printf("\nEnter the element to be inserted :\n");
scanf("%d",&data);
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->prev=NULL;
tmp->next=NULL;
if(start == NULL)
start = tmp;
else
{
start->prev = tmp;
tmp->next = start;
start = tmp;
}
display_forward();
}
void insert_at_end()
{
int data;
struct node *q,*tmp;
printf("\nEnter the element to be inserted :\n");
scanf("%d",&data);
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->prev=NULL;
tmp->next=NULL;
if(start == NULL)
start = tmp;
else
{
q=start;
while(q->next != NULL)
q = q->next; // Go To last Node
q->next = tmp;
tmp->prev = q;
}
display_forward();
}
void insert_after_pos()
{
int data;
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
printf("\nEnter the element to be inserted :\n");
scanf("%d",&data);
tmp->info=data;
tmp->prev=NULL;
tmp->next=NULL;
if(start==NULL)
{
start=tmp;
}
else
{
printf("Enter index after which element to be inserted :\n");
scanf("%d",&pos);
q=start;
for(i=0;i<pos;i++)
{
q = q->next;
}
tmp->next = q->next;
if(q->next!=NULL)
{
q->next->prev=tmp;
}
q->next = tmp;
tmp->prev=q;
display_forward();
}
}
void del()
{
struct node *tmp,*q,*prev;
printf("Enter the element to be deleted :\n");
scanf("%d",&data);
if(start->info==data)  //deletion of first node
{
tmp=start;
if(tmp->next!=NULL)
{
start->next->prev=NULL;
}
start=start->next;
free(tmp);
display_forward();
return;
}
q=start;
while(q->next->next!=NULL)  //deletion of middle node
{
if(q->next->info==data)
{
prev=q->next->prev;
tmp=q->next;
q->next=tmp->next;
q->next->prev=prev;
free(tmp);
display_forward();
return;
}
q=q->next;
}
if(q->next->info==data)  //deletion at end
{
tmp=q->next;
q->next=NULL;
free(tmp);
display_forward();
return;
}
printf("\nElement not found \n");
}
void  display_forward()
{
struct node *q;
if(start==NULL)
printf("List is empty!!\n");
else
{
printf("**** Elements in Doubly Linked List ****\n");
q=start;
while(q!=NULL)
{
printf("%d\t",q->info);
q=q->next;
}
}
}
void display_backward()
{
struct node *q = start;
while(q->next!=NULL)
{
q=q->next;
}
while(q!=start)
{
printf("%d\t",q->info);
q=q->prev;
}

printf("%d\t",q->info);
}


Output:

****Doubly Linked List*****

1.Create
2.Insert at Beginning
3.Insert at End
4.Insert After Position
5.Delete
6.Display Forward
7.Display Backward
8.Exit

Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)
1

Enter the first element to be inserted :
10
**** Elements in Doubly Linked List ****
10
Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)
2

Enter the element to be inserted :
20
**** Elements in Doubly Linked List ****
20 10
Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)
3

Enter the element to be inserted :
30
**** Elements in Doubly Linked List ****
20 10 30
Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)
7
30 10 20
Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)
6
**** Elements in Doubly Linked List ****
20 10 30
Enter Your Choice :(1.Create 2.Insert at Beg. 3.Insert at End 4.Insert after Pos. 5.Delete 6.Display forward 7. Display backward 8.Exit)