a Implement a program in Java to sort a stack of integer in

(a) Implement a program in Java to sort a stack of integer in ascending order using for this purpose another auxiliary (temp) stack.

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.

peek - operation that returns the value of the top element of the stack without removing it.

(b) What is the running time complexity of your program?

Solution

a.)

public static Stack<Integer> sort(Stack<Integer> s) {

  if (s.isEmpty()) {

    return s;

  }

  int pivot = s.pop();

  // partition

  Stack<Integer> left = new Stack<Integer>();

  Stack<Integer> right = new Stack<Integer>();

  while(!s.isEmpty()) {

    int y = s.pop();

    if (y < pivot) {

      left.push(y);

    } else {

      right.push(y);

    }

  }

  sort(left);

  sort(right);

  // merge

  Stack<Integer> tmp = new Stack<Integer>();

  while(!right.isEmpty()) {

    tmp.push(right.pop());

  }

  tmp.push(pivot);

  while(!left.isEmpty()) {

    tmp.push(left.pop());

  }

  while(!tmp.isEmpty()) {

    s.push(tmp.pop());

  }

  return s;

}