DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiments
Student Name: Anurag Singh UID=22BET10338
Branch: CSE ‘IT’ Section/Group: 22BET_IOT 703/B
Semester: 5th Date of Performance: 27/08/2024
Subject Name: DAA Subject Code: 22ITH-311
1. Code for enqueue, dequeue, Isfull and Isempty operation in queues using
templates.
import java.util.Scanner;
public class Queue<T> {
private int front, rear, size, capacity;
private T[] queue;
// Constructor to initialize queue
public Queue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
queue = (T[]) new Object[capacity]; // Array of generic type
}
// Method to check if the queue is full
public boolean isFull() {
return (this.size == this.capacity);
}
// Method to check if the queue is empty
public boolean isEmpty() {
return (this.size == 0);
}
// Method to add an item to the queue (enqueue)
public void enqueue(T item) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue " + item);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
return;
}
this.rear = (this.rear + 1) % this.capacity;
this.queue[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}
// Method to remove an item from the queue (dequeue)
public T dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue");
return null;
}
T item = this.queue[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
System.out.println(item + " dequeued from queue");
return item;
}
// Method to get the front item of the queue
public T front() {
if (isEmpty()) {
return null;
}
return this.queue[this.front];
}
// Method to get the rear item of the queue
public T rear() {
if (isEmpty()) {
return null;
}
return this.queue[this.rear];
}
// Main method for user-defined interaction with the queue
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the capacity of the queue: ");
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
int capacity = scanner.nextInt();
Queue<Integer> queue = new Queue<>(capacity);
while (true) {
System.out.println("\nChoose an operation:");
System.out.println("1. Enqueue");
System.out.println("2. Dequeue");
System.out.println("3. Check if the queue is full");
System.out.println("4. Check if the queue is empty");
System.out.println("5. View the front item");
System.out.println("6. View the rear item");
System.out.println("7. Exit");
System.out.print("Enter your choice: ");
int choice = scanner.nextInt();
switch (choice) {
case 1:
System.out.print("Enter the item to enqueue: ");
int item = scanner.nextInt();
queue.enqueue(item);
break;
case 2:
queue.dequeue();
break;
case 3:
if (queue.isFull()) {
System.out.println("The queue is full.");
} else {
System.out.println("The queue is not full.");
}
break;
case 4:
if (queue.isEmpty()) {
System.out.println("The queue is empty.");
} else {
System.out.println("The queue is not empty.");
}
break;
case 5:
Integer frontItem = queue.front();
if (frontItem != null) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
System.out.println("Front item: " + frontItem);
} else {
System.out.println("The queue is empty.");
}
break;
case 6:
Integer rearItem = queue.rear();
if (rearItem != null) {
System.out.println("Rear item: " + rearItem);
} else {
System.out.println("The queue is empty.");
}
break;
case 7:
System.out.println("Exiting...");
scanner.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
2. Code and analyze to sort an array of integers using Merge sort
public class MergeSort {
// Method to merge two subarrays
public static void merge(int[] array, int left, int middle, int right) {
// Sizes of the subarrays
int n1 = middle - left + 1;
int n2 = right - middle;
// Temporary arrays
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; ++i)
leftArray[i] = array[left + i];
for (int j = 0; j < n2; ++j)
rightArray[j] = array[middle + 1 + j];
// Initial indices of subarrays and merged array
int i = 0, j = 0;
int k = left;
// Merge the temporary arrays back into the original array
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
// Copy remaining elements of leftArray, if any
while (i < n1) {
array[k] = leftArray[i];
i++;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
k++;
}
// Copy remaining elements of rightArray, if any
while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}
// Method to sort an array using Merge Sort
public static void sort(int[] array, int left, int right) {
if (left < right) {
// Find the middle point
int middle = (left + right) / 2;
// Recursively sort the two halves
sort(array, left, middle);
sort(array, middle + 1, right);
// Merge the sorted halves
merge(array, left, middle, right);
}
}
// Method to print the array
public static void printArray(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
// Main method to test the Merge Sort implementation
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
System.out.println("Original array:");
printArray(array);
sort(array, 0, array.length - 1);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
System.out.println("Sorted array:");
printArray(array);
}
}
Output:
3. Code to find the height of a Binary tree with Analysis
class Node {
int data;
Node left, right;
// Constructor to create a new node
public Node(int item) {
data = item;
left = right = null;
}
}
// Class to represent the binary tree
class BinaryTree {
Node root;
// Method to calculate the height of the binary tree
public int findHeight(Node node) {
if (node == null) {
return 0; // Base case: If the node is null, return 0 (height of an empty tree)
} else {
// Recursively calculate the height of left and right subtrees
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
int leftHeight = findHeight(node.left);
int rightHeight = findHeight(node.right);
// Height of the tree is the maximum of the heights of the left and right subtrees
plus 1
return Math.max(leftHeight, rightHeight) + 1;
}
}
// Main method to test the height calculation
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Creating a binary tree
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
// Calculating the height of the tree
int height = tree.findHeight(tree.root);
System.out.println("The height of the binary tree is: " + height);
}
}
Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
4. Code to find the ignored successor in an Binary Search Trees with complexity
Analysis.
public class Binary
{
/* A binary tree node has data,
the pointer to left child
and a pointer to right child */
static class node
{
int data;
node left;
node right;
node parent;
};
static node inOrderSuccessor(
node root,
node n)
{
// step 1 of the above algorithm
if (n.right != null)
return minValue(n.right);
node succ = null;
// Start from root and search for
// successor down the tree
while (root != null)
{
if (n.data < root.data)
{
succ = root;
root = root.left;
}
else if (n.data > root.data)
root = root.right;
else
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
break;
}
return succ;
}
/* Given a non-empty binary search tree,
return the minimum data
value found in that tree. Note that
the entire tree does not need
to be searched. */
static node minValue(node node)
{
node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null)
{
current = current.left;
}
return current;
}
/* Helper function that allocates a new
node with the given data and
null left and right pointers. */
static node newNode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
node.parent = null;
return (node);
}
static node insert(node node,
int data)
{
if (node == null)
return (newNode(data));
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
else
{
node temp;
if (data <= node.data)
{
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
}
else
{
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
return node;
}
}
public static void main(String[] args)
{
node root = null, temp, succ, min;
// creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root.left.right.right;
// Function Call
succ = inOrderSuccessor(root, temp);
if (succ != null)
System.out.printf(
"\n Inorder Successor of %d is %d ",
temp.data, succ.data);
else
System.out.printf("\n Inorder Successor doesn't exit");
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
Output:
