Please make sure program compiles in java. Write a method in Java to sort a stac
ID: 3673256 • Letter: P
Question
Please make sure program compiles in java.
Write a method in Java to sort a stack of n integer numbers, s, in descending order. static Stack sort(Stack s) To implement this method you must use one more auxiliary stack and you should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push, pop, peek, and isEmpty.(b) What is the running time complexity of your method? Justify.Explanation / Answer
import org.junit.Test; public class Solution { // Sort a stack in ascending order // May only use one additional stack to hold items // Stack supports push, pop, peek, and isEmpty private Stack stack; private Stack auxiliaryStack; @Test void testStackIncreasingOrder() { stack = new Stack(); stack.push(3); stack.push(2); stack.push(1); System.out.println("original stack"); printStack(); sortStack(); System.out.println("Sorted stack"); printStack(); } @Test void testEmptyStack(){ stack = new Stack(); System.out.println("original stack"); printStack(); sortStack(); System.out.println("Sorted stack"); printStack(); } @Test void testStackRandomOrder() { stack = new Stack(); stack.push(3); stack.push(2); stack.push(1); stack.push(5); stack.push(1); stack.push(1); stack.push(12); stack.push(0); System.out.println("original stack"); printStack(); sortStack(); System.out.println("Sorted stack"); printStack(); } public static void main(String[] args) { Solution e = new Solution(); System.out.println("Test reverse sorted stack"); e.testStackIncreasingOrder(); System.out.println("Test empty stack"); e.testEmptyStack(); System.out.println("Test randomly ordered stack"); e.testStackRandomOrder(); } public void sortStack() { auxiliaryStack = new Stack(); if (stack.isEmpty()) { return; } while (!stack.isEmpty()) { Object topOfStack = stack.pop(); if (auxiliaryStack.top != null) { Object topOfAuxiliary = auxiliaryStack.peek(); if ((Integer) topOfStack > (Integer) topOfAuxiliary) { emptyAuxiliary(); } } auxiliaryStack.push(topOfStack); } // System.out.println("AuxiliaryStack"); // printAuxiliaryStack(); emptyAuxiliary(); } public void emptyAuxiliary() { // Put all the elements of the auxiliary stack back in // the original one while (!auxiliaryStack.isEmpty()) { Object element = auxiliaryStack.pop(); stack.push(element); } } public Stack getStack() { return stack; } public void printStack() { Node current = stack.top; while (current != null) { System.out.println(current.data); current = current.next; } } public void printAuxiliaryStack() { Node current = auxiliaryStack.top; while (current != null) { System.out.println(current.data); current = current.next; } } } class Stack { Node top; Object pop() { if (top != null) { Object item = top.data; top = top.next; return item; } return null; } void push(Object item) { Node t = new Node(item); t.next = top; top = t; } Object peek() { return top.data; } boolean isEmpty() { if (top == null) { return true; } return false; } } class Node { Object data; Node next; public Node(Object item) { data = item; } public Node(Object item, Node n) { data = item; next = n; } }