Data Structures LAB Program for the academic year 2024-25
1. Write a program to implement basic stack operations
#include <iostream>
Using namespace std;
class Stack
{
int top;
public:
int s[4], size;
Stack()
{
top = -1;
size=4;
}
void push(int x);
int pop();
int first();
};
void Stack::push(int x)
{
if (top<=size-1)
{
top++;
s[top]=x;
}
else
cout << “No elements in the stack”;
}
int Stack::pop()
{
if (top < 0)
{
cout << "No Elements in the Stack";
return 0;
}
else
{
int x = s[top];
top--;
return x;
}
}
int Stack::top()
{
if (top < 0)
{
cout << "Stack is Empty";
return 0;
}
else
{
int x = s[top];
return x;
}
}
int main()
{
Stack ob;
ob..push(10);
ob.push(20);
ob.push(30);
ob.push(40);
cout<<”The top element in the stack:”<< ob.first();
cout << ob.pop() << " deleted from stack\n";
cout<<”Now the top element in the stack:”<< ob.first();
return 0;
}
Output:
The top elements in the stack : 40
40 deleted form stack
Now the top element in the stack: 30
2. Write a Program to reverse a string using Stack
#include<bits/stdc++.h>
using namespace std;
class Stack
{
public:
int top;
unsigned capacity;
char* array;
};
Stack* createStack(unsigned capacity)
{
Stack* stack=new Stack();
stack->capacity=capacity;
stack->top=-1;
stack ->array=new char [(stack->capacity * sizeof(char))];
return stack;
}
int isFull(Stack* stack)
{
return stack->top==stack->capacity-1;
}
int isEmpty(Stack* stack)
{
return stack->top==-1;
}
void push(Stack* stack, char item)
{
if(isFull(stack)) return;
stack->array[++stack->top]=item;
}
char pop(Stack* stack)
{
if(isEmpty(stack)) return -1;
return stack->array[stack->top--];
}
void reverse(char str[])
{
int n = strlen(str);
Stack* stack=createStack(n);
int i;
for(i=0;i<n;i++)
push(stack,str[i]);
for(i=0; i<n; i++) str[i]=pop(stack);
}
int main()
{
char str[]="friends";
reverse(str);
cout<<"Reversed String is……. "<<str;
return 0;
}
Output:
Reversed String is ……..sdneirf
3. Write a Program to find factorial of given no using Recursion
#include<iostream>
using namespace std;
int factorial(int n)
{
if(n==0)
return(1);
else
{
return(n*factorial(n-1));
}
}
int main()
{
int fact, value;
cout<<"Enter any number: ";
cin>>value;
fact=factorial(value);
cout<<"Factorial of a number is: "<<fact<<endl;
}
Output:
Enter any number 4
Factorial of a number is: 24
4 . Write a Program to create a Queue by using array.
#include<iostream>
using namespace std;
class Queue
{
int a[4];
int rear, front, size;
public:
Queue()
{
rear =-1;
front = 0;
size=4;
}
void enqueue(int x);
void dequeue();
void display();
};
void Queue :: enqueue(int x)
{
if( rear == size-1)
cout << "Queue is full";
else
{
rear++;
a[rear] = x;
}
}
void Queue :: dequeue()
{
cout<< a[front];
front++;
}
void Queue :: display()
{
for( int i = front; i <= rear; i++)
cout << a[i] << endl;
}
void main()
{
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
cout<<”Elements in the Q are”;
q.display();
cout<<”Deleted element from the Q is:”;
q.dequeue();
cout<<”\nNow elements in the Q are\n”;
q.display();
}
Output:
Elements int Q are
10
20
30
40
Deleted element form the Q is : 10
Now elements in the Q are
20
30
40
5. Write a Program to create, insert, delete and
display linked program
#include <iostream>
using namespace std;
struct Node
{
int num;
Node *next;
};
struct Node *head=NULL;
void insertNode(int n)
{
struct Node *new_node=new Node;
new_node->num=n;
new_node->next=head;
head=new_node;
}
void display()
{
cout<<"The list contains the data entered:\n";
struct Node *temp = head;
while(temp!=NULL)
{
cout<<temp->num<<" ";
temp=temp->next;
}
cout<<endl;
}
void deletenode()
{
if(head!=NULL)
{
Node *temp=head;
head=head->next;
}
}
int main()
{
insertNode(1);
insertNode(3);
insertNode(5);
insertNode(7);
insertNode(9);
insertNode(11);
display();
deletenode();
display();
return 0;
}
Output:
The list contains the data entered: 11 9 7 5 3 1
The list contains the data entered:
9 7 5 3 1
6. Write a program to implement Inorder traversal of Binary Tree
# include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
void inorderTraversal(Node* root)
{
if (root == NULL)
return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
inorderTraversal(root);
return 0;
}
Output
42513
7. Write a program to implement Preorder traversal of Binary Tree
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
void preorderTraversal(Node* root)
{
if (root == NULL)
return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
preorderTraversal(root);
return 0;
}
Output
12453
8. Write a program to implement Postorder traversal of Binary Tree
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
void postorderTraversal(Node* node)
{
if (node == NULL)
return;
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->data << " ";
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
postorderTraversal(root);
return 0;
}
Output
45231
9. Write a Program to implement Linear Search method.
#include<iostream>
using namespace std;
int main()
{ int list[]={10,20,40,30,50};
int size,i,s;
size= sizeof(list)/sizeof(list[0]);
cout<<"Enter the element to be Search"; cin>>s;
for(i = 0; i < size; i++)
{
if(s == list[i])
{
cout<<"Element is found at position"<<i+1;
break;
}
}
if(i == size)
cout<<"Given element is not found in the list!!!";
}
Output:
Enter the element to be search 30
Element is found at position 4
10. Write a Program to implement Binary Search algorithm.
#include<iostream>
using namespace std; int main()
{
int list[] = {10,20,30,40,50,60,70,80,80,100};
int first, last, middle, size, i, s;
size= sizeof(list)/sizeof(list[0]);
cout<<"Enter the element to be Search"; cin>>s;
first = 0;
last = size - 1;
middle = (first+last)/2;
while (first <= last)
{
if (list[middle] < s) first = middle + 1;
else if (list[middle] == s)
{
cout<<"Element is found at position"<<middle+1;
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
cout<<"Given element is not found in the list!!!";
Output:
Enter the element to be search: 60
Element is found at position 6
11. Write a Program to implement Bubble Sort.
#include<iostream>
using namespace std;
void bubblesrt( int a[], int n )
{
int i, j,t=0;
for(i = 0; i < n; i++)
for(j = 1; j < (n-i); j++)
if(a[j-1] > a[j])
{
t = a[j-1]; a[j-1]=a[j]; a[j]=t;
}
}
int main()
{
int i,size;
int array[] = {12,9,4,99,120,1,3,10};
size=sizeof(array)/sizeof(array[i]);
cout<<"Values Before sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" "; cout<<endl; bubblesrt(array, size);
cout<<"Values after sorting:"<<endl; for(i = 0; i < size; i++)
cout<< array[i]<<" ";
return 0;
}
Output:
Values Before sorting:
12 9 4 99 120 1 3 10
Values after sorting:
1 3 4 9 10 12 99 120
12. Write a Program to implement Insertion Sort.
#include<iostream>
using namespace std;
void insertionsrt(int array[], int n)
{
int i,j;
for (i = 1; i < n; i++)
{
int j = i;
int B = array[i];
while ((j > 0) && (array[j-1] > B))
array[j] = array[j-1]; j--;
}
array[j] = B;
}
int main()
{
int i,size;
int array[] = {12,9,4,99,120,1,3,10};
size=sizeof(array)/sizeof(array[0]);
cout<<"Values Before sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
cout<<endl;
insertionsrt(array, size);
cout<<"Values after sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
}
Output:
Values Before sorting:
12 9 4 99 120 1 3 10
Values after sorting:
1 3 4 9 10 12 99 120
13. Write a Program to implement Selection Sort.
#include<iostream>
using namespace std;
void selectionsort(int array[], int n)
{
int x,indexofmin;
for(x=0; x<n; x++)
{
indexofmin = x;
for(int y=x; y<n; y++)
if(array[indexofmin]>array[y]) indexofmin = y;
int temp = array[x];
array[x] = array[indexofmin];
array[indexofmin] = temp;
}
}
int main()
{
int array[] = {12,9,4,99,120,1,3,10};
int i,size;
size=sizeof(array)/sizeof(a
rray[0]); cout<<"Values
Before sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
cout<<endl;
selectionsort(array, size);
cout<<"Values after sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
}
Output:
Values Before sorting:
12 9 4 99 120 1 3 10
Values after sorting:
1 3 4 9 10 12 99 120
14. Write a Program to implement Quick Sort.
#include<iostream>
using namespace std;
void quicksort(int array[],int low, int n)
{ int mid,t;
int lo = low;
int hi = n;
if (lo >= n)
return;
mid = array[(lo + hi) / 2];
while (lo < hi)
{
while (lo<hi && array[lo] < mid) lo++;
while (lo<hi && array[hi] > mid) hi--;
if (lo < hi)
{
t = array[lo]; array[lo] = array[hi]; array[hi] = t;
}
}
if (hi < lo)
{
int t = hi; hi = lo; lo = t;
}
quicksort(array, low, lo);
quicksort(array, lo == low ? lo+1 : lo, n);
}
int main()
{
int array[] = {12,9,4,99,120,1,3,10,13};
int i,size; size=sizeof(array)/sizeof(array[0]);
cout<<"Values Before sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
cout<<endl;
quicksort(array,0,size-1);
cout<<"Values after sorting:"<<endl;
for(i = 0; i < size; i++)
cout<< array[i]<<" ";
}
Output:
Values Before sorting:
12 9 4 99 120 1 3 10 13
Values after sorting:
1 3 4 9 10 12 13 99 120
15. Write a Program to implement Heap Sort.
#include <iostream>
using namespace std;
void MaxHeapify(int a[], int i, int n)
{
int j, temp; temp = a[i]; j = 2*i;
while (j <= n)
{
if (j < n &&
a[j+1] > a[j]) j
= j+1;
if (temp > a[j])
break;
else
if (temp <= a[j])
{
a[j/2] = a[j]; j = 2*j;
}
}
a[j/2] = temp; return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i]; a[i] = a[1]; a[1] = temp;
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--) MaxHeapify(a, i, n);
}
int main()
{
int n, i,size;
int array[] = {12,9,4,99,120,1,3,10,13};
size=sizeof(array)/sizeof(array[0]);
cout<<"Values Before sorting:"<<endl;
for(i = 1; i < size; i++)
cout<< array[i]<<" "; cout<<endl;
Build_MaxHeap(array, size-1);
HeapSort(array, size-1);
cout<<"Values after sorting:"<<endl;
for(i = 1; i < size; i++)
cout<< array[i]<<" ";
}
Output:
Values Before sorting:
12 9 4 99 120 1 3 10 13
Values after sorting:
1 3 4 9 10 12 13 99 120
