Code is provided for A,B and C. I need the solution for D and E

Assignment:

Write separate programs for the following exercises in Java. Each file should have your name at the top in comment, with short description of the implemented class and main method should have comments about the problem it is solving. Make sure your files have appropriate names. Programs should write output to the Console. . a) LinkedListADT: Implement linked list ADT using the bellow pseudo code.

Linked List ADT Given Node class, below is an example of implementation for some linked list operations... class Node data-type data Node next Node(data-type val) data = val next = null/None // implement get and set methods for data and next class LinkedList Node head Node tail LinkedList() Assign null/None to head and tail addHead(data-type val) Node n = Node(val) if (head == null/None) // no elements head = n tail = n else // have elements set n.next to head head =n addTail(data-type val) Node n = Node(val) if (head == null/None) // no elements head = n tail = n else // have elements set tail.next to n tail =n data-type deleteTail() Node n = tail if (head == null/None) // no elements throw exception if (head == tail) // one element head = null/None You should have all the operations in the pseudo code. Write test program with main method creating an instance of the Linked List and calling all the operations to demonstrate they work correctly. You must implement a class called LinkedListADT and TestLinkedList class in a separate file.

b) MiddleList: Write an algorithm, implemented as a method that takes a LinkedListADT object (using the above class) and integer k as parameters and prints middle element + K elements data in the LinkedList. Evaluate and report the time and space complexity of your algorithm. Main method should create and populate the LinkedListADT instance with some elements, call the middleList method with some K to print values. You must have a class called MiddleList with the algorithm (method middleList) and main method. For example 1 (odd number of elements): Linked list elements: 1 2 3 4 5 6 7 8 9 K=2 Output: 5 6 7 For example 1 (even number of elements): Linked list elements: 1 2 3 4 5 6 7 8 K=2 Output: 4 5 6 c) StackADT: Implement raw array Stack ADT to include operations for create empty stack, isEmpty, isFull, push, pop, and size using the bellow pseudo code .

StackADT (using LinkedListADT) class StackADT LinkedListADT items // class attribute/member to store stack items in linked list StackADT() // constructor to initialize list Initialize items to empty list boolean isEmpty() // return true if empty and otherwise false if linked list is empty return true return false; void push(int item) add item to the top of stack int pop() if linked list is empty throw exception return item from the top of the stack int size() return number of elements StackADT (using raw array) class StackADT { int top // index of the top element in stack int items[] // array to store stack items int max // might not need if language allows determining size of array dynamically StackADT(int n) Initialize array to n capacity top = 0 max = n boolean isEmpty() if array has no elements return true return false boolean isFull() { if array is full

You should not have any other operations. Write main method to demonstrate the correct working of each operation in a separate test program. You must implement aclass called StackADT and TestStack class in a separate file.

d) QueueADT: Implement Queue ADT using the LinkedListADT from previous exercise to include operations for create empty queue, isEmpty, isFull, enQueue, and deQueue, and size using the bellow pseudo code . You should not have any other operations.

QueueADT (using LinkedListADT) class QueueADT LinkedList items // linked list to store items QueueADT() // constructor to initialize empty linked list Initialize items to empty list boolean isEmpty() if linked list is empty return true return false void enQueue(int item) add item to the end of the queue int deQueue() if (isEmpty()) throw exception

return first element in queue int size() return number of items QueueADT (using raw array) public class QueueADT { int end // keep track of number of items int items[] // array to store items int max // depending on language may not need; keep track of array capacity QueueADT(int n) // constructor to initialize queue to n capacity Initialize array to hold n items // language dependent end = 0 max = 0 boolean isEmpty() if no items in array // end == 0 return true return false boolean isFull() if already have max items in array return true return false void enQueue(int item) if (isFull()) throw exception add item to the end of the queue increment end int deQueue() if (isEmpty()) throw exception x = first item in queue loop to move all items to the previous index in array (e.g. x[0] = x[1] decrement end return x

int size() return number of items in array

Write main method to demonstrate the correct working of each operation in a separate test program. You must implement a class called QueueADT and TestQueue class in a separate file.

e) QueueReverseK: Write an algorithm, implemented as a method reverseK that takes as input an instance of Queue (use the above implementation of QueueADT) and integer K. Then it uses Stack and/or Queue (use the above implementation of StackADT and QueueADT) to reverse the order of the K elements in the Queue instance. You can only use the Stack operations and Queue operations listed above to implement the solution and you cannot use recursion. Main method should create and populate a Queue instance, call the reverseK algorithm, and display the changed Queue contents.

You must implement a single class called QueueReverseK with the method reverseK and main method. The program should use the QueueADT and StackADT classes. Evaluate and report the time and space complexity of your algorithm. For example: K=4 Original Queue Contents: 12 34 65 76 23 12 36 90 New Queue Contents: 12 34 65 76 90 36 12 23

Code For A,B & C as per request:

/// Answer for question::: A

//:::::::::::::::::::::::node.java:::::::::::

class Node{

int val;

Node next;

Node(int data)

{

this.val=data;

next = null;

}

}

//::::::::::::::::::::::::::::::::::: linked_list.java :::::::::::::::::::::::::::::::::::::::

class LinkedListADT{

/*

creating head and tail objects for Node class.

*/

Node head;

Node tail;

/*

Constructor...

here we set head and tail nodes are null...

*/

LinkedListADT()

{

head=null;

tail=null;

}

/*

Method to add data to head node.

*/

public void addHead(int val){

// creatiing new node while creating object val is set to the node from constructor..

Node n = new Node(val);

// if head is null indicate linkedlist is empty so head and tail both are same now.

if(head==null)

{

head=n;

tail=n;

}

// not null means linked list is not empty and we need to add data front of the inked list

else{

head.next=n;

head=n;

}

}

/*

Method to add data to Tail node.

*/

public void addTail(int val){

// creatiing new node while creating object val is set to the node from constructor..

Node n = new Node(val);

// if head is null indicate linkedlist is empty so head and tail both are same now.

if(head==null)

{

head=n;

tail=n;

}

// not null means linked list is not empty and we need to add data end of the inked list

else{

n.next=tail;

tail=n;

}

}

/*

Delete data from tail node.

*/

public int deleteTail(){

Node n= tail;

// If head is null it indicate linked list is empty.

if(head==null)

{

return -1;

}

// deleting from tail.

int val = tail.val;

// move the tail node to to front node.

tail = tail.next;

return val;

}

}

//:::::::::::::::::::::::::::::::::::::::::TestLinkedlist.java::::::::::::::::::::::::::::::::::::::

import java.util.*;

class TestLinkedList{

public static void main(String[] args) {

// creating scanner onbject

Scanner sc = new Scanner(System.in);

// creating linkedlistADT onject.

LinkedListADT obj = new LinkedListADT();

System.out.println("Enter head data: ");

/*

adding element to head.

*/

int val = sc.nextInt();

obj.addHead(val);

/*

inserting node at tail.

*/

val = sc.nextInt();

obj.addTail(val);

/*

inserting node at head

*/

val = sc.nextInt();

obj.addHead(val);

/*

inserting node at head

*/

val = sc.nextInt();

obj.addHead(val);

/*

inserting node at tail.

*/

val = sc.nextInt();

obj.addTail(val);

/*

inserting node at tail.

*/

val = sc.nextInt();

obj.addTail(val);

// deleting nodes... from tail ...

System.out.println("deleting order from tail::");

System.out.println(""+obj.deleteTail());

System.out.println(""+obj.deleteTail());

System.out.println(""+obj.deleteTail());

System.out.println(""+obj.deleteTail());

System.out.println(""+obj.deleteTail());

System.out.println(""+obj.deleteTail());

}

}

//..........................................MiddleNodeMain.java..................................

import java.util.*;

class MiddleNodeMain{

public static void main(String[] args) {

// creating scanner onbject

Scanner sc = new Scanner(System.in);

// creating linkedlistADT object.

LinkedListADT obj = new LinkedListADT();

int data;

int conti,ch;

do{

System.out.println("...................................");

System.out.println("1.add data before head 2.add data end of linkedlist ");

ch = sc.nextInt();

switch(ch)

{

case 1 :

System.out.println("Enter data:");

data = sc.nextInt();

obj.addHead(data);

break;

case 2 :

System.out.println("Enter data:");

data = sc.nextInt();

obj.addTail(data);

break;

}

System.out.println("If u want to continue enter 1: ");

conti= sc.nextInt();

}while(conti==1);

/*

calling to middleNode.

*/

System.out.println("Enter K value");

int k = sc.nextInt();

MiddleNode md = new MiddleNode();

md.middle(obj,k);

}

}

//.........................................................................MiddleNode.java................................

import java.lang.Math:

class MiddleNode{

int count=0;

int length;

Node last;

Node first;

int k;

public void middle(LinkedListADT list, int k)

{

last = list.tail;

first = list.head;

this.k=k;

recurssion(last); // using the recurrsion for the

}

public void recurssion(Node last)

{

if(last!=first) //

{

// untill last node and first node are same recurssion continue.

count++;

// every recurssion call count increment to know the length of the list.

recurssion(last.next);

}

else

{

//when last and first nodes are same if condition fails and enter into else.

// and set count value equals to length of th linkedlist.

length=count;

}

// .these are execute while call back

count--; // every callback count value decremented

if((Math.floor(length/2)-1)>=count)

{

// when count value equals to half of the length of the linkedlist then we are are at middle of linked list

// so we start printing the values here upto given k element.

if(k>=0)

System.out.println(" "+last.val);

// after printing every element we decrement the k value to know how many elements we printed still now.

k--;

}

}

}

/*

Time complexity :

we traverse the list only one time while recurssion so time complexity is O(n)

Space Complexity:

here we use the recurssion so we store at worst n recors on recurssion stack.

so space complexity is O(n)

Time complexity : O(n)

Space complexity: O(n)

*/

///::::::::::::::::::::::: StackADT.java::::::::::::::::::::::::::::::::::

/*

using LinkedListADT

*/

class StackADT{

//creating object for linkedlistADT..

LinkedListADT list = new LinkedListADT();

int size;

StackADT()

{

// initializing

list.head = null;

// tail is usedas top variable of stack here.

list.tail = null;

size=0;

}

/*

method to know stack empty of not

*/

public boolean isEmpty()

{

if(size==0) // size indicates number of elements in the stack.

return true;

return false;

}

/*

Method to push elements into stack.

*/

public void push(int item)

{

Node n = new Node(item);

// increment size

size++;

/*

list.tail is used here top variable for stack.

tail is null indicates stack is empty.

so we directly assign the node to head and tail

actually here no need of head.

*/

if(list.tail==null){

list.head=n;

list.tail=n;

}

/*

if stack is not empty

we insert new node at tail.

*/

else{

n.next=list.tail;

list.tail=n;

}

}

/*

Method pop elements from stack.

*/

public int pop()

{

// val is return value.

int val;

if(size==0)

{

// if size =0 indicates stack is empty.

System.out.println("Underflow: no elements in the stack.");

return -1;

}

else

{

// here remove top element from the stack.

val = list.tail.val;

list.tail=list.tail.next;

size--;

}

return val;

}

/*

return the size of the stack.

*/

public int size(){

return size;

}

}

//::::::::::::::::::::::::::::::::::::::::::: Stack.java:::::::::::::::::::::::::::::::::::;

import java.util.*;

class Stack{

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

StackADT sadt = new StackADT();

int ch;

int conti;

do{

System.out.println("1.push 2.pop 3.size 4.isEmpty ");

ch = sc.nextInt();

switch(ch)

{

case 1 :

System.out.println("Enter push element:");

sadt.push(sc.nextInt());

break;

case 2 :

System.out.println("poped element:\t"+sadt.pop());

break;

case 3 :

System.out.println("Sizeof stack:\t"+sadt.size());

break;

case 4 :

if(sadt.isEmpty())

System.out.println("Stack Empty");

else

System.out.println("Stack not empty");

break;

}

System.out.println("If u want to continue enter 1: ");

conti= sc.nextInt();

}while(conti==1);

}

}

//:::::::::::::::::::output::::::::::

//:::::::::::::::::::::::::::: stack using raw array::::::::::::::::::::::::

// file name : arraySatck.java

class arrayStack{

int max;

int top=0;

int size=0;

int stack[] ;

/*

constructor to assign the size to stack

*/

arrayStack(int max)

{

this.max=max;

stack = new int[max];

}

/*

push elements to the stack

*/

public void push(int item)

{

if(top

{

stack[top] = item;

top++;

size++;

}

else{

System.out.println("Stack overflowS");

}

}

/*

pop elements from the stack

*/

public int pop()

{

int item;

if(top>0)

{

item=stack[top-1];

top--;

size--;

return item;

}

else

{

System.out.println("Stack underflow");

return -1;

}

}

// return size of current stack

public int size()

{

return size;

}

// return empty or not

public boolean isEmpty()

{

if(size==0)

return true;

return false;

}

// return full or not

public boolean isFull()

{

if (max == size) {

return true;

}

return false;

}

}

//:::::::::::::::::::::::::::::::::::::::::::::::::: file name :stack_arr.java::::::::::::::::::::::::::::

import java.util.*;

class Stack{

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println("Enter max size of stack");

int size = sc.nextInt();

arrayStack sadt = new arrayStack(size);

int ch;

int conti;

do{

System.out.println("1.push 2.pop 3.size 4.isEmpty 5.isFull");

ch = sc.nextInt();

switch(ch)

{

case 1 :

System.out.println("Enter push element:");

sadt.push(sc.nextInt());

break;

case 2 :

System.out.println("poped element:\t"+sadt.pop());

break;

case 3 :

System.out.println("Sizeof stack:\t"+sadt.size());

break;

case 4 :

if(sadt.isEmpty())

System.out.println("Stack Empty");

else

System.out.println("Stack not empty");

break;

case 5 :

if(sadt.isFull())

System.out.println("Stack Full");

else

System.out.println("Stack not Full");

break;

}

System.out.println("If u want to continue enter 1: ");

conti= sc.nextInt();

}while(conti==1);

}

}

//:::::::::::::::::::OUTPUT