Part 1: Stacks We will implement a program that will use STACK to do the add, and multiplication. (Do not use the build in function or classes of Java or from the textbook). Create a stack class that takes integer (INTGER Class) Create a main that ask user to input commands If the user put integer value, push it to the stack (you need to check this) If they put any of the following symbols: + or * o Apply that operation on the 2 last items pushed to the stack (Hint make use pop) o If the stack doesn't have 2 items just ignore the operation o Store the result and push it to the stack If the user entered the ? symbol, print the stack- using toString() to print all the stacks items without popping them If the user put P, pop the stack and print the value If the user put the Z symbol, end the program If they put any other symbol/string - ignore it Write a Test program to: o Add 10 o Print stack Add 12 Print stack (now with 12, 10) o Add 14 Sum last 2 item Pop the stack (should be 24) Use * to multiply top 2 item Then type? O o Then stop the program with Z o Take screen shot of your program running O Part2: LinkedList insert We will implement a program that will use Priority Queues! We will create a list of random integers, create 3 methods of sorting them then sort them. Use the following code: import java.util.Random; // this creates random for our program public class App { //sample code for methods, create your own public static int mySort(int[] arr) { // YOUR CODE GOES HERE } return 0; public static void main(String[] args) throws Exception { int numitem = 100; // This decide how big you array is int[] myArr = new int[numitem]; Random myRand = new Random(); // creating Random object // Range for random to select from int min = 5; int max = 1000; } int indexMin = 0; for (int i= 0; i < myArr.length; i++) { myArr[i] = myRand.nextInt(max - min + 1) + min; // storing random integers in an array } // Now sort it double startTime = System.nanoTime(); // YOURSORTINGMETHOD(); double endTime= System.nanoTime(); double duration = (endTime - startTime); //divide by 1000000 to get milliseconds. System.out.println("the time it took to sort is " + duration); We provided the code for you to start Create the following Classes, remember you can do them in different classes (You may use LinkedList or array, your choice) (20%) o Heap o Priority Q with sorted Q o Priority Q with not sorted Q Now create sorting algorithm (30%) with their respective classes o Heap sort Insertion sort o Selection sort Answer: o o o O Do the Big-O analysis of each algorithm? Can you comment which one is faster? Do you think if we use array or LinkedList, we could speed the program up? Does the array initial order have any effect on the speed? Submit it in PDF