6. AIM: Write a java program for performing various operations on queue using linked list.

Program:
package inter;
import java.util.*;
class Node{
protected int data;
protected Node link;
public Node(){
link = null;
data = 0;
}
public Node(int d,Node n){
data = d;
link = n;
}
public void setLink(Node n){
link = n;
}
public void setData(int d){
data = d;
}
public Node getLink(){
return link;
}
public int getData() {
return data;
}
}
class linkedQueue{
protected Node front, rear;
public int size;
public linkedQueue(){
front = null;
rear = null;
size = 0;
}

public boolean isEmpty(){

return front == null;
}
public int getSize(){
return size;
}
public void insert(int data){
Node nptr = new Node(data, null);
if (rear == null){
front = nptr;
rear = nptr;
}
else {
rear.setLink(nptr);
rear = rear.getLink();
}
 size++ ;
}
public int remove(){
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
Node ptr = front;
front = ptr.getLink();
if (front == null)
rear = null;
size-- ;
return ptr.getData();
}
public int peek() {
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return front.getData();
}
public void display(){
System.out.print("\nQueue = ");
if (size == 0){
System.out.print("Empty\n");
return ;
}
Node ptr = front;
while (ptr != rear.getLink() ){
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}
public class LinkedQueueImplement{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
linkedQueue lq = new linkedQueue();
System.out.println("Linked Queue Test\n");
char ch;
do
{
System.out.println("\nQueue Operations");
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. peek");
System.out.println("4. check empty");
System.out.println("5. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
lq.insert( scan.nextInt() );
break;
case 2 :
try {
System.out.println("Removed Element = "+ lq.remove());
 }
catch (Exception e){
System.out.println("Error : " + e.getMessage());
}
break;
case 3 :
try{
System.out.println("Peek Element = "+ lq.peek());
}
catch (Exception e) {
System.out.println("Error : " + e.getMessage());
}
break;
case 4 :
System.out.println("Empty status = "+ lq.isEmpty());
break;

case 5 :
System.out.println("Size = "+ lq.getSize());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}

lq.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Output:

Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
855

Queue = 5 855
7. AIM: Write a java program for the following using stack

a) Infix to postfix conversion.

b) Expression evaluation.
c) Obtain the binary number for a given decimal number.

Program:

a) package adslab3;
import java.io.*;
class stack
{
char stack1[]=new char[20];
int top;
void push(char ch){
top++;
stack1[top]=ch;
}
char pop(){
char ch;
ch=stack1[top];
top--;
return ch;
}
int pre(char ch){
switch(ch){
case '-':return 1;
case '+':return 1;
case '*':return 2;
case '/':return 2;
}
return 0;
}
boolean operator(char ch){
if(ch=='/'||ch=='*'||ch=='+'||ch=='-')
return true;
else
return false;
}
boolean isAlpha(char ch){
if(ch>='a'&&ch<='z'||ch>='0'&&ch=='9')
return true;
else
return false;
}
void postfix(String str){
char output[]=new char[str.length()];
char ch;
int p=0,i;
for(i=0;i<str.length();i++){
ch=str.charAt(i);
if(ch=='('){
push(ch);
 }
else if(isAlpha(ch)){
output[p++]=ch;
}
else if(operator(ch)){

if(stack1[top]==0||(pre(ch)>pre(stack1[top]))||stack1[top]=='(')
{
push(ch);
}
}
else if(pre(ch)<=pre(stack1[top])){
output[p++]=pop();
push(ch);
}
else if(ch=='('){
while((ch=pop())!='(')
{
output[p++]=ch;
}
}
}
while(top!=0){
output[p++]=pop();
}
for(int j=0;j<str.length();j++){
System.out.print(output[j]);
}
}
}
class InfixToPost
{
public static void main(String[] args)throws Exception
{
String s;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
stack b=new stack();
System.out.println("Enter input string");
s=br.readLine();
System.out.println("Input String:"+s);
System.out.println("Output String:");
b.postfix(s);
}
}
Output: Enter input string
a+b*c
Input String:a+b*c
Output String:
abc*+

b) package adslab3;

import java.util.*;
public class EvaluateExpressionUsingStacks
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
Stack<Integer> op = new Stack<Integer>();
Stack<Double> val = new Stack<Double>();
Stack<Integer> optmp = new Stack<Integer>();
Stack<Double> valtmp = new Stack<Double>();
/* Accept expression */
System.out.println("Evaluation Of Arithmetic Expression Using Stacks Test\n");
System.out.println("Enter expression\n");
String input = scan.next();
input = "0" + input;
input = input.replaceAll("-","+-");
String temp = "";
try {
for (int i = 0;i < input.length();i++)
{
char ch = input.charAt(i);
if (ch == '-')
temp = "-" + temp;
else if (ch != '+' && ch != '*' && ch != '/')
temp = temp + ch;
else
{
val.push(Double.parseDouble(temp));
op.push((int)ch);
temp = "";
}
}
val.push(Double.parseDouble(temp));
char operators[] = {'/','*','+'};
for (int i = 0; i < 3; i++) {
boolean it = false;
while (!op.isEmpty()){
int optr = op.pop();
double v1 = val.pop();
double v2 = val.pop();
if (optr == operators[i]){
if (i == 0) {
valtmp.push(v2 / v1);
it = true;
break;
}
else if (i == 1){
valtmp.push(v2 * v1);
it = true;
break;
}
else if (i == 2){
valtmp.push(v2 + v1);
it = true;
break;
}
 }
else{
valtmp.push(v1);
val.push(v2);
optmp.push(optr);
}
}

while (!valtmp.isEmpty())
val.push(valtmp.pop());
while (!optmp.isEmpty())
op.push(optmp.pop());
if (it)
i--;
}
System.out.println("\nResult = "+val.pop());
}
catch (Exception e) {
System.out.println("Invalid Input");
return;
}
}
}
Output: Evaluation Of Arithmetic Expression Using Stacks Test
Enter expression

3+7

Result = 10.0

c) package adslab3;

import java.util.*;

public class DecimalToBinaryUsingStacks

{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
Stack<Integer> stk = new Stack<Integer>();
System.out.println("Enter decimal number");
int num = scan.nextInt();
while (num != 0){
int d = num % 2;
stk.push(d);
num /= 2;
}
System.out.print("\nBinary equivalent = ");
while (!(stk.isEmpty() )){
System.out.print(stk.pop());
}
 System.out.println();
}
}

Output: Enter decimal number

10

Binary equivalent = 1010

8.AIM: Write a java program to implement various operations on Binary Search Tree
Using Recursive and Non-Recursive methods.

Program: package adslab3;

import java.util.Scanner;
class BSTNode{
BSTNode left, right;
int data;
public BSTNode(){
left = null;
right = null;
data = 0;
}
public BSTNode(int n){
left = null;
right = null;
data = n;
}
public void setLeft(BSTNode n){
left = n;
}
public void setRight(BSTNode n){
right = n;
}
public BSTNode getLeft(){
return left;
}
public BSTNode getRight(){
return right;
}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
}
class BST
{
private BSTNode root;
public BST(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public void insert(int data){
root = insert(root, data);
}
private BSTNode insert(BSTNode node, int data){
if (node == null)
node = new BSTNode(data);
else{
 if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
public void delete(int k){
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k){
BSTNode p, p2, n;
if (root.getData() == k){
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null){
p = rt;
return p;
}
else if (rt == null) {
p = lt;
return p;
}
else{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData()){
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}

public int countNodes() {

return countNodes(root);
}
private int countNodes(BSTNode r){
if (r == null)
return 0;
else{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
public boolean search(int val){
return search(root, val);
}
private boolean search(BSTNode r, int val){
boolean found = false;
while ((r != null) && !found){
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder(){
inorder(root);
}
private void inorder(BSTNode r){
if (r != null){
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
public void preorder(){
preorder(root);
}
private void preorder(BSTNode r){
if (r != null){
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
public void postorder(){
postorder(root);
}
private void postorder(BSTNode r){
if (r != null){
 postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}

public class BinarySearchTree{

public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
BST bst = new BST();
System.out.println("Binary Search Tree Test\n");
char ch;
do
{
System.out.println("\nBinary Search Tree Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. search");
System.out.println("4. count nodes");
System.out.println("5. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
bst.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bst.search( scan.nextInt() ));
break;
case 4 :
System.out.println("Nodes = "+ bst.countNodes());
break;
case 5 :
System.out.println("Empty status = "+ bst.isEmpty());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.print("\nPost order : ");
bst.postorder();
System.out.print("\nPre order : ");
bst.preorder();
System.out.print("\nIn order : ");
bst.inorder();

System.out.println("\nDo you want to continue (Type y or n) \n");

 ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Output:
Binary Search Tree Operations

1. insert
2. delete
3. search
4. count nodes
5. check empty
1
Enter integer element to insert
5

Post order : 5
Pre order : 5
In order : 5
Do you want to continue (Type y or n)

Binary Search Tree Operations

1. insert
2. delete
3. search
4. count nodes
5. check empty
1
Enter integer element to insert
65

Post order : 65 5
Pre order : 5 65
In order : 5 65
9.AIM: Write a java program to implement the following for a graph.
a) BFS b) DFS

Program:

a) package adslab3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {

// Function to perform breadth first search
static void breadthFirstSearch(int[][] matrix, int source){
boolean[] visited = new boolean[matrix.length];
visited[source-1] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(source);
System.out.println("The breadth first order is");
while(!queue.isEmpty()){
System.out.println(queue.peek());
int x = queue.poll();
int i;
for(i=0; i<matrix.length;i++){
if(matrix[x-1][i] == 1 && visited[i] == false){
queue.add(i+1);
visited[i] = true;
}
}
}
}
// Function to read user input
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int vertices;
System.out.println("Enter the number of vertices in the graph");
try{
vertices = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
int[][] matrix = new int[vertices][vertices];
System.out.println("Enter the adjacency matrix");
int i,j;
for(i=0; i<vertices; i++){
for(j=0; j<vertices; j++){
 try{
matrix[i][j] = Integer.parseInt(br.readLine());
}catch (IOException e){
System.out.println("An error occurred");
}
}
}
int source;
System.out.println("Enter the source vertex");
try{
source = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
breadthFirstSearch(matrix,source);
}
}

Output: Enter the number of vertices in the graph

4
Enter the adjacency matrix
1
1
1
0
1
0
0
0
1
1
1
0
0
0
0
1
Enter the source vertex
3
The breadth first order is
3
1
2

b) package adslab3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class DepthFirstSearch {

// Function to perform depth first search
static void depthFirstSearch(int[][] matrix, int source){
boolean[] visited = new boolean[matrix.length];
visited[source-1] = true;
Stack<Integer> stack = new Stack<>();
stack.push(source);
int i,x;
System.out.println("The depth first order is");
System.out.println(source);
while(!stack.isEmpty()){
x = stack.pop();
for(i=0; i<matrix.length; i++){
if(matrix[x-1][i] == 1 && visited[i] == false){
stack.push(x);
visited[i] = true;
System.out.println(i+1);
x = i+1;
i = -1;
}
}
}
}
// Function to read user input
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int vertices;
System.out.println("Enter the number of vertices in the graph");
try{
vertices = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
int[][] matrix = new int[vertices][vertices];
System.out.println("Enter the adjacency matrix");
int i,j;
for(i=0; i<vertices; i++){
for(j=0; j<vertices; j++){
try{
matrix[i][j] = Integer.parseInt(br.readLine());
}catch (IOException e){
System.out.println("An error occurred");
}
 }
}
int source;
System.out.println("Enter the source vertex");
try{
source = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
depthFirstSearch(matrix,source);
}
}

output:

Enter the number of vertices in the graph

4
Enter the adjacency matrix
1
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
Enter the source vertex
2
The depth first order is
2
1
3
4
10.Aim: Write a java program to implement Merge & Heap Sort of given elements.

Program:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class mergeheap {
static void merge(int[] array,int low,int mid,int high){
int i,j,k;
int[] c= new int[high-low+1];
k = 0;
i=low;
j=mid+1;
while(i<=mid && j<=high){
if(array[i]<=array[j]){
c[k++] = array[i++];
}
else{
c[k++] = array[j++];
}
}
while(i<=mid){
c[k++] = array[i++];
}
while(j<=high){
c[k++] = array[j++];
}
k=0;
for(i = low; i<=high; i++){
array[i] = c[k++];
}
}
// Function implementing the merge sort
static void mergeSort(int[] array,int low, int high){
if(high-low+1>1){
int mid = (low+high)/2;
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
merge(array,low,mid,high);
}
}
public static void Heapsort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
 // One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to read the input and display the output
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the size of the array");
try {
size = Integer.parseInt(br.readLine());
} catch (Exception e) {
System.out.println("Invalid Input");
return;
}
int[] array = new int[size];
System.out.println("Enter array elements");
 int i,ch;
for (i = 0; i < array.length; i++) {
try {
array[i] = Integer.parseInt(br.readLine());
} catch (Exception e) {
System.out.println("An error Occurred");
}
}
System.out.println("select choice 1.merge 2.heap");
ch=Integer.parseInt(br.readLine());
System.out.println("The initial array is");
System.out.println(Arrays.toString(array));
switch(ch)
{
case 1:
mergeSort(array,0,array.length-1);
break;
case 2:
Heapsort(array);
break;
default:
System.out.println("Invalid choice ");
}

System.out.println("The sorted array is");

System.out.println(Arrays.toString(array));
}
}

Output:
Enter the size of the array
3
Enter array elements
25
4
154
select choice 1.merge 2.heap
1
The initial array is
[25, 4, 154]
The sorted array is
[4, 25, 154]