Question

Recursively sorting an unbounded stack (java) in ascending order? (This assignment is only limited to stacks only, No other data structures are allowed)

My professor gave us a hint on how to implement this, however she wants the comparable interface to be used. im not sure on how to do this.

Hint: May want to use a public method that accepts the original stack and then creates the two additional stacks needed. This method then calls a private method that accepts all three stacks and does the recursive sort. Your methods should make sure all types of stacks passed contain comparable objects. Refer to the generic presentation in Shared Files.

What I have : unboundedarray.java

import java.util.ArrayList;

public class UnboundedStack
{
   protected ArrayList element;

   public UnboundedStack()
   {
     element = new ArrayList();
   }

   public T peek() throws StackUnderflowException
   {
     T topofstack = null;
     if(isEmpty())
     {
         throw new StackUnderflowException("Empty Stack");
     }
   
     else
         topofstack = element.get(element.size() - 1);
     return topofstack;
   }

   public void pop() throws StackUnderflowException
   {
     if(isEmpty())
     {
       throw new StackUnderflowException("empty stack");
     }
     else
         element.remove(element.size() - 1);
   }

   public void push(T elements) throws StackOverFlowException
   {
      element.add(elements);
   }

   public boolean isEmpty()
   {
      return (element.size() == 0);
   }

   public boolean isFull()
   {
     return false;
   }
}

my main class :

public class Recursivestack {

  
  
    public static UnboundedStack initializeSort(UnboundedStack s)
    {
        UnboundedStack temp = new UnboundedStack<>();
        UnboundedStack sort = new UnboundedStack<>();
        return temp; // this will need to be fixed
    }
  
  
  
  
    public static void main(String args[])
   {
       UnboundedStack unsorted = new UnboundedStack<>();
       unsorted.push("kevin");
       unsorted.push("brian");
       unsorted.push("devon");
       unsorted.push("larry");
       unsorted.push("kaiden");
       initializeSort(unsorted);
   }
}

Answer 1

Class UnboundedStack :

import java.util.ArrayList;

public class UnboundedStack<T> implements Comparable
{

protected ArrayList<T> element;
public UnboundedStack()
{
element = new ArrayList<>();
}

public ArrayList getElement() {
return element;
}
public T peek() throws RuntimeException
{
T topOfStack;
if(isEmpty())
{
throw new RuntimeException("StackUnderFlow Exception. Empty Stack");
}

else
topOfStack = (T) element.get(element.size() - 1);
return topOfStack;
}
public T pop() throws RuntimeException
{
if(isEmpty())
{
throw new RuntimeException("StackUnderFlow Exception. Empty stack");
}
else {
T popElement = (T) peek();
element.remove(element.size() - 1);
return popElement;
}
}
public void push(T elements) throws RuntimeException
{
element.add(elements);
}

public boolean isEmpty()
{
return (element.size() == 0);
}

@Override
public int compareTo(Object o) {
if(o.hashCode() == peek().hashCode()) {
return 0;
}else if(peek().hashCode() > o.hashCode()){
return 1;
}else{
return -1;
}
}
}

********************************************************************************************************

Class Sort :

public class Sort<T> {

// Method to sort stack
public void sortStack(UnboundedStack<T> stack){

// If stack is not empty
if(!stack.isEmpty()){

// Remove the top item
final T temp = stack.pop();

// Sort remaining stack
sortStack(stack);

// Push the top item back in sorted stack
sortedInsert(stack, temp);
}
}

// Recursive Method to insert an item x in sorted way
public void sortedInsert(UnboundedStack<T> stack, final T element){
int result = 2;
if(!stack.isEmpty()){
result = stack.compareTo(element);
}
// Base case: Either stack is empty or newly inserted
// item is greater than top (more than all existing)
if(stack.isEmpty() || result == -1){
stack.push(element);
return;
}
// If top is greater, remove the top item and recurse
final T temp = stack.pop();
sortedInsert(stack, element);

// Put back the top item removed earlier
stack.push(temp);
}
}

*********************************************************************************************

Main Method :

import java.util.ArrayList;

public class RecursiveStack {

public static void main(String args[]) {
Sort<String> sortStringStack = new Sort<>();
UnboundedStack<String> unsortedStringStack = new UnboundedStack<>();
unsortedStringStack.push("kevin");
unsortedStringStack.push("brian");
unsortedStringStack.push("devon");
unsortedStringStack.push("larry");
unsortedStringStack.push("kaiden");
sortStringStack.sortStack(unsortedStringStack);
ArrayList<String> stringArrayList = unsortedStringStack.getElement();
for (String element : stringArrayList) {
System.out.println(element);
}

Sort<Integer> sortIntegerStack = new Sort<>();
UnboundedStack<Integer> unsortedIntegerStack = new UnboundedStack<>();
unsortedIntegerStack.push(10);
unsortedIntegerStack.push(1);
unsortedIntegerStack.push(3);
unsortedIntegerStack.push(12);
unsortedIntegerStack.push(12);
unsortedIntegerStack.push(-9);
unsortedIntegerStack.push(88);
unsortedIntegerStack.push(0);
unsortedIntegerStack.push(5);
sortIntegerStack.sortStack(unsortedIntegerStack);
ArrayList<Integer> integerArrayList = unsortedIntegerStack.getElement();
for (Integer element : integerArrayList) {
System.out.println(element);
}

}
}