Programs Sssssssss

Program:
import java.util.*;
/**
*
* @author hp <
*/
public class ListAdtArray {
public static void main(String args[])
{
int n,pos,x, del, count=0,elem;
int a[] = new int[50];
Scanner s=new Scanner(System.in);
System.out.println("Enter the array length:");
n=s.nextInt();
System.out.println("Enter "+n+" elements:");
for(int i=0;i<n;i++)
{
a[i]=s.nextInt();
}
System.out.println("ListADT Array");
char ch;
/* Perform list operations */
do
{
System.out.println("ListADT Array Operations\n");
System.out.println("1. insert");
System.out.println("2. delete");
System.out.println("3. display");
System.out.println("4. Search");
System.out.println("Enter your choice");
int choice = s.nextInt();
switch (choice)
{
case 1 :
System.out.print("Enter the index value where you want to insert
element:");
pos = s.nextInt();
System.out.print("Enter the element you want to insert:");
x = s.nextInt();
n++;
for(int i=n; i>pos; i--)
{
a[i] = a[i-1];
}
a[pos] = x;
System.out.print("Element inserted Successfully..!!\n");
System.out.print("Array elements are :\n");
for(int i=0; i<n; i++)
{
System.out.print(a[i]+ " ");
}
break;
case 2 :
System.out.print("Enter Element to be Delete : ");
del = s.nextInt();
{
if(a[i] == del)
{
for(int j=i; j<(n-1); j++)
{
a[j] = a[j+1];
}
count++;
break;
}
}
if(count==0)
{
System.out.print("Element Not Found..!!");
}
else
{
System.out.print("Element Deleted Successfully..!!\n");
n=n-1;
{
}
}
break;
case 3 :
{
}
break;
case 4:
int i;
System.out.println("enter the element you want to search :");
elem=s.nextInt();
for(i=0; i<n; i++)
{
if(a[i]==elem)
{
System.out.println("Element found at position : "+(i+1));
}
}
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.println("\nDo you want to continue (Type y or n)");

ch = s.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
Output:
Enter the array length:
5
Enter 5 elements:
32 21 45 34 65
ListADT Array
ListADT Array Operations
1. insert
2. delete
3. display
4. Search
Enter your choice
1
Enter the index value where you want to insert element:3
Enter the element you want to insert:46
Element inserted Successfully..!!
Array elements are :
32 21 45 46 34 65
Do you want to continue (Type y or n)
y
1. insert
2. delete
3. display
4. Search
Enter your choice
2
Enter Element to be Delete : 21
Element Deleted Successfully..!!
32 45 46 34 65
y
1. insert
2. delete
3. display
4. Search
Enter your choice
4
enter the element you want to search :
34
Element found at position : 4

y
1. insert
2. delete
3. display
4. Search
Enter your choice
3
32 45 46 34 65
n
BUILD SUCCESSFUL (total time: 1 minute 4 seconds)
Program:
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size ;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print("\nSingly Linked List = ");
if (size == 0)
{
System.out.print("empty\n");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
}
System.out.print(ptr.getData()+ "\n");
}
}
/* Class SinglyLinkedList */
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
linkedList list = new linkedList();
System.out.println("Singly Linked List Test\n");
char ch;
/* Perform list operations */
do
{
System.out.println("\nSingly Linked List Operations\n");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println("Invalid position\n");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" \n");
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display List */
list.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:
Singly Linked List Test
Singly Linked List Operations
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
1
Enter integer element to insert
23
Singly Linked List = 23
2. insert at end
5. check empty
6. get size
2
35
Singly Linked List = 23->35
2. insert at end
5. check empty
6. get size
3
67
Enter position
2
Singly Linked List = 23->67->35
2. insert at end
5. check empty
6. get size
4
Enter position
1
2. insert at end
5. check empty
6. get size
5
Empty status = false
2. insert at end
5. check empty
6. get size
6
Size = 2
2. insert at end
5. check empty
6. get size
4
Enter position
2
2. insert at end
5. check empty
6. get size
4
Enter position
6
Invalid position

y
2. insert at end
5. check empty
6. get size
4
Enter position
1
Singly Linked List = empty
2. insert at end
5. check empty
6. get size
5
Empty status = true
Singly Linked List = empty
n
BUILD SUCCESSFUL (total time: 2 minutes 19 seconds)
Program:
import java.util.*;
class Queen
{
//number of queens
private static int N;
//chessboard
private static int[][] board = new int[100][100];
//function to check if the cell is attacked or not

private static boolean isAttack(int i,int j)
{
int k,l;
//checking if there is a queen in row or column
for(k=0;k<N;k++)
{
if((board[i][k] == 1) || (board[k][j] == 1))
return true;
}
//checking for diagonals
for(k=0;k<N;k++)
{
for(l=0;l<N;l++)
{
if(((k+l) == (i+j)) || ((k-l) == (i-j)))
{
if(board[k][l] == 1)
return true;
}
}
}
return false;
}
private static boolean nQueen(int n)

{
int i,j;
//if n is 0, solution found
if(n==0)
return true;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
//checking if we can place a queen here or not
//queen will not be placed if the place is being attacked
//or already occupied
if((!isAttack(i,j)) && (board[i][j]!=1))
{
board[i][j] = 1;
//recursion
//wether we can put the next queen with this arrangment or not
if(nQueen(n-1)==true)
{
return true;
}
board[i][j] = 0;
}
}
}
return false;
}

{
Scanner s = new Scanner(System.in);
//taking the value of N
System.out.println("Enter the value of N for NxN chessboard");
N = s.nextInt();
int i,j;
//calling the function
nQueen(N);
//printing the matix
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
System.out.print(board[i][j]+"\t");
System.out.print("\n");
}
}
}
Output:
First run:
Enter the value of N for NxN chessboard
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
BUILD SUCCESSFUL (total time: 12 seconds)
Second run:
Enter the value of N for NxN chessboard
6
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
1 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 1 0
Program:
import java.io.*;
class QueueImpl
{
static int i,front,frontelem,rear,item,max=5,ch;
static int a[]=new int[5];
QueueImpl()
{
front=-1;
rear=-1;
}
public static void main(String args[])throws IOException
{
System.out.println("--Queue Operations--");
while((boolean)true)
{
try
{
System.out.println("Select Option 1.Enqueue 2.Dequeue 3.display
4.Rear 5.front 6.Exit");
BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
ch=Integer.parseInt(br.readLine());
}
catch(Exception e)
{ }
if(ch==6)
break;
else
{
switch(ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
rear();
break;
case 5:
front();
break;
}
}
}
}
static int rear(){
item=a[rear];
System.out.println("Rear element is : "+item);
return a[rear];
}
static int front(){
frontelem=front+1;
item=a[frontelem];
System.out.println("Front element is : "+item);
return a[front];
}
// static boolean isQueueFull(){
// return (maxSize == currentSize);
// }
//
// static boolean isQueueEmpty(){
// return (currentSize == 0);
// }
static void insert()
{
if(rear>=(max-1))
{
System.out.println("Queue is Full");
}
else
{
try
{
System.out.println("Enter the Element: ");
item=Integer.parseInt(br.readLine());
}
catch(Exception e)
{}
rear=rear+1;
a[rear]=item;
}
}
static void delete()
{
if(front==-1)
{
System.out.println("Queue is Empty");
}
else
{
front=front+1;
item=a[front];
System.out.println("Deleted Item: "+item);
}
}
static void display()
{
System.out.println("Elements in the Queue are:");
for(int i=front+1; i<=rear; i++)
{
System.out.println(a[i]);
}
}
}
Output:
--Queue Operations--
Select Option 1.Enqueue 2.Dequeue 3.display 4.Rear 5.front 6.Exit
1
Enter the Element:
14
1
Enter the Element:
63
1
Enter the Element:
75
3
Elements in the Queue are:
14
63
75
4
Rear element is : 75
5
Front element is : 14
2
Deleted Item: 14
6
Program:
import java.util.Scanner; // to user input

public class CircularQueue
{
public static void main(String args[]) //entry point
{
int a[]=new int[10]; //array initialization
int max=5,f,r,ch,x; //variables declaration
f=-1;
r=-1; //intially queue empty
do
{
System.out.println("1:enqueue 2:dequeue 3:queuerear 4:queuefront"
+ " 5:display 6:exit" + "\n" + "enter ur choice:");
Scanner s=new Scanner(System.in); //to read input
ch=s.nextInt(); //reading value
if(ch==6)
{
System.out.println("exiting..."); //to exit from loop
break;
}
else
{
switch(ch) //for choosing one of the options
{
case 1:
System.out.println("enter element:");
x=s.nextInt();
if(r==max) //reached maxsize
System.out.println("queue is full");
else if(f==-1&&r==-1)
{
f=0;
r=0;
}
else if(r==(max-1)&&f!=0)
r=0;
else
r=(r+1)%max;
a[r]=x; //inserting value
break;
case 2:
if(r==-1&&f==-1) //reached minsize
System.out.println("queue is empty");
else if(f==r)
{
f=-1;
r=-1;
}
else if(f==max-1)
f=0;
else
f++; //increment front
break;
case 3:
System.out.println("queue rear element:"+a[r]);
break;
case 4:
System.out.println("queue front element:"+a[f]);
break;
case 5:
System.out.println("queue elements are:");
for(int i=f;i<=r;i++)
System.out.println(a[i]); //displaying all elements
break;
default: //if incorrect option
System.out.println("enter correct choice");
break;
}
}
}while(true); //repeats until false

}
}
Output:
1:enqueue 2:dequeue 3:queuerear 4:queuefront 5:display 6:exit

enter ur choice:
1
enter element:
24
enter ur choice:
1
enter element:
28
enter ur choice:
5
queue elements are:
24
28
enter ur choice:
3
queue rear element:28
enter ur choice:
3
enter ur choice:
4
queue front element:24
enter ur choice:
6
exiting...
Program:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Palindrome

{
public static void main(String[ ] args)
{
Scanner input = new Scanner(System.in);
String inputString;
System.out.print("Enter string: ");
inputString = input.next( );
if (isPalindrome( inputString )){

System.out.println("That is a palindrome.");
}
else{
System.out.println("That is not a palindrome.");
}
}
public static boolean isPalindrome(String input)

{
Queue<Character> q = new LinkedList<Character>( );
Stack<Character> s = new Stack<Character>( );
char letter;
int i;
for (i = 0; i < input.length( ); i++)

{
letter = input.charAt(i);
q.add(letter);
s.push(letter);
}
while (!q.isEmpty( ))
{
if (q.remove( ) != s.pop( ))
return false;
}
return true;
}
}
Output:
First run:
Enter string: radar
That is a palindrome.
Second run:
Enter string: abbadbf
That is not a palindrome.
Program:
import java.lang.*;
import java.util.*; //to read user input
public class StackLinkedList
{
{
int max=10,top,ch,x; //variables declaration
top=-1; //intially stack empty
StackLinkedList l=new StackLinkedList();
do
{
System.out.println("1:push 2:pop 3:stacktop 4:display"
+ " 5:exit" + "\n" + "enter ur choice:");
if(ch==5)
{
break;
}
else
{
{
case 1:
x=s.nextInt();
if(top==max) //reached maxsize
System.out.println("stack is full");
else
l.push(x);
top++; //increment top
break;
case 2:
if(top==-1) //reached minsize
System.out.println("stack is empty");
else
l.pop();
break;
case 3:
System.out.println("stack top element:"+(l.stacktop()));
break;
case 4:
System.out.println("stack elements are:");//displaying all elements
l.display();
break;
break;
}
}

}
class Node //create node for every element
{
int data; //for data
Node link; //for next element
}
Node top; //top link
StackLinkedList()
{
this.top=null;
}
public void push(int x)
{
Node temp=new Node();
temp.data=x;
temp.link=top;
top=temp;
}
public void pop()
{
top=(top).link;
}
public int stacktop()
{
return top.data;
}
{
Node temp=top;
while(temp!=null)
{
System.out.println(temp.data);
temp=temp.link;
}
}
} //class
Output:
1:push 2:pop 3:stacktop 4:display 5:exit

enter ur choice:
1
enter element:
32
enter ur choice:
1
enter element:
56
enter ur choice:
1
enter element:
74
enter ur choice:
4
stack elements are:
74
56
32
enter ur choice:
3
stack top element:74
enter ur choice:
2
enter ur choice:
4
stack elements are:
56
32
enter ur choice:
3
stack top element:56
enter ur choice:
5
exiting...
Program:
import java.io.*;
class Node
{
public int data;
public Node next;
public Node(int x)
{
data=x;
}
public void displayNode()
{
System.out.print(data+" ");
}
}
class LinkList
{
private Node first;
private Node last;
public LinkList()
{
first=null;
last=null;
}
public void insertLast(int x)
{
Node newNode=new Node(x);
newNode.next=null;
if(isEmpty())
first=newNode;
else
last.next=newNode;
last=newNode;
}
public int deleteFirst()
{
int t=first.data;
if(first.next==null)
last=null;
first=first.next;
return t;
}
public int peekFirst()
{
return(first.data);
}
{
return(first==null);
}
public void displayList()
{
Node current=first;
while(current!=null)
{
current.displayNode();
current=current.next;
}
}
}
class Queue
{
private LinkList l;
public Queue()
{
l=new LinkList();
}
public void insert(int x)
{
l.insertLast(x);
System.out.println("Inserted");
}
public int delete()
{
return l.deleteFirst();
}
public boolean isQueueEmpty()
{
return l.isEmpty();
}
{
l.displayList();
}
public int peek()
{
return l.peekFirst();
}
}
class QueueList
{
{
Queue q=new Queue();
int ch,d;
while((boolean)true)
{
System.out.println("MENU");
System.out.println("--------");
System.out.println("1.Insert");
System.out.println("2.Delete");
System.out.println("3.Peek");
System.out.println("4.Display");
System.out.println("5.Exit");
System.out.println("Enter Your Choice: ");
ch=Integer.parseInt(br.readLine());
if(ch==5)
break;
else
{
switch(ch)
{
case 1:
System.out.println("Enter Number of Elements");
int n1=Integer.parseInt(br.readLine());
System.out.println("\nEnter elements: ");
for(int i=0; i<n1; i++)
{
d=Integer.parseInt(br.readLine());
q.insert(d);
}
break;
case 2:
if(q.isQueueEmpty())
System.out.println("Queue is Empty ");
else
{
d=q.delete();
System.out.println("Deleted data:- "+d);
}
break;
case 3:
System.out.print("Queue is Empty ");
else
{
d=q.peek();
System.out.println("First item:- "+d);
}
break;
case 4:
System.out.println("Queue is Empty ");
else
{
System.out.println("Datas in Queue ");
q.display();
}
break;
default:
System.out.println("Invalid choice ");
}
}
System.out.println(" ");
}
}
}
Output:
MENU
--------
1.Insert
2.Delete
3.Peek
4.Display
5.Exit
Enter Your Choice:
1
Enter Number of Elements
3
Enter elements:
14
Inserted
53
Inserted
98
Inserted
MENU
--------
1.Insert
2.Delete
3.Peek
4.Display
5.Exit
Enter Your Choice:
2
Deleted data:- 14
MENU
--------
1.Insert
2.Delete
3.Peek
4.Display
5.Exit
Enter Your Choice:
3
First item:- 53
MENU
--------
1.Insert
2.Delete
3.Peek
4.Display
5.Exit
Enter Your Choice:
4
Datas in Queue
53 98
MENU
--------
1.Insert
2.Delete
3.Peek
4.Display
5.Exit
Enter Your Choice:
5
Program:
import java.io.*;
class Dequeue
{
int arr[];
int lim;
int front;
int rear;
public Dequeue(int l)
{
lim=l;
front=rear=0;
arr=new int[(l+1)];
}
void addfront(int val)
{
if(front==0 && rear ==0)
{
front=1;
rear=1;
arr[1]=val;
}
else if(rear==lim)
{
System.out.println("Overflow");
}
else
{
arr[++rear]=val;
}
}
void addrear(int val)
{
if(front==0 && rear ==0)
{
front=1;
rear=1;
arr[1]=val;
}
else if(front==-1)
{
System.out.println("Overflow");
}
else
{
arr[--front]=val;
}
}
void popfront()
{
if(front==rear)
{
System.out.println("The Front element removed is : "+arr[front]);
front=0;
rear=0;
}
else if(front==0 && rear==0)
{
System.out.println("Underflow");
}
else
{
System.out.println("The Front element removed is : "+arr[rear]);
rear--;
}
void poprear()
{
if(front==rear)
{
System.out.println("The Rear element removed is : "+arr[front]);
front=0;
rear=0;
}
else if(front==0 && rear==0)
{
System.out.println("Underflow");
}
else
{
System.out.println("The Rear element removed is : "+arr[front]);
front++;
}
}
void display()
{
System.out.print("The elements in Deque are: ");
for(int i=front;i<=rear;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println(" ");
}
{
int flag=0;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter size of array");
Dequeue obj=new Dequeue(Integer.parseInt(br.readLine()));
while(flag==0)
{
System.out.println("1 for addrear");
System.out.println("2 for addfront");
System.out.println("3 for poprear");
System.out.println("4 for popfront");
System.out.println("5 for exit");
int ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1:
System.out.println("Enter element");
obj.addrear(Integer.parseInt(br.readLine()));
obj.display();
break;
case 2:System.out.println("Enter element");
obj.addfront(Integer.parseInt(br.readLine()));
obj.display();
break;
case 3:obj.poprear();
obj.display();
break;
case 4:obj.popfront();
obj.display();
break;
case 5:flag=1;
break;
}
}
}
}
Output:
Enter size of array

4
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
1
Enter element
15
The elements in Deque are: 15
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
2
Enter element
17
The elements in Deque are: 15 17
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
1
Enter element
87
The elements in Deque are: 87 15 17
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
3
The Rear element removed is : 87
The elements in Deque are: 15 17
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
4
The Front element removed is : 17
The elements in Deque are: 15
1 for addrear
2 for addfront
3 for poprear
4 for popfront
5 for exit
5
Program:
import java.io.*;
class Node
{
public int data;
public Node next;
public Node previous;
public Node(int x)
{
data=x;
}
public void displayNode()
{
System.out.print(data+" ");
}
}
class DoublyLinkList
{
private Node first;
private Node last;
public DoublyLinkList()
{
first=null;
last=null;
}
public void insertFirst(int x)
{
newNode.next=null;
if(isEmpty())
last=newNode;
else
first.previous=newNode;
newNode.next=first;
first=newNode;
}
public void insertLast(int x)
{
newNode.next=null;
if(isEmpty())
first=newNode;
else
{
last.next=newNode;
newNode.previous=last;
}
last=newNode;
}
public int deleteFirst()
{
int t=first.data;
last=null;
else
first.next.previous=null;
first=first.next;
return t;
}
public int deleteLast()
{
int t=last.data;
first=null;
else
last.previous.next=null;
last=last.previous;
return t;
}
{
return(first==null);
}
public void displayForward()
{
Node current=first;
{
current=current.next;
}
}
public void displayBackward()
{
Node current=last;
{
current=current.previous;
}
}
}
class Deque
{
private DoublyLinkList l;
public Deque()
{
l=new DoublyLinkList();
}
public void insertLeft(int x)
{
l.insertFirst(x);
System.out.print("Inserted to Front ");
}
public void insertRight(int x)
{
l.insertLast(x);
System.out.print("Inserted to Rear ");
}
public int deleteLeft()
{
return l.deleteFirst();
}
public int deleteRight()
{
return l.deleteLast();
}
public boolean isQueueEmpty()
{
return l.isEmpty();
}
public void displayFromFront()
{
l.displayForward();
}
public void displayFromRear()
{
l.displayBackward();
}
}
class DequeApp
{
{
String ch="y";
DataInputStream inp=new DataInputStream(System.in);
int n,d;
Deque q=new Deque();
while(ch.equals("y"))
{
System.out.println("MENU");
System.out.println("--------");
System.out.println("1.Insert at Front");
System.out.println("2.Insert at Rear");
System.out.println("3.Delete at Front");
System.out.println("4.Delete at Rear");
System.out.println("5.Display From Front");
System.out.println("6.Display From Rear");
System.out.println("Enter your choice ");
n=Integer.parseInt(inp.readLine());
switch(n)
{
case 1: System.out.println("Enter the data ");
d=Integer.parseInt(inp.readLine());
q.insertLeft(d);
break;
case 2: System.out.println("Enter the data ");
d=Integer.parseInt(inp.readLine());
q.insertRight(d);
break;
case 3: if(q.isQueueEmpty())
System.out.print("Deque is Empty ");
else
{
d=q.deleteLeft();
System.out.print("Deleted data:- "+d);
}
break;
else
{
d=q.deleteRight();
System.out.print("Deleted data:- "+d);
}
break;
else
{
System.out.print("Elements in Deque From Front:- ");
q.displayFromFront();
}
break;
else
{
System.out.print("Elements in Deque From Rear:- ");
q.displayFromRear();
}
break;
default: System.out.print("Invalid choice ");
}
System.out.println("");
System.out.print("Enter y to continue ");
ch=inp.readLine();
}
}
}
Output:
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
5.Display From Front
6.Display From Rear
Enter your choice
1
Enter the data
23
Inserted to Front
Enter y to continue y
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
6.Display From Rear
Enter your choice
2
Enter the data
22
Inserted to Rear
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
6.Display From Rear
Enter your choice
1
Enter the data
24
Inserted to Front
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
6.Display From Rear
Enter your choice
5
Elements in Deque From Front:- 24 23 22
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
6.Display From Rear
Enter your choice
4
Deleted data:- 22
MENU
--------
1.Insert at Front
2.Insert at Rear
3.Delete at Front
4.Delete at Rear
6.Display From Rear
Enter your choice
6
Elements in Deque From Rear:- 23 24
Enter y to continue n
BUILD SUCCESSFUL (total time: 1 minute 1 second)
Program:
import java.util.*; //to read user input

public class DequeSingleList
{
int max=5; //size of deque
{
DequeSingleList d=new DequeSingleList(); //creating object
int a[]=new int[10]; //array initialization
int r=0,f,ch,x;//variables declaration
f=0; //intially queue empty
int max=5;
do
{
System.out.println("1:enqueuerear 2:enqueuefront 3:dequeuerear
4:dequefront "
+ "5:queuerear 6:queuefront 7:display 8:exit" + "\n" + "enter ur
choice:");
if(ch==8)
{
break;
}
else
{
{
case 1:
x=s.nextInt();
else
d.enqueuerear(x); //increment rear
break;
case 2:
x=s.nextInt();
else
d.enqueuefront(x); //increment rear
break;
case 3:
if(r==-1) //reached minsize
else
d.dequeuerear(); //decrement rear
break;
case 4:
if(r==-1) //reached minsize
else
d.dequeuefront(); //decrement rear
break;
case 5:
System.out.println("queue rear element:"+d.dequerear());
break;
case 6:
System.out.println("queue front element:"+d.dequefront());
break;
case 7:
d.display(); //displaying all elements
break;
break;
}
}

}
class Qnode //creating node for every element
{
int key; //creating data
Qnode next; //creating link next
Qnode prev; //creating link prev
public Qnode(int key)
{
this.key=key;
this.next=next;
this.prev=prev;
}
}
Qnode rear,front;
public void enqueuerear(int key)
{
Qnode temp=new Qnode(key);
if(this.rear==null)
{
this.front=this.rear=temp;
return;
}
temp.prev=this.rear;
this.rear.next=temp; //inserting element
this.rear=temp;
max++;
}
public void enqueuefront(int key)
{
Qnode temp=new Qnode(key);
if(this.front==null)
{
this.front=this.rear=null;
}
temp.next=front;
this.front.prev=temp;
this.front=temp;
max++;
}
Qnode dequeuerear()
{
if(this.rear==null)
return null;
Qnode temp=this.rear;
this.rear=this.rear.prev;
if(this.rear==null)
this.front=null; //deleting
max--;
return temp;
}
Qnode dequeuefront()
{
return null;
Qnode temp=this.front;
this.front=this.front.next;
this.rear=null;
max--;
return temp;
}
public int dequerear()
{
return rear.key;
}
public int dequefront()
{
return front.key;
}
{
Qnode temp=front;
while(temp!=null)
{
System.out.println(temp.key);
temp=temp.next;
}
}
} //class9
Output:
1:enqueuerear 2:enqueuefront 3:dequeuerear 4:dequefront 5:queuerear

6:queuefront 7:display 8:exit
enter ur choice:
1
enter element:
14
enter ur choice:
2
enter element:
76
enter ur choice:
1
enter element:
73
enter ur choice:
7
queue elements are:
76
14
73
enter ur choice:
5
enter ur choice:
6
enter ur choice:
4
enter ur choice:
7
queue elements are:
14
73
enter ur choice:
8
exiting...
Program:
import java.util.Scanner; // to read user inputs

public class PriorityQueue
{
{
int a[]=new int[10];
int priority[]=new int[10]; //array initialization
int max=10,f,r,ch,x,p,i,j; //variables declaration
f=1;
i=0;
r=0;//intially queue empty
do
{
System.out.println("1:enqueue 2:dequeue 3:queuerear 4:queuefront"
+ " 5:display 6:exit" + "\n" + "enter ur choice:");
if(ch==6)
{
break;
}
else
{
{
case 1:
x=s.nextInt();
System.out.println("enter priority of that element");
p=s.nextInt(); //reading priority
else
a[++r]=x; //increment rear
priority[++i]=p; //incrementing priorityand assign
break;
case 2:
if(r==f) //reached minsize
else
{
for(i=0,j=0;i<r-1&&j<r-1;i++,j++)
{
if(i==j)
{
for(j=0;j<r-1;j++)
{
if(priority[j]<priority[j+1]) //max priority value
a[j]=a[j+1];
}
}
}
f=f+1; //increment front

}
break;
case 3:
System.out.println("queue rear element:"+a[r]);
break;
case 4:
System.out.println("queue front element:"+a[f]);
break;
case 5:
for(i=f;i<=r;i++)
System.out.println(+a[i]+" priority:"+priority[i]);//displaying
all elements
break;
break;
}//switch
} //else

}//main
} //class
Output:

enter ur choice:
1
enter element:
14
enter priority of that element
3
enter ur choice:
1
enter element:
65
1
enter ur choice:
1
enter element:
34
2
enter ur choice:
5
queue elements are:
14 priority:3
65 priority:1
34 priority:2
enter ur choice:
3
enter ur choice:
4
enter ur choice:
5
queue elements are:
14 priority:3
65 priority:1
34 priority:2
enter ur choice:
2
enter ur choice:
5
queue elements are:
65 priority:1
34 priority:2
enter ur choice:
6
exiting...
Program:
import java.util.*;
class BSTNode
{
int data;
BSTNode left;
BSTNode right;
BSTNode( int d ) // constructor
{ data = d; }
}
class BinarySearchTree
{
public BSTNode insertTree(BSTNode p, int key) // create BST
{
if( p == null )
p = new BSTNode(key);
else if( key < p.data)
p.left = insertTree( p.left, key);
else p.right = insertTree( p.right, key);
return p; // return root
}
public BSTNode search(BSTNode root, int key)

{
BSTNode p = root; // initialize p with root
while( p != null )
{ if( key == p.data ) return p;
else if( key < p.data ) p = p.left;
else p = p.right;
}
return null;
}
public int leafNodes(BSTNode p)

{
int count = 0;
if( p != null)
{ if((p.left == null) && (p.right == null))
count = 1;
else
count = count + leafNodes(p.left)
+ leafNodes(p.right);
}
return count;
}
} // end of BinarySearchTree class

////////////////////// BinarySearchTreeDemo.java ////////////////////
class BinarySearchTreeDemo
{ public static void main(String args[])
{
int arr[],n;
Scanner s=new Scanner(System.in);
System.out.println("Enter array length: ");
n=s.nextInt();
arr=new int[n];
System.out.println("enter "+n+" elements: ");
for(int i=0;i<n;i++)
{
arr[i]=s.nextInt();
}
BinarySearchTree bst = new BinarySearchTree();
BSTNode root = null;
// build tree by repeated insertions
for( int i = 0; i < arr.length; i++ )
root = bst.insertTree( root, arr[i]);
BSTNode root2 = root; // copy BST

// int key = 66;
int key ;
System.out.println("Enter the key to be searched: ");
key=s.nextInt();
BSTNode item = bst.search(root2, key);
if( item != null )
System.out.print("\n item found: " + item.data);
else System.out.print("\n Node " + key + " not found");
System.out.print("\n Number of leaf nodes: " + bst.leafNodes(root));
}
}
Output:
Enter array length:

12
enter 12 elements:
45 25 12 10 20 30 65 55 50 60 75 80
Enter the key to be searched:
66
Node 66 not found

Number of leaf nodes: 6
Program:
class Entry
{ public String key; // word
public String element; // word meaning
public Entry(String k, String e) // constructor

{
key = k;
element = e;
}
}
class HashTable
{
Entry[] hashArray; // array holds hash table
int size; // table size
int count; // current number of items in the table
public HashTable(int s) // constructor
{
size = s;
count = 0;
hashArray = new Entry[size];
}
int hashFunc( String theKey ) // convert the string into a numeric key
{
int hashVal=0;
// convert the string into a numeric key
for(int i = 0; i < theKey.length(); i++)
hashVal = 37*hashVal + (int)theKey.charAt(i);
hashVal = hashVal % size;

if(hashVal < 0 )
hashVal = hashVal + size;
return hashVal;
}
public void insert(String theKey, String str) // insert a record

{
if( !isFull() )
{
int hashVal = hashFunc(theKey); // hash the key
// until empty cell or null,

while(hashArray[hashVal] != null )
{
++hashVal; // go to next cell
hashVal %= size; // wraparound if necessary
}
hashArray[hashVal] = new Entry(theKey, str);
count++; // update count
}
else
System.out.println("Table is full");
}
public Entry delete(String theKey) // delete a record with the key

{
if( !isEmpty() )
{
while(hashArray[hashVal] != null) // until empty cell,

{
if(hashArray[hashVal].key == theKey) // found the key?
{ Entry tmp = hashArray[hashVal]; // save item
hashArray[hashVal] = null; // delete item
count--;
return tmp; // return item
}
}
return null; // cannot find item
}
else
System.out.println("Table is empty");
return null;
}
public Entry search(String theKey) // find item with key
{
while(hashArray[hashVal] != null) // until empty cell,

{
if(hashArray[hashVal].key == theKey) // found the key?
return hashArray[hashVal]; // yes, return item
}
return null; // cannot find item
}
public void displayTable()
{
System.out.println("<< Dictionary Table >>\n");
for(int i=0; i<size; i++)

{
if(hashArray[i] != null )
System.out.println( hashArray[i].key + "\t" +
hashArray[i].element );
}
}
public boolean isEmpty() // returns true, if table is empty
{
return count == 0;
}
public boolean isFull() // returns true, if table is full
{
return count == size;
}
public int currentSize()
{
return count;
}
}
///////////////////////// Dictionary.java ////////////////////////////

class Dictionary
{
{
HashTable ht = new HashTable(19); // create hash table of size, 19
// Insert the following items into hash table

ht.insert("man", "gentleman");
ht.insert("watch", "observe");
ht.insert("hope", "expect");
ht.insert("arrange", "put together");
ht.insert("run", "sprint");
ht.insert("wish", "desire");
ht.insert("help", "lend a hand");
ht.insert("insert", "put in");
ht.insert("count", "add up");
ht.insert("format", "arrangement");
ht.displayTable(); // Display the table items
// Search an item
String word = "wish";

Entry item = ht.search(word);
if( item != null )
System.out.println("found: " + item.key + "\t" + item.element);
else
System.out.println(word + " not found");
// Delete an item
word = "hope";
item = ht.delete(word);
if( item != null )
System.out.println("deleted: " + item.key + "\t" + item.element);
else
System.out.println(word + " not found - no deletion");
// Current number of items in the table
System.out.println("size: " + ht.currentSize());
}
}
Output:
<< Dictionary Table >>
insert put in
help lend a hand
man gentleman
watch observe
format arrangement
run sprint
wish desire
arrange put together
hope expect
count add up
found: wish desire
deleted: hope expect
size: 9
Program:
public class Preorder {

static class Node {
int value;
Node left, right;
Node(int value){
this.value = value;
left = null;
right = null;
}
}
public void insert(Node node, int value) {

if (value < node.value)
{
if (node.left != null)
{
insert(node.left, value);
}
else
{
System.out.println(" Inserted " + value + " to left of " +
node.value);
node.left = new Node(value);
}
}
else if (value > node.value)
{
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value +
" to right of "
+ node.value);
node.right = new Node(value);
}
}
}
public void traversePreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
{
Preorder tree = new Preorder();
Scanner sc = new Scanner(System.in);
System.out.println("enter the number of nodes");
int i = sc.nextInt();
System.out.println("total nodes:"+i);
int[] ab=new int[i];
for(int x=0;x<i;x++)
{
ab[x]=sc.nextInt();
}
Node root = new Node(5);

System.out.println("Building tree with root value " + root.value);
for(int y=0;y<ab.length;y++){
tree.insert(root, ab[y]);
}
System.out.println("pre order traversal is :");
tree.traversePreOrder(root);
}
}
Output:
enter the number of nodes

5
total nodes:5
14 36 76 2 6
Building tree with root value 5
Inserted 14 to right of 5
Inserted 2 to left of 5
pre order traversal is :
5 2 14 6 36 76
Program:
public class Inorder {

static class Node {
int value;
Node left, right;
Node(int value){
this.value = value;
left = null;
right = null;
}
}

{
{
}
else
{
node.value);
}
}
{
} else {
" to right of "
+ node.value);
}
}
}
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
traverseInOrder(node.right);
}
}
{
Inorder tree = new Inorder();
{
ab[x]=sc.nextInt();
}

}
System.out.println("inorder traversal is:");

tree.traverseInOrder(root);
}
}
Output:

5
total nodes:5
14 36 76 2 6
inorder traversal is:
2 5 6 14 36 76
Program:
public class Postorder {

static class Node {
int value;
Node left, right;
Node(int value){
this.value = value;
left = null;
right = null;
}
}

{
{
}
else
{
node.value);
}
}
{
} else {
" to right of "
+ node.value);
}
}
}
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
}
}
{
Postorder tree = new Postorder();
{
ab[x]=sc.nextInt();
}

}
System.out.println("postorder traversal is :");
tree.traversePostOrder(root);
}
}
Output:

5
total nodes:5
14 36 76 2 6
postorder traversal is :
2 6 76 36 14 5
Program:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class BFS {

// 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
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){
}
}
}
int source;
System.out.println("Enter the source vertex");
try{
source = Integer.parseInt(br.readLine());
return;
}
breadthFirstSearch(matrix,source);
}
}
Output:
Enter the number of vertices in the graph

3
Enter the adjacency matrix
0
0
0
1
0
1
1
1
1
Enter the source vertex
2
The breadth first order is
2
1
3
Program:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class DFS {

// 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
int vertices;
System.out.println("Enter the number of vertices in the graph");
try{
vertices = Integer.parseInt(br.readLine());
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){
}
}
}
int source;
System.out.println("Enter the source vertex");
try{
source = Integer.parseInt(br.readLine());
return;
}
depthFirstSearch(matrix,source);
}
}
Output:
Enter the number of vertices in the graph

5
Enter the adjacency matrix
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
Enter the source vertex
1
The depth first order is
1
2
3
4
Program:
class BubbleSort
{
void bubbleSort(int arr[])
{
int n = arr.length;
System.out.println("Enter " + n + " integers");
Scanner in = new Scanner(System.in);

for (int c = 0; c < n; c++)
arr[c] = in.nextInt();
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
/* Prints the array */

void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method to test above

{
BubbleSort ob = new BubbleSort();
int arr[];
System.out.println("Enter number of elements");
int n = in.nextInt();
arr = new int[n];
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
Output:
Enter number of elements

6
Enter 6 integers
87 45 63 25 15 41
Sorted array
15 25 41 45 63 87
Program:
class InsertionSort {
/*Function to sort array using insertion sort*/
void sort(int arr[])
{
int n = arr.length;

for (int c = 0; c < n; c++)
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
/* A utility function to print array of size n*/

static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
}
// Driver method
{
int arr[];
arr = new int[n];
InsertionSort ob = new InsertionSort();

ob.sort(arr);
System.out.println("Sorted array");
printArray(arr);
}
}
Output:

7
Enter 7 integers
16 2 8 1 9 6 33
Sorted array
1 2 6 8 9 16 33
Program:
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)

int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()

arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)

{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before

// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */

{
int n = arr.length;

}
// Driver program
{
int arr[];
arr = new int[n];
for (int c = 0; c < n; c++)
QuickSort ob = new QuickSort();

ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
Output:

9
Enter 9 integers
10 35 8 3 94 34 82 9 01
sorted array
1 3 8 9 10 34 35 82 94
Program:
class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */

int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/

for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays

int i = 0, j = 0;
// Initial index of merged subarry array

int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */

while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using

// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves

sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves

merge(arr, l, m, r);
}
}

{
int n = arr.length;
}
// Driver method
{
int arr[];
arr = new int[n];
for (int c = 0; c < n; c++)

MergeSort ob = new MergeSort();

ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
}
Output:

8
Enter 8 integers
15 3 26 75 14 28 89 34
Sorted array
3 14 15 26 28 34 75 89
Program:
public class HeapSort

{
public void sort(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
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);
}
}

{
int n = arr.length;
}
// Driver program
{
int arr[];
arr = new int[n];
for (int c = 0; c < n; c++)

HeapSort ob = new HeapSort();

ob.sort(arr);
System.out.println("Sorted array is");

printArray(arr);
}
}
Output:

9
Enter 9 integers
15 24 37 9 7 3 90 26 2
Sorted array is
2 3 7 9 15 24 26 37 90
Program:
import java.io.*;
import java.util.*;
class Radix {
// A utility function to get maximum value in arr[]

static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to

// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]

for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains

// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array

for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now

// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using

// Radix Sort
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead

// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array

static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
}
/*Driver function to check for above function*/

public static void main (String[] args)
{
int arr[];
arr = new int[n];
for (int c = 0; c < n; c++)

radixsort(arr, n);
print(arr, n);
}
}
Output:

7
Enter 7 integers
14 2 5 8 21 67 1
1 2 5 8 14 21 67
Program:
class BinarytreeSort
{
// Class containing left and

// right child of current
// node and key value
class Node
{
int key;
Node left, right;
public Node(int item)

{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarytreeSort ()
{
root = null;
}
// This method mainly

// calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to
insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty,

return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur
down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the root */

return root;
}
// A function to do
// inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
void treeins(int arr[])
{
for(int i = 0; i < arr.length; i++)
{
insert(arr[i]);
}
// Driver Code
{
BinarytreeSort tree = new BinarytreeSort ();
int arr[];
arr = new int[n];
for (int c = 0; c < n; c++)

tree.treeins(arr);
tree.inorderRec(tree.root);
}
}
Output:

8
Enter 8 integers
15 34 11 86 92 55 9 2
2 9 11 15 34 55 86 92
Program:
import java.io.*;
class Edge
{
int v1,v2,wt; // wt is the weight of the edge
}
class kruskalsalgo
{
{
int i,j,mincost=0;
BufferedReader br=new BufferedReader( new InputStreamReader(System.in));
System.out.println(" Enter no.of vertices:");
int v=Integer.parseInt(br.readLine());
System.out.println(" Enter no.of edges:");
int e=Integer.parseInt(br.readLine());
Edge ed[]=new Edge[e+1];
for(i=1;i<=e;i++)
{
ed[i]=new Edge();
System.out.println(" Enter the vertices and the weight of edge "+(i)+ ":");
ed[i].v1=Integer.parseInt(br.readLine());
ed[i].v2=Integer.parseInt(br.readLine());
ed[i].wt=Integer.parseInt(br.readLine());
}
for(i=1;i<=e;i++) // sorting the edges in ascending order
for(j=1;j<=e-1;j++)
{
if(ed[j].wt>ed[j+1].wt)
{
Edge t=new Edge();
t=ed[j];
ed[j]=ed[j+1];
ed[j+1]=t;
}
}
int visited[]=new int[v+1]; // array to check whether the vertex is visited or not
for(i=1;i<=v;i++)
visited[i]=0;
System.out.println("MINIMUM SPANNING TREE :");
for(i=1;i<=e;i++)
{
if(i>v)
break;
else if( visited[ed[i].v1]==0 || visited[ed[i].v2]==0)
{
System.out.println(ed[i].v1+ "-"+ ed[i].v2);
visited[ed[i].v1]=visited[ed[i].v2]=1;
mincost+=ed[i].wt;
}
}
System.out.println("MINIMUM COST = " +mincost);
}
}
Output:
Enter no.of vertices:

5
Enter no.of edges:
8
Enter the vertices and the weight of edge 1:
1
3
10
3
5
64
1
2
13
3
2
20
2
5
5
1
4
100
4
3
80
4
5
40
MINIMUM SPANNING TREE :
2-5
1-3
4-5
MINIMUM COST = 55

Programs Sssssssss

Uploaded by

Document Informationclick to expand document informationprograms in java

Document Informationclick to expand document information

Copyright:

Available Formats

Programs Sssssssss

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Programs Sssssssss

Uploaded by

Copyright:

Available Formats

Program:

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

Do you want to continue (Type y or n)

Singly Linked List Test

Singly Linked List Operations

Singly Linked List = 23

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 23->35

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 23->67->35

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 67->35

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 67->35

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 67->35

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 67

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = 67

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = empty

Do you want to continue (Type y or n)

Singly Linked List Operations

Singly Linked List = empty

Do you want to continue (Type y or n)

//function to check if the cell is attacked or not

private static boolean nQueen(int n)

public static void main(String[] args)

import java.util.Scanner; // to user input

}while(true); //repeats until false

1:enqueue 2:dequeue 3:queuerear 4:queuefront 5:display 6:exit

public class Palindrome

if (isPalindrome( inputString )){

public static boolean isPalindrome(String input)

for (i = 0; i < input.length( ); i++)

}while(true); //repeats until false

1:push 2:pop 3:stacktop 4:display 5:exit

Enter size of array

import java.util.*; //to read user input

}while(true); //repeats until false

1:enqueuerear 2:enqueuefront 3:dequeuerear 4:dequefront 5:queuerear

import java.util.Scanner; // to read user inputs

f=f+1; //increment front

}while(true); //repeats until false

1:enqueue 2:dequeue 3:queuerear 4:queuefront 5:display 6:exit

public BSTNode search(BSTNode root, int key)

public int leafNodes(BSTNode p)

} // end of BinarySearchTree class

BSTNode root2 = root; // copy BST

/Copy data to temp arrays/